복습 정리 노트

백준에서 3600문제 넘게 풀면서 루비 난이도 문제를 처음으로 푼 기념으로 이 문제만 별개의 포스트로 정리해본다. 무려 월드 파이널 문제이며 그 해 문제 중에서도 solved.ac 기준으로 난이도가 가장 높은 문제이다. 백준 BOJ 10058번 : 센서 네트워크 문제 난이도 : Ruby V 알고리즘 분류 : 기하학, 이분 매칭 2차원 좌표 평면 상에 N개의 점이 주어질 때, 어떤 두 점의 거리도 M 이하가 되게 하는 점들의 집합의 최대 크기와 그 때의 점들의 번호 목록을 구하는 문제이다. 가장 naive하게 생각할 수 있는 풀이는 각 점을 집합에 포함시키거나 시키지 않은 뒤 해당 집합에서 가장 먼 두 점 사이의 거리가 M 이하라면 집합의 최대 크기를 비교하여 갱신해주는 방식이 있다. 이 때의 시간 복잡도..

백준 BOJ 3419번 : Racing Car Trail 문제 난이도 : Diamond III 알고리즘 분류 : 이분 매칭 N x M 크기의 배열이 주어지고, X가 없는 칸에서만 이동이 가능하다고 할 때, Alice와 Bob이 번갈아가면서 지나온 칸은 다시 이동하지 않도록 칸을 이동시키면서 상대가 더 이상 이동하지 못하도록 최선의 전략으로 이동시킨다고 할 때, 각 칸에서 시작할 때 누가 이기는지를 구하는 문제이다. 격자 그래프는 이분 그래프이므로 이분 매칭 알고리즘으로 최대 매칭을 구한 뒤, 시작점 v를 포함하지 않는 최대 매칭이 존재한다면 Bob이 항상 이길 수 있다. 왜냐하면 그러한 매칭이 존재하는 경우 Alice는 어떻게 이동해도 최대 매칭에 포함되는 정점으로 이동하게 되고, Bob은 그 격자점과 ..

이 포스트에서는 이분 매칭의 응용 중 하나인 최대 독립 집합(Maximum Independent Set)에 대해서 다룬다. 어떤 노드들의 집합에서 어떤 두 노드도 서로 간선으로 연결되어 있지 않을 때, 이 집합을 독립 집합이라고 한다. 그래프에서 최대 크기의 독립 집합을 최대 독립 집합이라고 한다. 이분 매칭 문제에서 최대 독립 집합은 전체 노드에서 최소 정점 커버(= 최소 꼭짓점 덮개)를 뺀 나머지가 된다. 그리고 최소 정점 커버는 쾨니그의 정리에 의해서 최대 매칭 수와 동일하다. 즉, 최대 독립 집합의 크기 I = V - M이다. (V = vertex의 수, M = 최대 매칭 수) 백준 BOJ 14986번 : Punching Power 문제 난이도 : Platinum III (난이도 기여로 난이도 상..

이분 매칭 알고리즘에 대해서는 이전에 다룬 적도 있고 문제 풀이도 한 적 있지만 잊어버린 내용이 많아서 공부를 위해 다시 정리해본다. 이분 매칭 알고리즘 1. 이분 그래프란 그래프의 정점을 같은 그룹의 노드 사이에 간선으로 연결된 노드 쌍이 존재하지 않도록 두 그룹으로 나눌 수 있는 그래프를 의미한다. 2. 이분 매칭 알고리즘은 이러한 이분 그래프에서 하나의 노드가 두 개 이상의 간선에 포함되지 않도록 선택할 수 있는 최대 간선의 수를 말한다. (즉, 최대한으로 매칭시킬 수 있는 노드 쌍의 수를 찾는 것이다.) 3. 쾨니그의 정리는 최대 매칭 수 = 최소 꼭짓점 덮개 수라는 정리이다. 여기서 최소 꼭짓점 덮개란 몇 개의 노드를 선택하여 이들과 이 꼭짓점들을 포함하는 간선들을 체크할 때, 모든 간선들이 체..

백준 BOJ 25711번 : 인경산 문제 난이도 : Gold V 알고리즘 분류 : 누적 합 2차원 좌표 상의 N개의 점이 주어지고, 어떤 인접한 구간의 두 점 사이를 이동할 때 필요한 에너지는 내리막길일 경우 거리에 해당, 평지일 경우 거리의 2배, 오르막길일 경우 거리의 3배라고 할 때 M개의 쿼리에 대해 두 지점 사이의 필요한 에너지들을 구하는 문제이다. 쿼리 문제이므로 O(1)이나 O(log N)과 같이 짧은 시간에 쿼리를 처리할 수 있어야 한다. 이 문제에서는 누적 합을 이용하여, 맨 왼쪽 지점에서부터 특정 지점까지 이동하는데 필요한 에너지들의 목록을 구해둔다. 반대로, 맨 오른쪽 지점에서부터 특정 지점까지 이동하는데 필요한 에너지들의 목록도 구해둔다. 각각의 값들은 위에서 정의한 식대로 구해주면..

풀이한 문제들 중에서 인상적인 문제만 몇 개 뽑아서 정리한다. 문제 알고리즘은 무작위로 선정하였다. 백준 BOJ 25569번 : My뷰 꾸미기 문제 난이도 : Platinum IV 알고리즘 분류 : 조합론, 분할 정복을 이용한 거듭제곱 N개의 (a, b)쌍에 대해 min(a, b) = c라고 할 때, (a C 1 x b C 1) + (a C 2 x b C 2) + ... + (a C c x b C c)의 합을 구하는 문제이다. N과 a, b는 30만 이하이다. 각 항을 팩토리얼과 분모는 페르마의 소정리 + 분할 정복을 이용한 거듭제곱으로 계산이 가능하나, 항이 매우 많아 시간 초과에 걸리게 된다. 이 경우 항을 줄여주어야 하는데, (a C 1 x b C 1) + (a C 2 x b C 2) + ... +..

삼분 탐색 알고리즘(Ternary Search Algorithm)이란 말 그대로 구간에서 1/3 지점과 2/3 지점의 함수값의 크기 비교를 기반으로 탐색을 해나가는 알고리즘이다. 이분 탐색 알고리즘은 그래프가 단조 증가 또는 단조 감소한다는 조건 하에서만 사용이 가능하지만, 삼분 탐색은 극값이 최대 1개 이하로 있는 모든 그래프에 대하여 사용 가능하다. (즉, 단순히 극값을 갖는 그래프 뿐만이 아닌 단조 증가, 감소 그래프에서도 사용이 가능하다.) 1개의 최솟값을 갖는 y = x^2 꼴의 그래프를 [l, r]의 구간에서 삼분 탐색하는 상황에 대해 생각해보자. (물론 극값을 구간에 포함하고 있다고 가정한다.) 1/3 지점을 x = m1, 2/3 지점을 x = m2라고 하며, 우리는 극값의 x 좌표 x_mi..

백만년만에 문제 풀이 정리를 한다. 물론 시간 날 때마다 문제는 꾸준히 풀어오고 있다. 그동안 정리 안 한 것은 브론즈 문제들을 굳이 풀이를 정리하기에는 불필요하다고 느껴서였고, 가끔 약간의 메모가 필요한 문제들이 있으면 정리해보려고 한다. 백준 BOJ 8120번 : Coding of Permutations 문제 난이도 : Gold I 알고리즘 분류 : 세그먼트 트리 길이 N인 수열로 a_i = i번째 위치의 왼쪽에 있는 더 큰 수의 개수가 주어질 때, N에 대한 순열을 찾는 문제이다. 예를 들어 (0, 0, 1, 0, 2, 0, 4)가 주어진다면 (1, 5, 2, 6, 4, 7, 3)이 답인데 왜냐하면 1의 왼쪽에 더 큰 수가 0개, 5의 왼쪽에 더 큰 수가 0개, 2의 왼쪽에 더 큰 수가 1개, 6의..

백준 BOJ 25513번 : 빠른 오름차순 숫자 탐색 문제 난이도 : Gold V 알고리즘 분류 : BFS 주어진 5 x 5 크기의 배열에서, 특정 위치에서 시작하여 1, 2, 3, 4, 5, 6을 순서대로 방문하는 최소 경로의 길이를 구하는 문제이다. (이 때, -1은 지나갈 수 없는 칸이며 만약 순서대로 방문하는 것이 불가능하다면 -1을 출력해야 한다.) BFS를 반복문으로 여러 번 사용하는 문제이다. 초기 위치에서 cur(1 ~ 6으로 반복문을 돌려준다.)를 방문하는 BFS를 구현하고, 방문이 되었다면 초기 위치를 해당 칸의 위치로 바꿔주고 다음 루프를 돌면 된다. 만약 방문이 불가능하다면 -1을 출력해주고 즉시 종료해주면 된다. 더보기 #include #define int long long usi..

백준 BOJ 12041번 : Password Security (Small 2) 문제 난이도 : Gold III 알고리즘 분류 : 무작위화, 구성적 모든 대문자 알파벳을 하나씩 사용하여 26자리 비밀번호를 만들 때, 해당 비밀번호가 N개의 주어진 문자열을 포함하지 않도록 만드는 문제이다. 1 ~ 26으로 이루어진 순열을 무작위로 만든 뒤, 이 순열에 해당하는 문자열이 N개의 문자열을 포함하지 않을 때까지 돌리면 된다. 문제는 아예 불가능한 경우가 있는데, 이를 해결하기 위해 1만번까지는 돌려보고, 그래도 해당하는 정답이 없으면 impossible로 간주해주면 모든 테스트케이스를 통과할 수 있다. (참고로 1천번은 넉넉하지 않아 WA를 받을 확률이 높다.) 더보기 #include #define int lon..