[백준] (11053번) 가장 긴 증가하는 부분 수열

문제 (11053번) 가장 긴 증가하는 부분 수열

링크 : https://www.acmicpc.net/problem/11053

사용 언어 : JAVA

---

---

내 생각

이 문제는 종만북에서 본 문제라서 어렵지 않게 풀 줄 알았는데 본지 너무 오래되어서 다 까먹고 책이랑 비교하며 풀 수 있었다.그런데 최근에 다른 백준 문제를 풀다가 다른 방법이 있다는 것을 알았다.(후에 포스팅 올릴 것...) 사실 둘이 탐색 방향만 다를 뿐 같은 아이디어라 해도 무방하다.

 

먼저 종만북의 알고리즘이다.

종만북 알고리즘

S[0...n-1]을 차례로 탐색하며 S[start]보다 큰 S[next]를 찾고, 그 next에서 시작하는 lis의 길이에 1을 더하는 것이다. 재귀함수를 호출하며 메모이제이션을 적용하면 더 빠른 시간에 답을 찾을 수 있다.

이때 메모이제이션의 특징은, cache[i] = S[i]~S[n-1] 범위에서 S[i]로 시작하는 가장 긴 lis의 길이 라는 것이다.

그리고 위와 같은 방식은 함수를 처음 호출할 때에도 for문을 통해 start 지점을 일일이 지정해줘야 하는데, 이를 다르게 생각해 S[-1]=-999 에서부터 시작한다고 보면 S[-1]보다 큰 next는 [0, n) 이므로 lis(-1)로 간단하게 전체 for문을 대체할 수 있다. 아래에 이 방식으로 작성된 코드가 있다.

 

다음은 두번째 알고리즘이다.

쉽게 보면 위처럼 S[end]보다 작은 S[last]를 찾고, 그 last를 마지막 원소로 가지는 최대 lis의 길이에 1을 더하는 것이다.

이때 메모이제이션의 특징은, cache[i] = S[0]~S[i] 범위에서 S[i]로 끝나는 가장 긴 lis의 길이 라는 것이다.

 

이렇게 보면 오잉?? 이 두가지는 완전 똑같은 알고리즘이잖아? 싶을 것이다. 사실 맞다. cache가 가지는 의미에 차이가 있을 뿐이다. 근데 난 이걸 생각 못해서 고생했으므로.. 적어두고 싶었다.

그리고 두번째 알고리즘은 recursion dp 말고 iteration dp로도 사용할 수 있다. 아래 코드는 iteration 방식으로 작성되었다.

 

최종 코드

// 첫번째 알고리즘

int lis(int start){
  if(start+1>=S.length) return 0;
  if (cache[start+1]!=-1)   return cache[start+1];
  int ret = 1;
  for(int next=start+1; next<S.length; next++){
    if((start==-1)||S[start]<S[next])
      ret = Math.max(ret, lis(next)+1);
  }
  return cache[start+1]=ret;
}

// 두번째 알고리즘

int lis(int N, int S[], int cache[]){
  for(int i=1; i<N; i++){
      for(int j=0; j<i; j++){
        if(S[j]<S[i]){
          cache[i] = Math.max(cache[i], cache[j]+1);
        }
      }
    }
  return cache[N-1];
}

---