[종만북][알고스팟] 최대 증가 부분 수열 (LIS) - 동적계획법(Dynamic Programming) JAVA

https://www.algospot.com/judge/problem/read/LIS

algospot.com :: LIS

코드설명

동적계획법을 사용합니다.

 

첫번째는 완전탐색입니다.

처음에 틀렸던 부분은, 

public static int calculateLis(int idx) {
    //기저사례 0 : 범위를 벗어날경우 중단
    if(idx >= N) return 0;

    int cnt = 1;
    for(int i=idx + 1; i<N; i++) {
        if(arr[idx] < arr[i])
            cnt = Math.max(cnt,  calculateLis(i) + 1);
    }
    return cnt;
}

에서 아래와 같이 + 1 을 바깥에서 처리했던 점입니다.

cnt = Math.max(cnt,  calculateLis(i) ) + 1;

위와 같이 할경우, calculateLis가 실행되면 반환되면서 1개의 LIS값을 증가시켜주는데, 밖에서 처리할경우 의미없이 모든 반복문마다 + 1을 하기에, 올바르게 재귀함수의 실행 횟수에 따른 개수를 증가시키지 못합니다.

 

아래와 같이 수정합니다. 이를 통해 각 재귀함수의 실행횟수만큼만 개수가 증가합니다.

    cnt = Math.max(cnt,  calculateLis(i) + 1);

 

또한 두번쨰로, 기저사례가 필요없습니다. 

이 부분은 두번쨰 메모이제이션 문제를 풀떄 cache[start] = 1로 초기화해야 한다는 걸 꺠닫게 되면서 알게된 부분입니다.

//기저사례 0 : 범위를 벗어날경우 중단 --> 사실 이부분은 필요없었습니다. 애초에 for문에서 N값이 넘어가게 처리안하기 때문입니다.
if(idx >= N) return 0;

 

 

 

두번쨰는 메모이제이션 적용해보기 입니다.

이전에 풀었던 TrianglePath 문제의 최적화 과정이 떠오릅니다. 

위의 문제와 마찬가지로 이전의 선택은 이후의 선택에 전혀 영향을 미치지 않습니다.

LIS에서는 이전에 선택한 정수가 이후의 선택할 정수의 결과에 전혀 영향을 미치지 않는 다는 것 입니다.

 

그렇기에 부분문제의 정의를

lis(start) = S[start]에서 시작하는 부분 증가 수열 중 최대의 길이로 생각합니다.

이렇게 정의함으로써, 앞으로 특정 Cache[start]를 start 위치에서의 최적화 값으로 선택합니다. 즉 어떤 재귀함수가 오든 간에 이 start 인덱스에서의 최대값은 Cache[start]인 것 입니다. 이는, 이전의 결과가 Cache에 전혀 영향을 미치지 않기에 그렇습니다.

 

또, 문제를 풀면서 큰 부분을 틀렸습니다.

하단의 코드에서 처음에 cache[start] = 1을 제거한 상태에서 int cnt = 1 만으로 처리했었습니다.

그렇게 할경우, 저는, for문이  next < N 까지 임을 놓치고 N까지 호출된 후 기저사례가 종료된 후에 반환되며 + 1 이 될 것 이라 생각했습니다. 하지만, for문으로 next < N까지이며, 직관적으로 Cache[start]의 정의는 start 점에서의 LIS최대 길이를 의미하므로 start 위치의 첫 LIS시작은 반드시 1로써 시작해야만 합니다.

잘못된 재귀호출에 대한 생각으로 고민을 했었습니다.

public static int calculateLis(int start) {
//		기저사례 0 : 범위를 벗어날경우 중단--> 애초에 for문에서 N이상으로 호출 못하도록 합니다. 
//		if(start >= N) return 0;
    if(cache[start] != -1) return cache[start];

//		int cnt = 1;
    cache[start] = 1;
    for(int next=start + 1; next<N; next++) {
        if(arr[start] < arr[next])
            cache[start] = Math.max(cache[start],  calculateLis(next) + 1);
    }
    return cache[start];
}

 

세번쨰 부분은,  시작위치 고정하기 입니다.

2번 코드를 살펴보면, 모든 부분마다 직접 calculateLis(i)를 실행하고 있습니다.

이를 외부에서 호출하지 않고 한번의 수행으로 모든 구간을 구할 수 있습니다.

    for(int i=0;i<N;i++) answer = Math.max(answer, calculateLis(i));

 

S[-1] = -무한대 라고 가정하는 코드를 작성합니다. calculateLis(-1)을 호출하면 항상 -무한대 부터 시작하니, 모든 시작위치를 자동으로 시도하게 됩니다.

이와 같이 처리할경우 Cache[start + 1]로 -1이 0 으로 바뀌어 처리하도록 수정해야 합니다.

그렇다면, for문에서의 작업은 어떻게 처리할지 고민이 됩니다.

