https://www.algospot.com/judge/problem/read/TRIANGLEPATH
algospot.com :: TRIANGLEPATH
삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래
www.algospot.com
코드설명
동적계획법을 활용합니다.
첫번째 코드는, 완전탐색을 활용합니다.
완전탐색의 경우 재귀를 활용하여 구현했습니다.
하지만, 이 방법의 경우 2^(n)개의 시간복잡도를 가지기에 시간초과가 발생합니다.
n이 총 100개까지 가능하기에 2^100은 당연히 시간초과가 납니다.
두번쨰 코드는, 메모이제이션을 활용하여 부분문제에 대한 중복계산을 피할 수 있습니다.
어떻게 메모이제이션을 활용할 수 있을까요?
1. r과 c는 재귀 호출이 풀어야 할 부분 문제를 지정합니다. 이 두 입력이 정해지면 앞으로 우리가 만들 수 있는 경로들이 정해집니다. 따라서 이들은 앞으로 풀어야할 조각들에 대한 정보를 주는 입력들입니다.
2. 즉, 앞으로 풀어야 할 문제들에 대한 정보인 r과 c만을 활용하여 재귀함수를 작성합니다. 물론, 참조적 투명성 또한 지켜져야 할 것 입니다.
3. 위의 정의를 통해 findPathWithMemoziation(int r, int c)의 반환 값을 전체 경로의 최대치가 아니라 (r, c)에서 시작하는 부분 경로의 최대치로 바꿔야 합니다.
즉, 아래와 같이 정의합니다.
findPathWithMemoziation(int r, int c) : (r,c)에서 시작해서 맨 아래줄까지 내려가는 부분 경로의 최대합을 반환합니다.
전체경로의 최대 합을 반환하는 것이 아닌 부분 경로의 최대합을 반환한다는 것에 유의합니다.
첫번쨰 코드인 완전탐색 코드는 전체 경로의 최대합을 모아서 한번에 반환하는 것을 알 수 있습니다. 그 반환 값 자체가 결국에 답이었습니다.
두번쨰 코드인 메모이제이션 코드는 부분 경로의 최대합을 반환함으로써 부분문제로 나눌 수 있습니다. 이떄, 앞으로 연산에 영향을 미치는 값들인 r, c만 매개변수 인자로써 넘겨줌으로써 함수가 가벼워지고 목적에 맞게 진행됩니다.
위의 정리는 곧, 어떤 경로로 이 부분 문제에 도달했건 남은 부분문제는 항상 최적으로 풀어도 상관없다는 의미입니다. 이러한 구조를 최적 부분 구조(optimal substructure)라고 명명하며 동적계획법의 중요 요소로 꼽습니다.
최적 부분 구조는 어떤 문제와 분할 방식에 성립하는 조건입니다. 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우 이 조건이 성립한다고 합니다. 삼각형 문제에서는 어느쪽으로 내려갈지의 선택에 따라 두개의 부분 문제로 문제를 분할할 수 있었습니다. 이댸 지금까지의 선택과 상관 없이 각 부분 문제를 최적으로 풀기만 하면 전체 문제의 최적해도 할 수 있습니다. 따라서 최적 부분 구조가 성립함을 알 수 있습니다.
코드
완전탐색 코드입니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int[][] map;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- >0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
map = new int[N][N];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<i+1;j++) {
int value = Integer.parseInt(st.nextToken());
map[i][j] = value;
}
}
System.out.println(findPath(0, 0));
}
}
public static int findPath(int r, int c) {
//기저사례 0 : 범위를 벗어나는경우
if(r >= N || c >= N) return 0;
return map[r][c] + Math.max(findPath(r + 1,c), findPath(r + 1, c + 1));
}
}
메모이제이션 Cache를 활용한 경우입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int[][] map;
//-1은 아직 답이 계산되지 않았음을 의미합니다.
//1은 해당 입력들이 서로 대응됨을 의미합니다.
//0은 해당 입력들이 서로 대응되지 않음을 의미합니다.
public static int[][] cache;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- >0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
map = new int[N][N];
cache = new int[N][N];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
Arrays.fill(cache[i], -1);
for(int j=0; j<i+1;j++) {
int value = Integer.parseInt(st.nextToken());
map[i][j] = value;
}
}
System.out.println(findPathWithMemoization(0, 0));
}
}
public static int findPathWithMemoization(int r, int c) {
//기저사례 0 : 범위를 벗어나는경우
if(r >= N || c >= N) return 0;
if(cache[r][c] != -1) return cache[r][c];
return cache[r][c] = map[r][c] + Math.max(findPathWithMemoization(r + 1,c), findPathWithMemoization(r + 1, c + 1));
}
}
메모이제이션 Cache를 활용한 코드 2입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int answer = 0;
public static String W, fileName;
public static int[][] map, cache;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- >0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
map = new int[N][N];
cache = new int[N][N];
for(int i=0;i<N;i++) {
Arrays.fill(cache[i], -1);
st = new StringTokenizer(br.readLine());
for(int j=0; j<=i; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(getTrianglePathCount(0, 0));
}
}
public static int getTrianglePathCount(int r, int c) {
//기저사례 : 만약, 마지막 칸이라면 종료한다.
if(r == N - 1) return map[r][c];
if(cache[r][c] != -1) return cache[r][c];
int ret = Integer.MIN_VALUE;
ret = Math.max( getTrianglePathCount(r + 1, c), getTrianglePathCount(r + 1, c + 1)) + map[r][c];
return cache[r][c] = ret;
}
}
코드설명
재귀호출과 메모이제이션으로 구현하지 않고, 반복적 동적 계획법으로도 구현할 수 있습니다.
path2(y, x) = triangle[y, x] + Math.max(path2(y+1, x), path2(y + 1, x + 1)) 이라는 점화식이 성립하므로, 적용할 수 있습니다.
코드
반복적 동적 계획법을 적용한 방식입니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static int N, M, C, T, K;
private static int answer = 0;
private static int[][] arr;
private static int[][] DP;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- > 0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N][N];
DP = new int[N][N];
for(int i=0;i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<i+1; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(iterative());
}
}
private static int iterative() {
//기저사례를 계산한다.
for(int x = 0; x < N; x++) {
DP[N-1][x] = arr[N-1][x];
}
//다른 부분을 계산한다.
for(int y = N-2; y >= 0; y--) {
for(int x = 0; x < y + 1; x++) {
DP[y][x] = Math.max(DP[y+1][x], DP[y+1][x+1]) + arr[y][x];
}
}
return DP[0][0];
}
}
슬라이딩 윈도를 이용하여 공간복잡도를 줄입니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static int N, M, C, T, K;
private static int answer = 0;
private static int[][] arr;
private static int[][] DP;
private static int[][] DP2;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- > 0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N][N];
DP = new int[N][N];
DP2 = new int[2][N*N];
for(int i=0;i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<i+1; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(iterative());
}
}
private static int iterative() {
//기저사례를 계산한다.
for(int x = 0; x < N; x++) {
DP2[(N-1)%2][x] = arr[N-1][x];
}
//다른 부분을 계산한다.
for(int y = N-2; y >= 0; y--) {
for(int x = 0; x < y + 1; x++) {
DP2[y%2][x] = Math.max(DP2[(y+1)%2][x], DP2[(y+1)%2][x+1]) + arr[y][x];
}
}
return DP2[0][0];
}
}'알고리즘 > 알고리즘 문제해결 전략' 카테고리의 다른 글
| [종만북][알고스팟] 합친 LIS (JLIS) - 동적계획법(Dynamic Programming) JAVA (0) | 2024.06.08 |
|---|---|
| [종만북][알고스팟] 최대 증가 부분 수열 (LIS) - 동적계획법(Dynamic Programming) JAVA (0) | 2024.06.08 |
| [종만북][알고스팟] 와일드카드 (WILDCARD) - 동적계획법(Dynamic Programming) JAVA (0) | 2024.06.08 |
| [종만북][알고스팟] 외발 뛰기 (JUMPGAME) - 동적계획법(Dynamic Programming) JAVA (0) | 2024.06.07 |
| [종만북] 이항 계수 - 동적계획법(Dynamic Programming) JAVA (0) | 2024.06.07 |