복습 정리 노트

백준 BOJ 2150번 : Strongly Connected Component 문제 난이도 : Platinum V 알고리즘 분류 : 강한 결합 요소 (SCC) 방향 그래프가 주어질 때, 이들을 SCC로 나누어 출력하는 문제이다. 여기서 말하는 SCC(Strongly Connected Component)란, 한 Component 내의 어떤 두 점 사이에도 이동이 가능한 요소를 말한다. (SCC를 나눌 때는 당연히 한 Component의 크기가 최대가 되도록 나누어야 한다.) 그래프를 입력받고 adj 벡터에 간선들을 저장해주는 부분은 기본적이므로 설명을 생략한다. 이제 DFS 방식으로 노드들을 탐색하며, 노드 번호를 방문하는 순서대로 오름차순으로 매긴다. (nnum 벡터에 저장) 즉, 번호를 먼저 매기는 것..

백준 BOJ 24411번 : Stamp Combinations 문제 난이도 : Silver I 알고리즘 분류 : 누적 합, 해시를 사용한 집합과 맵 길이 N인 수열에 대해, 앞의 부분합과 뒤의 부분합의 합으로 쿼리로 입력된 값을 만들 수 있는지 구하는 문제이다. 이 때 N x Q(쿼리의 수) ≤ 10^7이다. 누적 합을 사용하는 것은 확실해보이나, 누적 합을 사용하더라도 O(N^2)에 돌아간다. 따라서 시간 복잡도를 조금 더 개선할 방법을 찾아보아야 한다. v_i를 1 ~ i번째 원소의 합이라고 하자. 그러면 뒤쪽 부분의 합은 v_N - v_i이고, 앞쪽 부분은 쿼리 값이 x라고 했을 때 x - (v_N - v_i)이다. map을 활용하여 v_0 ~ v_N 값들을 모두 저장해두고 m[x - (v_N - ..

백준 BOJ 16287번 : Parcel 문제 난이도 : Platinum V 알고리즘 분류 : 중간에서 만나기 (밋 인더 미들), DP N개의 물품 중 "서로 다른" 물품 4개를 골라 그 무게의 합이 M이 되도록 하는 경우가 있는지 확인하는 문제이다. 우선 N이 5,000이므로, O(N^4) 같은 방법은 안 된다. 각 원소는 최대 20만이므로, 두 원소의 합을 배열에 저장하고, 나머지 두 원소의 합을 배열의 기록을 이용하여 비교해보는 방식을 사용해볼 수 있다. O(N^2) 시간에 두 원소의 합을 구성하는 원소의 주소를 u, w에 저장한다. 다음으로 O(N^2) 시간에 나머지 두 원소의 합이 기록된 것들 중에서 주소가 둘 다 겹치지 않는 것이 있으면, YES를 정답으로 출력해주면 되고 그러한 조합이 하나도..

백준 BOJ 6325번 : Definite Values 문제 난이도 : Silver V 알고리즘 분류 : 트리를 사용한 집합과 맵 N개의 (변수) = (변수) 꼴의 수식이 주어지고, 처음에는 a만 값이 제대로 지정되었다고 할 때, 모든 등식이 적용된 이후 값이 제대로 지정된 변수의 목록을 구하는 문제이다. set을 사용한다. a = b라는 등식에서, a가 값이 지정되지 않고 b가 지정되었다면 a는 제대로 된 값이 지정된다. (set에 insert 해준다.) 반대로 a가 값이 지정되고 b가 지정되지 않았다면 a의 값은 쓰레기 값으로 덮어진다. (set에서 erase 해준다.) 이 과정을 N번 반복한 다음 set의 모든 원소들을 출력해주면 된다. #include #define int long long usi..

백준 BOJ 18869번 : 멀티버스 II 문제 난이도 : Gold V 알고리즘 분류 : 값/좌표 압축 두 집합에 대해, a_i, a_j와 b_i, b_j의 대소 관계가 모두 같다면 두 집합은 동일하다고 할 때, N개의 집합에 대해 몇 개의 집합 쌍이 동일한지를 구하는 문제이다. 각 집합에 대해 좌표 압축을 수행해주면, 원소들의 대소 관계가 같은 집합은 동일한 원소들을 가지게 된다. 이를 활용하여 좌표 압축을 N번 반복해준 뒤 브루트포스로 답을 구해주면 된다. #include #define int long long using namespace std; main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); int M, N; ci..

백준 BOJ 17272번 : 리그 오브 레전설 (Large) 문제 난이도 : Gold I 알고리즘 분류 : 분할 정복을 이용한 거듭제곱 N초를 길이가 1초인 스킬과 길이가 M초인 스킬로 구성하는 방법의 수를 구하는 문제이다. dp[N] = dp[N-1] + dp[N-M]이라는 점화식을 세울 수 있다. 그러나 Large 문제에서는 N이 10^18 이하이므로 dp로는 풀이가 불가능하다. 따라서 점화식을 행렬로 구성하여 행렬의 거듭제곱으로 답을 구해주어야 한다. 위와 같이 점화식을 만들 수 있다. 참고로 M이 100 이하이므로, 행렬의 크기는 아무리 커도 100 x 100을 넘어가지 않는다. 위의 A 행렬을 N 제곱 해주면, 곱해지는 행렬은 a_0, a_-1, ...으로 구성되는데, 정의에 의해 a_0 = 1..

백준 BOJ 12987번 : Matrix Again 문제 난이도 : Gold II 알고리즘 분류 : 분할 정복을 이용한 거듭제곱 주어진 행렬 A에 대해, S = A + A^2 + ... + A^K를 구하는 문제이다. 단일 행렬에 대한 거듭제곱은 N^2 log K 시간에 구할 수 있으나, 식 S의 경우에는 그러한 방식을 쓰더라도 결국 각 항을 따로 구하면 시간 복잡도가 늘어난다. 따라서 이 문제에서는 점화식을 사용하여 분할 정복으로 문제를 풀어주어야 되는데, 점화식은 다음과 같다. 위와 같이 점화식을 세우면 K를 계속해서 2로 나눠가면서 log 시간 복잡도로 식의 값을 구할 수 있다. 이 때 ( i ) 케이스의 A^(K/2)는 분할 정복을 이용한 거듭제곱 알고리즘을 사용하여 log(K) 시간에 구해준다. ..

백준 BOJ 12878번 : Blocks 문제 난이도 : Gold III 알고리즘 분류 : 분할 정복을 이용한 거듭제곱 N개의 블럭을 각각 빨강, 주황, 노랑, 초록색 중 하나로 칠하는데 그들 중 빨간색으로 칠해진 블럭과 노란색으로 칠해진 블럭이 각각 짝수개인 경우의 수를 구하는 문제이다. 가장 간단한 해결책은 N = 5 정도까지 완전 탐색으로 모든 경우를 count 해본 뒤, 규칙을 찾아 일반항을 찾는 방법이 있다. 직접 계산하는 방법은 위와 같다. 빨간색 또는 노란색으로 칠할 블럭을 선택하고, 그들 중 빨간색으로 칠할 블럭을 고른다. 나머지 블럭 중에서는 초록색 또는 주황색 중 어떤 색으로 칠할지를 고른다. 이 문제의 식 유도에서 핵심은 NC0 + NC2 + NC4 + ... = 2^(N-1)임을 알..

백준 BOJ 1185번 : 유럽여행 문제 난이도 : Platinum IV 알고리즘 분류 : 최소 스패닝 트리 (MST) 트리 형태의 그래프가 주어지고, 한 지점에서 시작하여 어떤 노드와 간선을 지나갈 때의 비용이 모두 주어질 때, 최소 비용으로 모든 노드를 순회할 때 드는 최소 비용을 구하는 문제이다. 경로를 생각해보면, 시작점을 제외하고 어떤 경로든 지나갔다가 다시 돌아와야 하므로, 간선의 시작점 → 간선 → 간선의 끝 점 → 간선 순서로 반드시 지나가게 된다. 따라서 간선의 비용 자체를 (간선의 시작점의 비용 + 간선의 끝 점의 비용 + 간선의 비용 x 2)로 설정해주고, 여기에 시작점으로 설정할 최소 비용인 노드의 비용을 더해주면 된다. #include #define int long long usi..

최근 최소 스패닝 트리 (MST) 문제들을 풀이하고 있는데, 문제 풀이 방식이 다들 상당히 비슷해서 모든 문제들의 풀이를 적는 것은 비효율적으로 보인다. (크루스칼이나 프림 알고리즘으로 모두 풀린다) 그들 중 별도의 아이디어가 필요한 문제들만 몇 개 풀이를 적어보려고 한다. 백준 BOJ 22570번 : Save your cats 문제 난이도 : Gold IV 알고리즘 분류 : 최소 스패닝 트리 (MST) 마녀가 울타리로 고양이를 가두었다고 하며, 각 폐쇄된 공간에는 고양이가 갇혀있다. 울타리를 부수는 비용은 울타리의 길이에 해당할 때, 최소 비용으로 고양이를 모두 구하는 비용을 구하는 문제이다. 울타리들을 그래프의 간선이라고 생각해보자. 사이클이 존재하지 않으면 모든 고양이가 구출될 수 있으므로, 결국 ..