start == -1 이 먼저 참이기에 arr[start < arr[next]를 검사하지 않고 바로 조건문이 실행됩니다. 그렇기에 IndexOutofError가 발생하지 않습니다.

if(start == -1 || arr[start] < arr[next])
    cache[start + 1] = Math.max(cache[start + 1],  calculateLisWithFixingStartPoing(next) + 1);

 

또, 문제의 답을 보면 answer값에 -1 을 처리하는 것을 확인할 수 있습니다. 

왜 이와 같은 처리를 할까요?

arr[Start] = -1 은 우리가 가상으로 추가한 입력값이기에 재귀함수가 start가 -1 일경우 한번 더 실행됩니다.

즉, 재귀함수가 -1 부터 시작되며 기존에 실행되던 횟수보다 재귀함수가 +1번씩 더 실행됩니다. 그렇기에 answer값에는 -1 을 출력해줘야 합니다.

 

또한 cache[start + 1] = 1 이라고 설정하는 이유는 항상 cache[start]는 있기 때문에 길이는 최하 1이기 떄문입니다.

 

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	public static int[] arr;
	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());
			arr = new  int[N];
			st = new StringTokenizer(br.readLine());
			answer = 0;
			for(int i=0;i<N;i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			
			for(int i=0;i<N;i++) {
				answer = Math.max(answer, calculateLis(i));
			}
			System.out.println(answer);
		}
	}
	
     // S[start]에서 시작하는 부분 증가 수열 중 최대의 길이를 반환한다.
	public static int calculateLis(int idx) {
		//기저사례 0 : 범위를 벗어날경우 중단 --> 사실 이부분은 필요없었습니다. 애초에 for문에서 N값이 넘어가게 처리안하기 때문입니다.
		if(idx >= N) return 0;
		
		int cnt = 1;
		for(int i=idx + 1; i<N; i++) {
			if(arr[idx] < arr[i])
				cnt = Math.max(cnt,  calculateLis(i) + 1);
		}
		return cnt;
	}
	
}

 

 

메모이제이션 적용

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 int[] arr;
	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());
			arr = new  int[N];
			st = new StringTokenizer(br.readLine());
			cache = new int[N];
			answer = 0;
			Arrays.fill(cache, -1);
			for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());
			for(int i=0;i<N;i++) answer = Math.max(answer, calculateLis(i));
			
			System.out.println(answer);
		}
	}
	
     // S[start]에서 시작하는 부분 증가 수열 중 최대의 길이를 반환한다.
	public static int calculateLis(int start) {
//		기저사례 0 : 범위를 벗어날경우 중단--> 애초에 for문에서 N이상으로 호출 못하도록 합니다. 
//		if(start >= N) return 0;
		if(cache[start] != -1) return cache[start];
		
//		int cnt = 1;
		cache[start] = 1;
		for(int next=start + 1; next<N; next++) {
			if(arr[start] < arr[next])
				cache[start] = cnt = Math.max(cnt,  calculateLis(next) + 1);
		}
		return cache[start];
	}
	
}

 

시작위치 고정을 통해 외부 반복문 삭제합니다.

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 int[] arr;
	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());
			arr = new  int[N];
			st = new StringTokenizer(br.readLine());
			cache = new int[N + 1];
			answer = 0;
			Arrays.fill(cache, -1);
			for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());
			answer = calculateLisWithFixingStartPoing(-1) - 1;
			
			System.out.println(answer);
		}
	}
	
	//arr[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환합니다.
	public static int calculateLisWithFixingStartPoing(int start) {
//		기저사례 0 : 범위를 벗어날경우 중단--> 애초에 for문에서 N이상으로 호출 못하도록 합니다. 
		if(cache[start + 1] != -1) return cache[start + 1];
		
		//항상 arr[start]는 있기 때문에 길이는 최하 1
		cache[start + 1] = 1;
		for(int next=start + 1; next<N; next++) {
			if(start == -1 || arr[start] < arr[next])
				cache[start + 1] = Math.max(cache[start + 1],  calculateLisWithFixingStartPoing(next) + 1);
		}
		return cache[start + 1];
	}
	
}

 

시작위치 고정 + 캐싱 코드2 입니다.

사실 불필요한 코드가 존재합니다.

if(start == N -1) { return 1; } 코드입니다.

이유는, 아래 하단에 보면 ret = 1 로써 lis(start)는 S[start]에서 시작하는 부분 증가 수열 중 최대의 길이를 반환하기에 항상 기본적으로 1개를 반환함을 알 수 있습니다. 애초에 next < N으로 처리되어있기에 범위를 나갈 일도 존재하지 않고요. 그렇기에, 기저사례는 필요하지 않습니다. 

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[] arr, 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());
			arr = new int[N];
			cache = new int[N + 1];
			Arrays.fill(cache, -1);
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<N;i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			System.out.println(LIS(-1) - 1);
		}
		
	}
	
	public static int LIS(int start) {
		if(start == N - 1) {
			return 1;
		}
		if(cache[start + 1] != -1) return cache[start + 1];
		
		int ret = 1;
		for(int next=start + 1; next<N; next++) {
			if(start == -1 || arr[start] < arr[next]) {
				ret = Math.max(ret, LIS(next) + 1);
			}
		}
		
		return cache[start + 1] = ret;
	}
	
}