수열
10, 20, 40, 30, 70, 50, 60이 있다고 한다면
이 중에서 증가하는 부분 수열 중에 가장 긴 것을 찾아라.
라는 것이 증가하는 부분 수열이라고 하겠다.
-----n^2 방법--------
간단히 n^2으로 풀 수 있는 소스를 설명하자면,
(이 부분도 간단히 생각해내기 어려웠다. 동적계획법으로 푸는 n^2 이다)
정말 간단하고 쉬운 방법은 n! 완전탐색이겠다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <iostream> using namespace std; int arr[7] = { 10, 20, 40, 30, 70, 50, 60 }; int dy[8]; int n = 7; int main(){ for (int i = 1; i <= n; i++){ for (int j = 0; j < i; j++){ if (arr[j] < arr[i] && dy[i] < dy[j] + 1){ dy[i] = dy[j] + 1; } } } sort(dy, dy + n); // 중요 cout << dy[n - 1] << endl; return 0; } | cs |
10, 20, 40, 30, 70, 50, 60기준이 되는 i값을 빨간색,
그 앞의 값들 j값들을 주황색으로 표현해서 설명하자면,
(1) i = 1 일 때
10, 20, 40, 30, 70, 50, 60
=> dy[7] = {0, 1, 0, 0, 0, 0, 0};
(2) i = 2일 때
10, 20, 40, 30, 70, 50, 60
=> dy[7] = {0, 1, 2, 0, 0, 0, 0};
(3) i = 3일 때
10, 20, 40, 30, 70, 50, 60
=> dy[7] = {0, 1, 2, 2, 0, 0, 0};
(4) i = 4일 때
10, 20, 40, 30, 70, 50, 60
=> dy[7] = {0, 1, 2, 2, 3, 0, 0};
(보충설명) 70이 가지는 증가하는 부분 수열 10, 20, 40, 70이다.
.......
써보면서 알게 되었는데, 최대 증가하는 부분 수열은 연속된 것을 고려하지 않는 듯 하다.
연속 된 것을 찾기 위한 알고리즘은 아닌 듯 하다.
20보다 작은 인덱스들을 처음부터 돌아다니면서
20보다 작고 (arr[i] > arr[j]) ,현재 자신이 가지고 있는 증가수열의 개수보다 크면(dy[i] < dy[j] + 1)
갱신
.....
Sort(정렬)를 반드시 해야 한다.
대충 감이 올지 모르겠다. 나도 글을 써보니까 이해가 될 듯 하다.
-----n*logn 방법--------
1)Lower Bound 방법
Lower Bound란 허용되는 하한값을 가진다는 것을 말한다.
결국 입력 되는 값들을 고대로 인덱스로 가지면서 연산을 해주면 된다는 것이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include <iostream> using namespace std; int arr[5] = {5, 2, 4, 1, 3}; int dy[110000]; int n = 5; int main(){ for (int i = 0; i < n; i++){ dy[arr[i]] = dy[arr[i] - 1] + 1; } for (int i = 0; i < 5; i++){ cout << dy[arr[i]] << " "; } cout << endl; return 0; } | cs |
