알고리즘

PS에 편한 C++ 문법

나는 C++로 PS를 하는데, 참고했던 책도 그렇게 최신 책은 아니고 컴파일 환경도 C++14였어서 이런저런 화려한 문법들을 쓰지 않고 PS를 진행했다. 그런데, 다른 사람들의 코드를 읽어 보니 각종 편리한 문법들을 많이 사용하고 있는 것 같아서 나름 사람들 어깨 너머로 배운 내용들이나 편법(?)등을 정리해 놓고자 한다. 다른 사람들의 PS 코드야 예전부터 가끔 읽었지만, 그때는 딱히 내가 저 사람들이 쓰는 문법을 따라 할 필요가 없었다고 느꼈다. 그런데 언젠가부터 이런 마인드를 바꾸기로 결심했는데, 바로 취업을 위한 코딩 테스트를 준비할 때였다. 평소에 PS를 할 때에는 한 문제에 수십 분부터 몇 시간, 며칠을 매달리든 내 자유였지만 코딩 테스트는 그 시간이 정해져 있기 때문에 효율적인 알고리즘을 빠르..

최단 거리 알고리즘의 이해

최단 거리 알고리즘에 대해 정리해 본다. 책을 참고했음을 밝힌다. 최단 거리 알고리즘은 말 그대로 시작 지점에서 도착 지점까지 이동하는 경로 중 가장 짧은 경로의 거리를 구하는 알고리즘이다. 장소와 길은 그래프로 나타내기 때문에, 그래프 이론과 밀접한 관련이 있다. 1. 다익스트라 알고리즘 (Dijkstra's algorithm) 가장 스탠다드한 최단 거리 알고리즘이다. 시작 정점을 지정하면 해당 정점에서 출발해서 다른 정점으로 도착할 때의 최단 거리를 알 수 있다. 길찾기 알고리즘을 적용하는 가장 흔한 예는 가중치(weight)가 있는 weighted graph이므로, 나중에 발견된 정점이 최단 거리일 수 있다. 즉, 단순한 BFS로는 최단 거리를 찾지 못하는 경우가 수없이 많다는 것이다. 다르게 말하..

KMP 알고리즘

KMP 알고리즘에 대해 공부하다가 헷갈리는 것들이 있어 자세히 정리했다. 책을 참고했음을 밝힌다. 먼저, KMP 알고리즘이란 문자열 검색을 보다 효율적으로 실행하는 알고리즘으로, 전체 문자열의 모든 부분에서 문자열 비교를 행하지 않으면서 대상 문자열을 빠르게 검색해 낸다. 전체 문자열이 짧으면 몰라도, 수천 수만 줄로 이루어진 문서에서 단어를 검색하는 작업은 모든 글자에서 하나하나 단어를 확인하기에는 무리가 있을 수 있다. 그래서 우리는 naive한 방법보다 훨씬 효율적인 KMP 알고리즘을 사용한다. 가장 간단한 알고리즘부터 떠올려 보자 먼저, 우리가 문자열 검색을 수행하고자 하는 전체 문자열을 '짚더미(haystack)', 그리고 찾아내고자 하는 대상 문자열을 '바늘(needle)'이라고 칭하자. 짚더..