알고리즘) 백준 Baekjoon 11055번 가장 긴 증가하는 부분수열
이 문자는 최대 증가 부분 수열(LIS, Longest Increasing Sub-sequence)로 유명한 dynamic programming 문제 중 하나입니다.
저는 재귀 함수를 이용해서 문제를 해결했습니다. 재귀함수 lis(n)은 모든 증가 부분 수열을 만든 후 그 중 가장 긴 길이를 반환합니다.
lis(n)가 A[i]를 골랐을 때, A[i+1..]의 숫자 중에 A[i]보다 큰 숫자들만 고른 부분 수열을 만들고 이 부분 수열에 대한 lis를 재귀 호출을 이용해서 구합니다.
와 같이 for문을 수행하게 됩니다. (첫 재귀함수에서 ret가 110으로 가장 크기 때문에 값에 대한 변화는 없습니다.)
위와 같은 방식으로 start = 1, 2, 3, .. 일때를 모두 탐색하면 가장 긴 길이의 부분 수열을 알아 낼 수 있습니다.
코드로 표현 하면 다음과 같습니다.
저는 재귀 함수를 이용해서 문제를 해결했습니다. 재귀함수 lis(n)은 모든 증가 부분 수열을 만든 후 그 중 가장 긴 길이를 반환합니다.
lis(n)가 A[i]를 골랐을 때, A[i+1..]의 숫자 중에 A[i]보다 큰 숫자들만 고른 부분 수열을 만들고 이 부분 수열에 대한 lis를 재귀 호출을 이용해서 구합니다.
start = 0일 때,
10, 20, 10, 30, 20, 50
10, 20, 10, 30, 20, 50
10, 20, 10, 30, 20, 50
10, 20, 10, 30, 20, 50
와 같이 for문을 수행하게 됩니다. (첫 재귀함수에서 ret가 110으로 가장 크기 때문에 값에 대한 변화는 없습니다.)
위와 같은 방식으로 start = 1, 2, 3, .. 일때를 모두 탐색하면 가장 긴 길이의 부분 수열을 알아 낼 수 있습니다.
코드로 표현 하면 다음과 같습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | int lis(int start) { int& ret = cache[start]; if (ret != -1) return ret; ret = arr[start]; for (int next = start + 1; next < n; next++) { if (arr[start] < arr[next]) ret = max(ret, lis(next) + arr[start]); } return ret; } int main() { cin >> n; for (int i = 0; i < n; i++){ cin >> arr[i]; } for (int i = 0; i < 1001; i++){ cache[i] = -1; } int maxLen = 0; for (int i = 0; i < n; i++) maxLen = max(maxLen, lis(i)); cout << maxLen << endl; } | cs |
댓글 없음: