체크무늬 공대생

. 등장 배경) 인터넷에서 정보들을 찾아볼 때, 한 번쯤은 Ctrl + F 단축어를 통해 특정 글자만 찾아본 경험이 있을 것이다. 그리고 이 작업은, 대부분의 경우에 아주 빠르게 완료되어 몇 개의 특정 글자가 존재하는 지 알려준다. KMP 알고리즘은 이러한 작업의 핵심이 되는 알고리즘으로서, 지금도 널리 쓰이고 있는 알고리즘이다. 아래 예시를 통해, KMP 알고리즘의 필요성을 느껴보자.아이같은아이같은아이작 에서 아이같은아이작 를 찾아보자. 대부분의 경우 아이같은아이.. 에서 멈췄을 것이다. ‘작’이 나와야 할 타이밍에 ‘아’가 나왔기 때문이다. 이렇게 매칭이 실패한 경우 두 번째 글자인 ‘이’부터 탐색을 다시 시작해야 할까? 만약 이렇게 매칭을 하면 정확한 결과는 얻을 수 있다. 브루트포스 알고리즘이기 ..

. 등장 배경) 개발하는 데에 있어서 수많은 데이터 중 원하는 값이 어디 있는 지 알아내는 건 매우 중요하다. 그리고 이것을 얼마나 빠르게 알아내는 지는 곧, 우리가 흔히 말하는 최적화와 연관되어 있다. 본 글에서는 편의상 원하는 값을 target, 데이터 리스트를 data_list 라고 표기하겠다. 이분 탐색(Binary Search)가 등장하기 전까지는, 아래 그림과 같은 순차 탐색을 진행했다.그러나 이와 같은 방식은 data_list를 처음부터 target 값이 나오기까지 하나하나 비교하기에 속도가 매우 느리다. 예를 들어 데이터의 개수 N이 100만개라고 가정한다면, 최악의 경우 100만개의 데이터들을 비교해야 한다. 그렇기에 순차 탐색보다 획기적으로 시행 시간을 단축시킬 수 있는 알고리즘의 사용..