코테/백준 온라인 저지(BOJ)

    [백준,BOJ 10773] 제로(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 10773] 제로(JAVA 구현)

    - 풀이 문제의 분류 자체가 스택이기 때문에 스택을 사용해야 한다는 생각이 들기도 하지만, 문제를 잘 읽어보면 정수가 계속 입력될 때 '0'이 입력되면 0이 입력되기 이전의 정수 하나를 지우기 때문에 최근에 입력된 데이터가 가장 먼저 출력되는 LIFO 구조의 스택을 사용해야 한다는 사실을 알 수 있다. 필자는 처음에 모든 정수를 입력받아 스택에 PUSH해준 뒤, POP 해가면서 0이 나오면 한 번 더 POP을 하는 식으로 접근하였지만, 예제 입력 2와 같이 0이 연속으로 입력되는 경우, 최근의 정수를 제대로 지우지 못하기 때문에 입력받을 때 0이면 바로 지워주게끔 풀이하였다. import java.io.BufferedReader; import java.io.BufferedWriter; import jav..

    [백준,BOJ 10828] 스택(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 10828] 스택(JAVA 구현)

    -풀이 자료구조 중 LIFO구조인 스택의 기본적인 동작들을 구현하는 문제로, 자바의 경우 배열과 연결 리스트를 활용하여 직접 구현이 가능하며, 별도의 Stack 라이브러리가 제공되어 해당 메서드를 이용해도 된다. 필자는 배열과 라이브러리를 이용해 구현해 보았다. 또, 이 문제에서 주의해야 할 점은 제한시간이 0.5초로 상당히 짧기 때문에, BufferedReader와 BufferedWriter 객체를 사용하는 것이 좋을 것 같다. - 배열을 이용해 직접 Stack 클래스 구현 방법. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; i..

    [백준,BOJ 1541] 잃어버린 괄호(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 1541] 잃어버린 괄호(JAVA 구현)

    - 풀이 이 문제의 경우 예제로 주어진 55-50+40이 55-(50+40)의 형태로 괄호를 씌워야 최솟값을 만들 수 있다는 사실을 알고, -를 기준으로 입력받은 문자열을 하나씩 탐색하며 다음 -를 만날 때까지 숫자들을 더하는 방식을 생각해 시도하였다. 그러나 문제에서 주어진 첫 문자와 마지막 문자는 숫자라는 조건을 보지 못하고 첫 문자에 음수가 입력되는 경우까지 생각하다 너무 복잡해져서 포기했다. 그런데 저 조건을 확인하고 나니 할 수 있을 것 같기도 하다. 결국 이 문제를 풀기 위해서는 -를 기준으로 문자열을 파싱해주면 된다는 것이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanne..

    [백준,BOJ 11399] ATM(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 11399] ATM(JAVA 구현)

    -풀이 그리디 알고리즘을 사용하기 적합한 문제의 조건은 1. 각 경우가 독립적인 경우 2. 각 경우의 선택으로 다른 경우에 영향을 미치지 않는 경우를 만족하면 된다고 알고 있다. 이 문제의 경우 각 사람들의 대기시간이 상호 영향을 받지 않는 독릭접인 상태이다. 그리디 알고리즘을 이용해 손님들의 소요시간을 최소로 만들기 위해서는 먼저 끝나는 사람을 우선으로 처리하면 최솟값이 나오게 된다. 이는 이전의 회의실 배정 문제와 비슷한 유형이라고 생각된다. 그렇기에 문제에서 알려주고 있는 최솟값을 구하는 방법을 코딩으로 옮기기만 하면 된다. import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(Str..

    [백준,BOJ 1931] 회의실 배정(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 1931] 회의실 배정(JAVA 구현)

    -풀이 처음 이 문제를 풀 때는 각 회의 정보를 시작시간을 기준으로 정렬하여 회의별 소요되는 시간이 가장 짧은 순서대로 조건을 걸어 카운팅을 하려 했지만, 조건이 애매해져 다른 분의 글을 참고하였다. 다른 분의 글에서는 정렬을 종료시간을 기준으로 하여, 가장 일찍 끝나는 회의 순서대로 카운팅 하는 방법을 사용했다. 맞다. 회의실을 가장 많이 돌리려면, 빨리 끝나는 순서대로 집어넣는 것이 그리디라고 할 수 있다. import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(..

    [백준,BOJ 11047] 동전 0(JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 11047] 동전 0(JAVA 구현)

    - 풀이 이전에 풀었던 문제였지만, 블로그에 글을 게시하지 않았던 문제이다. 단계별 풀어보기의 그리디 알고리즘으로 분류되어 있는 첫 번째 문제이다. 그리디 알고리즘이란, 한 상황에서 취할 수 있는 최대 이득을 취하는 알고리즘이라 한다. 이러한 방식은 이전 분류인 동적 프로그래밍의 과정이 너무 많은 연산이 이루어지기 때문에 이를 보완하기 위해 고안된 알고리즘이라 한다. 한 상황에서 최선의 것을 선택하다 보니 최적의 해를 보장하지 않는다는 특징이 있다고 한다. 그리디 알고리즘으로 분류되어 있는 특징처럼 문제에서 주어진 값 k를 최소한의 동전 개수로 이루기 위해서는 가장 높은 단위의 화폐부터 사용하면 최소한의 동전 개수를 사용하게 된다. 최소한의 동전 개수를 이루기 위해 가장 높은 단위의 화폐부터 사용한다는 ..

    [백준,BOJ 12865] 평범한 배낭(JAVA 구현, 추가풀이)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 12865] 평범한 배낭(JAVA 구현, 추가풀이)

    -내 생각 이 문제의 경우 혼자 풀어보려고 해서 결과는 잘 나오는 것 같은데 어떤 반례에서 걸리는지 계속 오답처리를 받아서 결국 검색을 해봤는데, 이러한 무게와 가치가 함께 주어지는 문제의 경우 knapsack 알고리즘이라고 별도로 존재한다는 사실을 알 수 있었다. -해법 knapsack알고리즘의 경우에 dp 배열을 1차원 또는 2차원으로 해결할 수 있다고 하는데, 많은 사람들이 2차원 배열을 사용하는 것 같다. 나의 경우는 알고리즘 대회를 준비하는 것이 아닌, 취업을 위한 공부이기 때문에 합격선만 만족하면 더 쉬운 것을 사용하는 것이 맞는 것 같다. dp배열을 사용할 때 각 인덱스가 의미하는 바는 dp [i번 째 아이템][무게]를 의미한다고 한다. 이를 표로 그려보면 아래와 같이 나타낼 수 있다. 0번..

    [백준,BOJ 1912] 연속합(JAVA 구현,추가풀이)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 1912] 연속합(JAVA 구현,추가풀이)

    -내 생각 문제를 제대로 읽어보지 않아서 점화식을 세울 수가 없었다. 이 문제에서 중요하게 보아야 할 내용은 수를 선택할 때 한 개 이상의 수를 연속되게 선택해야 한다는 제약조건이 있다. 즉 1번 숫자를 선택한 후 2번 숫자를 선택하지 않으면 더 이상 선택할 수 가없는 것이다. -해법 그렇다면 이 문제는 어떻게 해결해야 할까? 별도의 dp배열을 생성하여 누적된 값과 현재부터 다시 선택을 시작한 값을 비교해주면 간단하다. 우선 기본적인 점화식은 dp [n] = dp [n-1] + cost [n]이 되는데(기본 누적 점화식), 연속해서 선택해야 한다는 제약조건이 존재하기 때문에 예를 들어, 2번까지 누적해서 선택한 결과와 2번이 첫 번째로 선택된 결과 중 큰 값을 취해야 한다는 것인데, 1번, 2번을 누적하..

    [백준,BOJ 9251] LCS(JAVA 구현,추가풀이)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 9251] LCS(JAVA 구현,추가풀이)

    -내 생각 LIS알고리즘에 이은 LCS알고리즘이다. 전혀 처음 보는 유형의 문제였기 때문에 혼자 힘으로 풀지는 못했다. -해법 LCS의 경우 주의해야 할 경우가 Longest Common Subsequence인 최장 공통부분 순열이 있고, Logest Common Substring인 최장 공통부분 문자열인 경우가 있다고 한다. 순열의 경우는 현재 문제처럼 연속되는 문자는 고려하지 않고 단순히 두 문자열을 비교해서 겹치는 경우의 수를 구하는 것이다. 예를 들어 ACAYKP는 CAPCAK와 비교했을 때, A, C, P, K가 순서에 고려되지 않고 겹치게 된다. 그러나 문자열의 경우는 CA만이 순서와 내용이 일치한다는 차이점이 있다. LCS의 경우에는 2차원 배열을 이용해서 구하게 되는데 https://you..

    [백준,BOJ 11054] 가장 긴 바이토닉 부분 수열(JAVA 구현,추가풀이)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 11054] 가장 긴 바이토닉 부분 수열(JAVA 구현,추가풀이)

    -내 생각 이 문제를 이해할 때 주의해야 할 점이 하나 있는데, 바이 토닉 부분 수열과 바이 토닉 수열의 구분을 확실히 해야 한다. 이 문제에서 묻는 대상은 바이 토닉 부분 수열이기 때문에 문제에서 예로 든 {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이 토닉 수열이 아니라는 것이다. 처음 구현하기에 앞서 바이 토닉 부분 수열의 경우 가장 큰 값을 기준으로 왼쪽으로는 작은 값을 갖고, 오른쪽으로는 큰 값을 가지는 것을 보고 우선 가장 큰 값을 찾은 후 왼쪽부터 증가하다가 큰 값을 만나면 그 이후부터는 작은 값을 처리해 주려고 했지만, 구현에 실패해서 다른 분들의 글을 통해 도움을 받았다. -해법 우선 이 문제를 풀기 위해서는 LIS라는 개념이 완벽..

티스토리툴바