https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 알고리즘은 이진탐색으로 문제를 풀어야 시간초과가 걸리지않는 문제이다. 목표는 공유기를 설치한 집들 중 가장 가까운 집들의 거리의 최대값을 구하는 문제이다. 우선 가볍게 생각해보자 x좌표가 1인 집에서 간격이 5인 집의 x좌표는 몇일까? 당연히 6이다. 이 당연한 논리를 가지고 문제를 풀어볼 것이다. 간격을 이진탐색으로 선택하여 값의 조건을 ..

보이어･무어 알고리즘(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 알고리즘 원리를 알아보겠다. 우리가 기존에 아는 완전 탐색법(브루트 포스법)으로 문자열 찾을 때는 문자를 일일이 비교를 해가면서 찾았다. 책의 한 페이지에서 문자열을 찾는다고 하면 우린 책을 텍스트라하며 찾고자하는 문자열..

백준100솔을 달성했다. 알고리즘을 공부하다보니 달성하게되었는데 골드까지 무난히 찍고싶다! 현재 1월 9일부터 현재까지 알고리즘 스터디 그룹에 참여해서 학습중이다.