알고리즘 스터디 (35) 썸네일형 리스트형 [JAVA] BOJ 11399 ATM 그리디 알고리즘 문제 중에서도 가장 쉬운 문제인 것 같다. 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 찾는 문제인데 단순하게 각 사람의 기다리는 시간이 주어졌을 때 오름차순으로 정렬해서 세우는 것이 최소이다. 왜냐하면 돈을 인출하는데 걸리는 시간이 긴 사람이 앞에 있으면 계속 누적이 되기 때문에 값이 커질 수밖에 없다. 따라서 주어진 배열을 오름차순으로 정렬한 다음 각 요소를 이전 값까지의 누적 값과 더해 새롭게 저장한다. 즉, A(i) = A(i-1) + A(i) 이다. Input에는 BufferedReader 와 Output에는 System.out.println을 사용했다. public class Main { public static void main(String[] args) throw.. [JAVA] BOJ 11047 동전 0 그리디 알고리즘은 탐욕 알고리즘이라 하여 뒤를 생각하지 않고 각 상황에서 최선의 선택만을 하는 알고리즘을 의미한다. 이 문제에서는 예제에서 주어진 4200원을 만들기 위해 4200원보다 작은 것 중 가장 큰 동전을 선택하여 (예제에선 1000원) 개수에 4200/1000 한 것을 더해주고 K = 4200%1000 = 200으로 만들어주어 K가 0이 될 때까지 위의 과정을 반복합니다. 첫 번째 동전의 값은 1이기 때문에 K가 0이 안될 가능성은 없다. Input으로 주어지는 값이 많기 때문에 BufferedReader를 사용했고 출력되는 수는 한 개 밖에 없기 때문에 System.out.println을 사용했다. public class Main { public static void main(String[].. [JAVA] BOJ 1158 요세푸스 문제 원으로 앉아있다는건 배열을 순환한다는 것과 같다. 따라서 배열의 끝에 도착하면 다시 처음으로 돌아가도록 해주는 것이 핵심이다. 또한 K번째 사람을 제거한다는 것은 배열을 순환하면서 K번째를 방문했으면 넘어가도록 구현하였다. 독특한 출력형태로 input은 Scanner로 받고 출력은 BufferedWriter를 사용하였다. public class Main { public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String st = sc.nextLine(.. [JAVA] BOJ 9012 괄호 스택을 이용해서 푸는 문제이다. Stack은 LIFO구조로 한쪽 끝이 막혀있는 병을 생각하면 된다. 이 문제의 경우 입력값으로 들어오는 괄호를 병(스택)에 넣기 전에 병에 가장 마지막에 들어가 있는 괄호와 더해 () 즉 VPS 인지 검사한 다음 만약 VPS라면 병에 들어있는 마지막 괄호를 제거해주고 아니라면 병에 넣어주면 된다. INPUT/OUTPUT 에는 BufferedReader/BufferedWriter 를 사용하였다. import java.io.*; import java.util.*; public class Main { public static long[] N_li = new long[101]; public static void main(String[] args) throws IOException.. [JAVA] BOJ 11053 가장 긴 증가하는 수열 동적 계획법 문제답게 메모이제이션과 점화식을 생각해봐야 한다. A= {10, 20,10, 30, 20, 50} 라면 F(N) 은 N번째 요소가 이전 요소 중 몇 번째로 증가하는 수열인지 저장한다. 즉, 3번째 요소인 10은 이전 값 {10, 20} 중 1번째로 증가하는 수열이기 때문에 1이 F(3) = 1이 된다. 이처럼 A의 모든 요소를 반복문으로 돌면서 F(N) 값을 저장한 뒤 출력할 때는 F(N) 중 가장 큰 값을 출력하면 된다. 코드로 보면 import java.io.*; import java.util.*; public class Main { public static Integer[] DP; static ArrayList cost = new ArrayList(); public static void.. [JAVA] BOJ 1463 1로 만들기 생각보다 간단하게 풀 수 있는 문제였는데 정답 비율이 낮아서 놀랐다. 동적 계획법 문제이다 보니 이 역시도 메모이제이션과 점화식만 찾아내면 문제를 풀 수 있다. 이 문제는 연산을 사용하는 횟수의 최솟값을 출력하는 문제이다 보니 메모이제이션 해야 하는 값은 주어진 N을 1로 만드는데 까지 드는 연산 횟수의 최솟값이다. N이 2로 나누어지는지 3으로 나누어지는지에 따라 다른 케이스로 나뉘며, 각 케이스마다 N을 1로 빼는 케이스가 더해져 최솟값을 비교해야 한다. 예제를 보면, 10을 입력했을 때 10은 2로 나눠지기 때문에 F(10) = Math.min(F(10/2),F(10-1)) + 1으로 구할 수 있다. 한번 다음 단계로 갈 때마다 횟수를 추가해줘야 하기 때문에 +1을 한 것이다. 위의 식은 다시 F(.. [JAVA] BOJ 2579 계단 오르기 계단 오르기 문제는 정답 비율이 35% 정도 되는 어려운 문제였다. 꽤나 까다롭고 예상치 못한 부분이 있어서 2일 정도 계속 고민했던 것 같다. 이전 정수 삼각형 문제와 같이 마지막 계단으로 가는데 누적합이 최대가 되는 경로를 찾아 그 최대 누적합을 출력하는 문제이다. 동적 계획법 문제들이 그렇듯 메모이제이션과 점화식을 잘 찾아내면 해결할 수 있지만 이번 포스팅에선 내가 실패했던 케이스와 이를 해결한 과정을 기록하고자 한다. 실패한 케이스 문제의 조건은 세 개이다. 계단은 한 칸 혹은 두 칸씩 오를 수 있으며 연속된 세 개의 계단은 밟지 못하고 마지막 계단은 '반드시' 밟아야 한다. 문제는 이전 정수 삼각형 문제와 비슷하기 때문에 이 역시도 그와 같은 방법으로 DP 배열에 해당 칸까지의 최댓값을 저장해가.. [JAVA] BOJ 1932 정수 삼각형 동적계획법 문제임에 따라 점화식을 구하고 메모이제이션을 어떻게 할지 먼저 구상해야 한다. 입출력에는 BufferedReader 와 System.out.println을 사용하였다. 1. 메모이제이션(Memoization) 우선 정수 삼각형을 이루고 있는 값들을 cost(비용) 이라 하면, 이 cost는 2차원 배열이 된다. 또한 최대 누적값을 저장하는 2차원 배열 DP[][] 를 만들어 i행 j열의 요소까지의 최대값을 저장하여 중복되는 계산과정을 줄일 수 있다. 예를 들어, 2 1 3 1 2 0 인 2차원 배열이 입력값으로 주어졌을 때, cost는 [2][0][0] [1][3][0] [1][2][0] 이 되고 DP배열은 로직을 다 돌고나면 다음과 같은 배열이 될 것이다. [2][-1][-1] [3][5][.. 이전 1 2 3 4 5 다음
