알고리즘/공부2 [priority queue] 우선순위 큐 구조체 오름차순 정렬, custom sort priority queue의 custom sort를 찾아보게된 이유는 다익스트라 알고리즘 때문이다. 하얀색 박스를 보면 (-) 부호를 붙이는 모습을 볼 수 있다. 이는 구현의 편의를 위해 priority_queue를 사용하는데, 알고리즘 흐름상 우리는 오름차순으로 값을 얻기를 원하지만, priority queue는 자동으로 내림차순으로 출력되기 때문에(큰 값이 앞에 오기 때문에) 부호를 바꾸어가며 사용하는 것이다. 이를 보며 sort() 함수에서 세 번째 인자로 custom compare 함수를 만들어 사용하듯 priority queue도 custom sort가 가능하지 않을까 하여 찾아보았다. 결론부터 말하자면 찾아본 방법 중 여러 방법이 있지만, 그 중 두 가지 정도 방법을 사용할 것 같다. 사용자가.. 2021. 9. 29. KMP (Knuth–Morris–Pratt Algorithm) 알고리즘 이번 2학기에 들을 과목들을 살펴보다 알고리즘 교과목 강의계획서를 보니 kmp알고리즘이 있었다. 문자열 매칭을 다룰 때마다 몇 번 듣기는 했었는데 이번 기회에 제대로 공부해보고자 한다. 소스코드 #include #include #include using namespace std; vector getPi(string); vector kmp(string, string); int main() { string T, P; getline(cin, T); getline(cin, P); vector ans = kmp(T, P); cout T[i + k] 로 이동하여 비교를 시작하고, P도 k만큼 이동한 후 P[0]부터 비교를 시작하면 i 번째 인덱스에 있었을 때의 정보를 통해 T와 P가 일치한다고 알 수 있는 마지막 .. 2021. 7. 25. 이전 1 다음
