[DP] LIS (최장 공통 부분 수열)
LIS (Longest Increasing Subsequence) 수열 안에 있는 증가 하는 부분 수열 중 가장 긴 것을 찾는 문제 Idea1 완전탐색입니다. 1) 수열을 처음부터 하나씩 증가하면서 (a[]의 모든 원소마다), 각 경우마다는 첫번째 수 a[i]를 정하고, 인덱스를 1씩 늘려가면서(a[i+1] ... ) 첫번째 수보다 큰 숫자들을 컨테이너(sub_a[])에 담습니다. 2) sub_a를 1)번 과정을 되풀이하는 재귀함수를 구현합니다. a[] = {3, 2, 1, 7, 5, 4, 2, 6} 첫번째 원소 3을 기준으로, 그 다음 가능한 7 5 4 6 중 다시 재귀적으로 LIS를 뽑습니다. #include #include using namespace std; /* LIS의 길이를 반환 */ int..
2019. 9. 6.
[정렬] sort
버블정렬, 선택정렬, 삽입정렬, 쉘정렬, 병합정렬, 퀵정렬, 힙정렬, 계수정렬, 기수정렬까지... 많은 정렬들을 직접 구현해봤지만, 결국 실전에서는 이것들을 일일이 구현할 순 없다. 물론, 다 외워서 할 수 있으면 정말 좋긴 할 것이다. 실전에서 만약 정렬이 필요하다면, #include sort(v.begin(), v.end()); stable_sort(v.begin(), v.end()); STL함수를 써야할 것이다. sort 여기 있는 sort함수는 introsort라는 하이브리드 기법을 썼다고 한다. 불안정한 quick sort가 아니라서 다행이다. 시간복잡도 O(NlogN)을 보장한다. stable_sort 또한 중복되는 key에서 각 key가 가진 다른 값도 정렬하고 싶을 때는 stable_sor..
2019. 9. 2.
