devbelly

문제 www.acmicpc.net/problem/20191 알고리즘 이분탐색 풀이 문자열 S와 T가 주어집니다. $T^n$을 문자열 T를 n회 반복한 문자열이라고 정의할 때, n번 반복하여 줄임말 S를 만들기 위한 최소 n을 구하는 문제입니다. 줄임말을 만들 때, 순서를 유지한다는 점에서 투포인터 전략을 떠올릴 수 있습니다. 각각을 $pt, ps$라고 해봅시다. 각 포인터가 가리키는 문자열이 일치할 때는 둘 다 1씩 더해서 다음 문자를 확인하고 다르다면 $pt$만을 증가시키고 문자열 T가 끝에 다다랐다면 다시 $pt$를 0으로 초기화 해줍니다. 이렇게 할 경우 다음과 같은 예시에서 비효율적으로 작동하게 됩니다. zzzz aaaz 즉 z가 나타나는 위치를 찾기 위해 일일이 T문자열을 탐색하는 대신, 다른 ..

문제 www.acmicpc.net/problem/18877 알고리즘 binary search 풀이 COWVID-19의 영향으로 사회적 거리두기를 실천하는 소들의 수가 주어집니다. 목초지의 범위가 주어지고 해당 범위안에 소를 배치하되, 가장 가까운 소의 거리가 최대가 되도록 하는 문제입니다. 소들을 임의의 거리 $d$로 배치할 수 있다면, $d$이하의 거리로 소를 배치할 수 있음이 자명합니다. 이분탐색으로 범위를 좁혀나갈 수 있다는 뜻과 동치입니다. $solve$함수는 거리$d$로 $N$마리의 소를 배치할 수 있는가를 리턴하는 함수입니다. $cur$은 가장 최근에 소를 배치한 지역을 의미합니다. 맨 처음에는 당연히 소를 배치하지 않았으므로 가장 작은 수로 초기화를 합니다. 다음의 $cur$이 될 수 있는 ..

문제 www.acmicpc.net/problem/1321 알고리즘 세그먼트트리 풀이 부대원의 숫자가 계속해서 바뀔 때, 몇번째 병사가 어디 부대에 들어있는지 묻는 문제입니다. 누적배열을 만들어 나이브하게 해결해봅시다. 부대원이 변경될때마다 누적배열을 변경하는데에 최대 $O(N)$의 복잡도를 요구하게됩니다. 업데이트를 더 빠르게 할 수 있는 세그먼트 트리를 요구합니다. 세그먼트 트리를 사용하면 업데이트와 쿼리가 $O(logN)$에 해결가능합니다. 남은 문제는 누적배열에서 몇번째에 해당하는$K$가 어디에 속한지 찾는 문제입니다. 누적배열은 오름차순의 형태를 띠고 있고 이는 이분탐색을 통해 접근할 수 있다는 의미입니다. 펜윅트리에서 쿼리는 누적합을 리턴하므로 펜윅트리 + 이분탐색을 통해 문제를 해결할 수 있습..

문제 https://www.acmicpc.net/problem/9426 알고리즘 세그먼트 트리 풀이 $N$초동안 온도를 기록하는데 최근 $K$초의 중앙값들을 모두 더하는 것을 요구하는 문제입니다. 이 문제의 경우는 이전의 값을 삭제하는 연산 없이 계속 추가한 후 중앙값만 처리하면 되므로 최대 힙, 최소 힙 두 개로 $O(NlogN)$에 해결 가능했으나, 가장 최근$K$초의 중앙값만을 계속 구해야 하므로 최근 K초를 제외한 온도를 삭제할 수 있는 자료구조인 세그먼트 트리를 활용하겠습니다. 문제에서 요구하는 핵심쿼리는 중앙값 처리입니다. 트리에서의 인덱스는 온도를 의미합니다. 온도의 개수를 누적시킨다면, 인덱스에 따라 값들이 오름차순으로 정렬되어 있으므로, 이분 탐색을 통해 중앙값을 빠르게 처리할 수 있습니..

문제 https://www.acmicpc.net/problem/5009 알고리즘 2-SAT, 이분탐색 풀이 우리가 결정해야 할 것은 아이들의 호감리스트를 반영한 아이들의 반 배정입니다. 언뜻 보면 선생님이 3명이여서 아이들이 결정해야할 선생님이 세 사람 같아 보이지만 실제론 두 사람입니다. 이유는 작년에 담당했던 선생님은 선택사항이 아니기 때문입니다. 문제 조건중 "반에 속하는 모든 학생은 학생들이 좋아하는 순서에서 상위 T위 안에 있어야 한다."는 달리 말해서 T위를 초과하는 학생과는 다른 반이 되어야 함을 의미합니다. 다른 반으로 배정하기 위해선 두 학생의 이전 선생님이 누구인지 알아야 하며, 이에 따라 반배정을 진행해주면 됩니다. 각 선생님 번호가 0 , 1 , 2라고 할 때, T(x)는 이전 선생..

문제 https://www.acmicpc.net/problem/3033 알고리즘 라빈 카프 풀이 https://www.acmicpc.net/problem/1701 길이 제한을 제외하고, 위 문제와 동일합니다. 우리는 1701번 문제를 $O(N^2)$에 해결했지만, 이 문제는 길이 제한이 20만 이므로 다른 전략을 택하도록 합시다. 만약 길이$m$인 문자열이 두 번 이상 등장한다고 해봅시다. 그러면 $m$보다 작은 $n$은 두 번 이상 등장함을 알 수 있을까요? 네. 이는 너무나도 확실합니다. 예를 들어 문자열 $aabaa$에서 부분 문자열 $aa$는 두번 등장함을 알 수 있고, 이보다 짧은$a$는 $aa$가 등장한 인덱스를 제외하고도 더 등장할 수가 있죠. 그렇다면 길이$m$보다 긴 길이$k$는 몇 번 ..