누적 합(Prefix sum) 계산 양을 줄여서 시간적으로 많은 이득을 볼 수 있는 알고리즘이다. 1. 기본 원리 1) 1차원 배열 1차원 배열에서 i번째부터 j번째 인덱스까지 k를 더한 것을 기록하려면, 새로운 배열의 i번째 인덱스에 k를 더하고 j+1번째 인덱스에 k를 빼면 된다. 새로운 배열의 크기는 기존 배열 크기보다 하나 이상 크게 만든다. 예를 들어 크기가 5인 배열에서 0번째부터 2번째 인덱스까지 N을 빼고 싶다면 다음과 같이 누적 합 배열을 만든다. { -N, 0, 0, N, 0, 0 } 위 새로운 배열을 0번째부터 마지막 인덱스까지 누적 합을 계산하게 되면 다음과 같다. 추가로 1번째부터 2번째 인덱스까지 M을 더하고 싶다면 누적 합 배열에 값을 추가한다. { -N, -M, 0, N, M..

중간에서 만나기(Meet In The Middle) 알고리즘 문제를 풀 때 완전 탐색으로 탐색하는 경우, 탐색의 범위가 커질수록 경우의 수와 연산량이 기하급수적으로 늘어나는 것을 볼 수가 있다. 이때 중간에서 만나기 방식을 사용하면, 시간 복잡도를 제곱근만큼 줄일 수 있다. 중간에서 만나기 방식은 앞쪽과 뒤쪽에서 절반씩 접근하여 중간에서 탐색한 결과가 만나게 하는 탐색 기술을 의미한다. 즉, 중간에서 만난 연산의 결과를 합쳐 전체 결과를 뽑아내는 것이다. 문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사..

문자열 1. KMP 알고리즘 문자열 검색을 빠르게 구하기 위한 알고리즘이다. 1) 기본 원리 접두사(prefix)와 접미사(suffix)를 이용해 pi[i] 배열을 구한 뒤 활용한다. pi[i] 배열은 0~i까지의 부분 문자열에서 prefix=suffix가 될 수 있는 부분 문자열 중 가장 긴 것의 길이이다. 이때, prefix가 0~i까지의 부분 문자열과 같으면 안 된다. 예를 들어 문자열 ABAABAB로 pi[i] 배열을 구해보자. i 부분 문자열 (0~i) pi[i] 0 A 0 1 AB 0 2 ABA 1 3 ABAA 1 4 ABAAB 2 5 ABAABA 3 6 ABAABAB 2 그렇다면 이 pi[i] 배열을 어떻게 활용하여 문자열 검색을 효율적으로 할 것인가? 문자열 ABCDABCDABEE에서 문자..

네트워크 유량(Network Flow) 그래프 개념 중 하나로 네트워크 유량을 이해하기 위해선 먼저 새로운 용어와 유량 그래프의 특징부터 알아야 한다. 유량 그래프는 보통 방향 그래프인 경우가 많다. 그래프의 간선 거리, 시간이나 가중치 대신 용량(Capacity)이라 한다. 두 정점 u, v를 있는 간선 (u, v)가 있을 때, u에서 v로 간선의 용량 이하만큼의 유량(flow)을 흘려보낼 수 있다. 그래프 내 서로 다른 소스(S, Source) 정점과 싱크(T, Sink) 정점이 있는데, 소스 정점은 유량을 발생시킨다. 소스 정점 외 정점들은 자신이 받은 유량만큼만 다시 흘려보낸다. 각 간선에 흐르는 유량은 그 간선의 용량을 넘을 수 없다. 간선 (u, v)로 유량이 흐르고 있다면 역방향인 간선(v,..

희소 테이블(Sparse Table) 배열이 정적이어야 한다. 즉, 배열 내용이 수정되면 안 된다. 배열의 아이디어는 분할 정복과 비슷하지만 더 빠르다. 기본 원리 모든 정점의 간선이 1개인 유향 그래프가 존재할 때 어떤 정점에서 시작해 k번 이동을 하면 도착하는 점은 유일하다. 이때 k번을 일일이 매번 따라가며 도착점을 계산할 수도 있겠지만 k값이 커질수록 시간도 오래 걸릴 것이다. 만약 어떤 정점의 n번 이동했을 때 도착점, 또 그 도착점을 정점마다 다 기억하는 배열이 있다면 도착점을 매우 효율적으로 구할 수 있을 것이다. 그렇다면 이 배열은 어떻게 가져야 할까? 1칸, 2칸, 4칸, 8칸, 16칸,... 등 2진수를 이용해 2진수에 해당하는 이동 값을 모두 배열로 만든다. 그리고 이동 횟수 k를 2..

위상 정렬(Topological Sort) 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위한 알고리즘이다. 여러 개의 답이 존재할 수 있다. DAG(Directed Acyclic Graph)에만 적용이 가능하다. 스택과 큐로 구현된다. 기본 원리 진입 차수가 0인 정점을 큐에 삽입한다. 큐에서 원소를 꺼내 연결된 모든 간선을 제거 후 진입 차수가 0이 된 정점을 큐에 삽입한다. 큐가 빌 때까지 2번 과정을 반복한다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다. 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ..