알고리즘5 [BOJ] 1806번: 부분합 (C++) Problem 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net Solution 구간 합의 시작을 가리키는 start 포인터와 끝을 가리키는 end 포인터를 두고 조건에 맞게 end 포인터와 start 포인터를 증가시키면 된다. 처음부터 숫자를 하나씩 더해가면서 합이 S 이상이 되면 start 포인터를 1 증가시키고 합을 갱신한다. 갱신된 합이 S보다 작으면 end 포인터를 합이 S 이상이 될 때까지 증가시킨다. 이 과정을 반복하는 동안 end - start의 값을 계산하여 가장 짧은 부분합의 길.. 2022. 1. 4. [BOJ] 3176번: 도로 네트워크 (C++) Problem 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 부끄럽지만 문제를 이해하는데 시간이 조금 걸렸다. 필자처럼 문제를 이해하는데 헤매는 사람이 있을 수도 있으니 문제에 대해 정리해보겠다. 예제 입력 1을 시각화하면 다음과 같다. 이때 도시 1과 도시 2를 연결하는 경로는 2-3-1로 길이가 100인 도로와 길이가 50인 도로로 이루어져 있다. 따라서 도시 1과 도시 2를 연결하는 경로에서 가장 짧은 도로의 길이는 50, 가장 긴 도로의 길이는 100이다. .. 2021. 12. 18. [BOJ] 5052번: 전화번호 목록 (C++) Problem Solution 접두사를 통해 해결할 수 있는 문제이므로 트라이를 이용한다. 트라이를 통해 일관성 없는 전화번호 목록을 어떻게 찾을 수 있을까? 트라이에서 두 문자열이 같은 접두사를 공유하고 있으면 같은 노드를 공유하고 있다. 예를 들어 두 문자열 913, 9134가 트라이에 입력되었을 때, 두 문자열은 9, 91, 913 노드를 공유하고 있다. 이때 공유하는 노드 중에 문자열의 끝을 나타내는 노드가 있으면 일관성이 없는 전화번호 목록이라고 볼 수 있다. 이 예제에서는 913 노드가 문자열의 끝을 나타내는 노드이므로 913, 9134는 일관성이 없는 전화번호 목록이다. 1. 모든 전화번호를 트라이에 넣는다. 2. 각각의 전화번호를 트라이에서 탐색하면서 일관성 여부를 확인한다. 3. 마지막 .. 2021. 12. 16. [BOJ] 1701번: Cubeditor(C++) Problem Solution 1. 문자열의 길이를 N, 지금까지 나온 부분문자열 중 가장 긴 문자열의 길이를 M이라고 하자. 2. 문자열의 인덱스 i에서 시작하는 길이가 (M+1)인 문자열을 패턴, 인덱스 (i+1)부터 (N-1)인 문자열을 텍스트로 설정하여 KMP search를 진행한다. 3. 텍스트에서 매칭되는 문자열을 찾으면 패턴을 인덱스 i에서 시작하는 길이가 (M+2)인 문자열로 두고 진행한다. 4. 찾지 못한다면 인덱스를 1 증가시켜 패턴이 매칭되는지 확인한다 문자열 : abcab 인덱스 = 0, M = 0 텍스트 = bcab 패턴 = a 매칭 결과 : O 인덱스 = 0, M = 1 텍스트 = bcab 패턴 = ab 매칭 결과 : O 인덱스 = 0, M = 2 텍스트 = bcab 패턴 = a.. 2021. 12. 14. 이전 1 2 다음
