combination, permutation 의 값만 계산하는 것은 공식을 이용하거나 dp 를 이용하거나 하면 구할 수 있다. 하지만 모든 케이스를 뽑아내야 한다면 단순 공식만으로는 안 된다. 이를 정리한 내용은 아래와 같다.https://ghqls0210.tistory.com/323 permutation, combination 구현 C++회사에서 치는 시험에 구글링이 안 되서 짬짬이 알고리즘들 개념을 다시 정리하고자 한다. 1. permutation (순열) 간단히 {0,1,2,3,4} 배열에서 5P3 을 구한다고 하면 {0,1,2} ~ {4,3,2} 까지가 계산된다. 이를ghqls0210.tistory.com
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/3G8aP/btsG4TTlb5Z/Rb43RcdiUwapGrIVxAS1b1/img.png)
KMP 알고리즘은 ctrl + F 와 같이 긴 문자열에서 특정 패턴을 찾을 때 사용되는 알고리즘이다. 단순히 하나씩 검색 시, 검색 대상 문자열 길이가 N, 검색 패턴 길이가 M일 때 O(NM) 이 소요되지만, KMP를 이용 시 O(N+M)이 소요된다. KMP 알고리즘은 다음과 같이 동작한다. - 실패 함수를 통해 패턴의 prefix와 suffix의 일치하는 최대 길이를 계산- 계산된 실패함수를 바탕으로 패턴 매칭 실패 시 suffix 위치로 이동 실패 함수 (아래에서 pi 함수)ababaabbabab 와 같은 패턴이 있을 때, prefix와 suffix의 공통 최대 길이를 구하는 함수이다. ababaabbabab의 경우, abab / aabb / abab 와 같이 prefix와 suffix의 공통 ..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/bglKUi/btsG35Ud0yw/j0XDRzzK32X8WUdSbpjd7K/img.png)
Trie 자료구조는 Tree와 유사하지만, element 개별로 트리를 구성하는 것이 아닌, 공통 prefix를 기준으로 tree를 구성한다. 대표적인 Trie 예시는 string 간의 공통 substring 검색, 검색엔진에서 검색어 유무 확인, 이더리움의 state 저장에 사용되는 merkle patricia trie 등이 있다. Trie 예시 : 알파벳 소문자로만 이루어진 경우 입력 : apple, app, banana, bbb, ccc, cat root를 기준으로 새로운 문자열 삽입 시, char 단위로 null이 아닌 곳을 따라 가다가 null 인 지점을 만나게 되면 해당 노드부터 한 글자씩 노드를 추가로 생성하면 된다. 입력된 문자열이 Trie에 존재하는 지 여부의 경우, 마찬가지로 Tr..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/HXeCC/btsG6e9SArx/cbBny3MQYqAzb4IDU6YVS0/img.png)
KD Tree : 일반적인 바이너리 트리를 k 차원으로 확장한 트리 데이터 타입이 n 차원 벡터일 때 (x1, ..., xn)x1을 기준으로 트리 구성, x2를 기준으로 트리 구성, ..., xn을 기준으로 트리 구성, x1을 기준으로 트리 구성, ... 을 반복하여 트리를 만드는 것 ex) 2차원에 대한 KD Tree 만들기input : (5, 3), (5, 4), (3, 9), (4, 6), (6, 2), (1, 1), (4, 1), (6, 7)root : (5, 3)left child : xi 차원의 값을 기준으로 작은 것, right child : xi 차원의 값을 기준으로 이상인 것 위와 같이 차원을 분리하여 각 차원에 대한 대소 비교를 통해 트리를 구성하는 것이 KD Tree KD Tree..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/bEucLj/btsGN1cl6PP/WHUGbzycdVRyToZou9WV00/img.png)
C++의 STL에는 vector와 queue 등 아주 좋은 친구들이 많다. 그 중 PS 에서 많이 쓰는 vector와 priority_queue 의 정렬 기능에 대해 정리하고자 한다. 1. vector algorithm STL 을 이용해 sort 함수로 vector를 쉽게 정렬할 수 있다. (단순 배열도 가능) sort(vec.begin(), vec.end()) 가 기본 사용법이며, vec의 처음부터 끝까지를 기본적으로 오름차순으로 정렬한다. 역순 정렬을 하고자 하면 sort(vec.rbegin(), vec.rend()) 와 같이 사용 가능하다. 하지만 이는 int, float, pair 등 기본 타입에만 적용이 된다. 따라서 operator 가 정의되지 않은 데이터 타입 (struct 로 직접 만든 데..