0. 최장 증가 부분 수열 LIS최장 증가 부분 수열 LIS어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있을 때, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분 수열을 추출하는 문제를 의미한다.ex) 3, 2, 6, 4, 5, 1의 배열의 LIS 해 중 하나는 2, 4, 5이다.이 문제를 부분집합으로 접근하면 시간 복잡도가 O(2^n)이므로, DP나 이진 검색을 활용하여 접근하는 것이 효율적이다.1. DP를 활용한 접근각 원소까지의 LIS 길이를 저장하는 배열인 LIS라고 할 때, LIS(i)를 이전 단계들과의 관계로 표현해보자.Case 1: LIS(i)가 a_i를 부분 수열의 마지막으로 포함하지 않는다면 → LIS(i) = LIS(i - 1)Case 2: LIS(i)가 a_i를 부분 수..

0. 트라이(Trie)트라이(Trie)는 문자열을 저장하고 호율적으로 탐색하기 위한 트리 형태의 자료구조이다. 트라이는 Retrieval Tree에서 나온 단어로 검색할 때 사용되는 자동완성 기능, 사전 검색 등 문자열 탐색에 특화되어 있다.단, 각 노드에서 자식들에 대한 배열을 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다.(메모리 복잡도에서 비효율적임)0-1. 트라이 자료구조의 노드 구조트라이의 노드는 4개의 정보를 담고 있다.key: 현재 노드의 알파벳data: 현재 노드까지의 결과 -> 완성된 문자열endOfWord: 현재 노드로 이루어진 단어가 있는지 판단하는 변수children: 자식 알파벳 노드들1. 트라이(Trie) 연산1-1. 삽입첫번째 문자가 trie head의 자식 노드에 있는..

0. 0/1 Knapsack배낭에 물건을 쪼개지 않고 담는 문제를 0/1 Knapsack이라고 한다.이 문제를 부분집합으로 풀게 되면 시간 복잡도가 O(2^n)이므로, DP로 접근하는 것이 효율적인 문제가 된다.1. 0/1 Knapsack 정의W = 배낭의 용량(v_i, w_i) = (물건의 가치, 물건의 무게)K[i, w] = 물건 i까지 고려했을 때, 배낭의 용량이 w일 때의 최대 가치 1-1. K[i, w] 수식 정의1-2. i번째 물건을 고려할 때1-3. 의사 코드배낭의 용량 Wn개의 물건과 각 물건 i의 무게 w_i와 가치 v_i, (단, i = 1, 2, ..., n)K[n, W]For i in 0 -> n : K[i, 0] W : K[0, w] n For w in 1 -> W If..

0. 메모이제이션(memoization)메모이제이션(memoization)이전에 계산한 값을 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다.동적 계획법의 핵심이 된다. 순수함수만 메모이제이션이 가능하다.순수함수란?1. 함수의 실행이 부수효과를 일으키지 않는 함수2. 동일한 input에 대해 동일한 output을 반환하는 함수3. 매개변수 이외에 함수 외부의 것들을 사용하지 않는 함수 메모이제이션은 추가적인 메모리 공간이 필요하다.추가로 재귀 함수 호출로 인한 시스템 호출 스택을 사용하게 됨에 따라 실행 속도 저하 또는 오버 플로우가 발생할 수 있다.0-1. 예시가장 일반적인 피보나치 수열 알고리즘 코드이다.fibo(n) { if (n  피보나치 수열 알고리즘에 메..