[도서리뷰] 알고리즘 문제 해결 전략
언젠가 내가 도서리뷰라는 카테고리를 만들고, '야, 이건 진짜 잘 썼다'싶은 책들을 리뷰하는 때가오면 이 책은 꼭 리뷰를 쓰고싶었다. 그래서 쓰는 오늘의 리뷰, 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략. 사실 이 책은 이미 너무 유명하다. 굳이 리뷰해야 싶을까? 정도로 이 쪽 업계에선 정평이 난 책이기도하고 알고리즘을 공부하는 사람들...특히나 최근 개발자 취업에 필수 코스라고 불리는 코딩테스트를 준비하는 이들이라면 누구나 다들 한 번은 이 책의 명성을 들어봤을 것이다. 내가 이 책을 처음 접한 건 한창 알고리즘에 빠져살던 대학교 4학년... 그러니까, 지금의 코딩테스트 광풍이 몰아치기도 이전이었던 2013년이었다. (라떼는 말이야, 썰을 풀자면...내가 이 책을 공부할때만해도 윗 사진의 가장..
[문자열] KMP 알고리즘
알고리즘 카테고리의 첫 포스팅은, KMP 알고리즘이다. Knuth, Morris, Pratt 이라는 세 사람의 첫 글자를 따선 만든 알고리즘인데, 쉽게 정의하자면 서로 다른 문자열을 비교하는 알고리즘이라고 보면 된다. 예를 들어, 'aaaabbccaab' 라는 문자열이 있을때, 'aab'라는 문자열이 몇번째 인덱스에 있는지 찾고자한다면 어떻게 찾아야 할까? 당장 떠오르는 방법은 아마도 'aaaabbccaab'의 첫번째글자와 'aab'의 첫 번째 글자를 비교해서 동일하면, 각각 두번째 글자를 비교하고 또 동일하면 세번째 글자를 비교하고. 만약 세번째에서 동일하지 않다면, 비교의 시작점이었던 'aaaabbccaab'의 두번째 글자로 돌아와서, 다시 'aab'의 첫 번째 글자와 비교를 할 것이다. 이 방법의 ..