투 포인터 알고리즘은 배열에서 두 개의 포인터를 사용하여 특정 목표를 달성하기 위한 기법입니다. 일반적으로 정렬된 배열에서 특정 조건을 충족하는 요소를 찾거나 연속된 서브 배열의 합과 같은 문제를 해결할 때 사용됩니다. 투 포인터 알고리즘의 전제와 조건 배열은 정렬되어 있어야 함: 투 포인터 알고리즘이 작동하려면 배열이 정렬되어 있어야 합니다. 포인터가 이동하는 방식 때문에 정렬되지 않은 배열에서는 올바른 답을 찾지 못할 수 있습니다. 두 개의 포인터를 사용함: 하나의 포인터는 배열의 시작점에, 다른 하나는 끝점에 위치시킵니다. 이 두 포인터는 문제에 따라 서로를 향해 움직이거나 같은 방향으로 움직일 수 있습니다. 투 포인터 알고리즘 설명 포인터 초기화: 두 개의 포인터를 배열의 시작과 끝에 위치시킵니다..

보이어･무어 알고리즘(Boyer-Moor algorithm) 이 알고리즘은 이전글에서 설명한 KMP보다 효율적이며 실제 프로그램에서 많이 사용되는 알고리즘이다. 패턴의 오른쪽부터 텍스트와 비교하기에 모든 텍스트와 비교할 필요없이 탐색이 가능하다. 패턴과 텍스트를 비교할 때 텍스트의 가장 뒷부분부터 비교한다. 비교해서 같지않은 문자열의 위치에 따라 패턴을 n만큼 이동시킨다. KMP와 동일하게 LPS를 만들어줘서 패턴의 반복되는 값을 찾아 문자열 검색을 효율적으로 이뤄지게한다. LPS 표의 각 자리의 값은 텍스트 인덱스의 위치마다 바뀐다. 어떤 기준으로 바뀔까? LPS = 패턴의 길이 값을 가진 27개의 정수를 담고 있는 리스트(대문자 기준이기에 소문자는 정수 개수 추가 필요) LSP[알파벳 인덱스] = 패..

KMP 알고리즘(Knuth-Morris-Pratt Algorithm) 이 알고리즘을 이해를 쉽게 하기 위해서는 KMP알고리즘에서의 접두사와 접미사를 알고가야한다. 예시 하나로 설명하고 넘어가겠다. ex) apple이라는 문자열이 주어졌다. 1, a 2, ap 3, app 4, appl 5, apple 총 5개의 접두사를 갖는다. 1, e 2, le 3, ple 4, pple 5, apple 총 5개의 접미사를 갖는다. 위의 예시로 접두사, 접미사 설명은 충분할 것으로 본다. 이제 KMP 알고리즘 원리를 알아보겠다. 우리가 기존에 아는 완전 탐색법(브루트 포스법)으로 문자열 찾을 때는 문자를 일일이 비교를 해가면서 찾았다. 책의 한 페이지에서 문자열을 찾는다고 하면 우린 책을 텍스트라하며 찾고자하는 문자열..