CS/Algorithm

1. 개념 소개KMP 알고리즘은 본문(Text) S 안에서 패턴(P) 을 찾는 문자열 검색 알고리즘이다.틀렸을 때 무식하게 처음부터 다시 비교하지 않고, 이미 비교해서 얻은 정보(LPS) 로 패턴을 점프한다.그래서 최악의 경우에도 O(N + M) (N=본문 길이, M=패턴 길이)필자는 이해하는데 무려 3일이라는 시간이 걸렸다......비교 요약완전탐색(브루트포스)은 “한 칸 밀고 처음부터 다시”KMP는 “겹친 만큼은 건너뛰고 다음 비교로”2. 주요 용어용어의미LPS, 실패함수, 실패 배열KMP 알고리즘에서 매칭 실패 시, 패턴을 얼마나 건너뛸 수 있는지를 알려주는 역할접두사문자열의 시작에서부터 연속된 부분 문자열. 예: "ABC"의 접두사는 "", "A", "AB", "ABC"접미사문자열의 끝에서부터 연..

1. 분할 정복 - 기본편 그대로 해결할 수 없는 문제를 "작은" 문제로 분할하여 문제를 해결하는 방법. 대표적으로 "병합정렬" 분할 정복에는 3가지 용어로 정리 할 수 있다. Divide 문제를 더 작은 단위로 가능할 때 까지 나눔 Conquer 각 하위 문제를 재귀로 해결, 탈출조건을 설정해 나눌 수 없는 단계에서는 문제를 해결 Combine (merge) conquer가 된 문제들을 합쳐서 점차적으로 원래의 문제의 답을 찾아 나감 쉬운 예시로 1 ~ 8 까지의 합을 생각해보자 1 2 3 4 5 6 7 8 # 1~8의 합 divide (1회) # 1~4의 합, 5~8의 합 1 2 3 4 || 5 6 7 8 divide (2회) # 1~2의 합, 3~4의 합, 5~6의 합, 7~8의 합 1 2 || 3..