복습 정리 노트

백준 BOJ 11012번 : Egg 문제 난이도 : Platinum II 알고리즘 분류 : 퍼시스턴트 세그먼트 트리 2차원 좌표계에서 점들의 좌표가 주어질 때, 직사각형 영역이 쿼리로 주어지면 해당 영역에 점이 몇 개가 있는지를 구하는 문제이다. (0 ≤ x, y ≤ 10^5, Q ≤ 50,000) 1차원 좌표계였다면 일반적인 세그먼트 트리로 해결이 가능한 것은 물론이고 값의 갱신이 없으므로 누적 합으로도 쉽게 계산이 가능하다. 2차원 좌표계 + 작은 범위였다면 2차원 배열의 누적 합으로 쉽게 계산이 가능하다. 이 문제에서는 세그먼트 트리 또는 2차원 배열을 선언하면 메모리 초과가 발생하게 되는데 이를 어떻게 해결할 수 있을까? 이러한 문제는 퍼시스턴트 세그먼트 트리(Persistent Segment T..

백준 BOJ 1739번 : 도로 정비하기 문제 난이도 : Platinum I 알고리즘 분류 : 2-SAT 어떤 가로 도로에 대해서 왼쪽 일방 통행의 경우 T, 오른쪽이면 F로 임의로 두자. 마찬가지로 세로 도로에 대해서도 위 방향은 T, 아래 방향을 F로 두자. 방향은 푸는 사람이 정의하면 된다. 명제 연결할 때만 제대로 연결하면 관계없다. 이제 어떤 점에서 다른 점으로의 이동에 대해, 두 가지 경로가 있으므로, 두 경로에 대해 (A and B) or (C and D)꼴이 나온다. 이것을 식을 풀어서 (나는 분배 법칙으로 풀었다.) (E or F) and (G or H) 꼴로 바꾼 뒤 2-SAT를 적용해주면 된다. 이 문제는 2-SAT에 다른 알고리즘이 접목된 문제도 아닌데 난이도가 Platinum I이..

11월 말 백준에서 풀이한 문제들 중, 플래티넘 이상 난이도 문제들에서 다른 사람들이 잘 다루지 않는 내용들을 선별하여 정리해보려고 한다. 이번 기간에 다룬 알고리즘은 MCMF(최소 비용 최대 유량)이다. 낮은 난이도나 다른 사람들이 많이 푼 문제들은 이미 다 풀어서 플래티넘 난이도 중에서도 어려운 것만 남았고, 그에 대한 풀이를 다룬 사람들이 별로 없어서 간략하게나마 적어본다. 어디까지나 스스로 공부, 잊어버렸을 때 나중에 다시 참고하기 위한 목적이지만 혹시나 검색 유입으로 보는 사람이 있다면 도움이 될 수 있으면 좋겠다. 백준 BOJ 14424번 : 두부장수 장홍준 3 문제 난이도 : Diamond V 알고리즘 분류 : MCMF (최소 비용 최대 유량) 사실 이 문제는 이전에 백준 BOJ 11111번..

최근 글 작성 빈도가 현저히 낮아졌는데, 바쁘다거나 그런 이유보다는 2022년 막바지로 갈수록 의욕이 떨어져간다는 표현이 맞는 것 같다. 그래도 아직 백준에서 2022년 푼 문제 수 랭킹 1위를 유지하고 있기 때문에 최소한 유종의 미라도 거두기 위해 연말까지는 열심히 풀어보려고 한다. 아무튼 11월 중순동안 공부한 내용들을 나중에 스스로 참고할 수 있도록 정리해보려고 한다. 백준 BOJ 2626번 : 헬기착륙장 문제 난이도 : Diamond V 알고리즘 분류 : 최소 외접원 2차원 좌표 평면 상의 N개의 점이 주어질 때 이들을 모두 포함하는 가장 작은 원의 중심과 반지름을 구하는 문제이다. 세 점을 지나는 원이 반드시 존재함을 이용하여 풀이하는 문제이다. (여담으로, 타원의 경우 최대 다섯 개의 점을 지..

백준 BOJ 17030번 : Cow Dating 문제 난이도 : Diamond V 알고리즘 분류 : 투 포인터, 누적 합 N개의 선택받을 확률 p_i가 주어질 때 (실제 입력은 p_i의 10^6배를 한 값들로 주어진다.) 연속한 구간 p_l ~ p_r을 선택하여 그들 중 하나에게만 선택이 될 확률의 최댓값을 구하는 문제이다. 구간을 잡고 관계식을 찾는 것이 핵심이다. 구간 [l, r]에서의 확률이 이미 있을 때, 어떤 조건에서 구간을 늘렸을 때 확률이 늘어나는지 계산해보자. 구간 [l, r]에서 하나에게만 선택받을 확률 f(l, r)은 위의 식처럼 나타낼 수 있고, 거기에 항을 하나 추가하여 f(l, r+1)을 관계식으로 구할 수 있다. 그러면 f(l, r+1) > f(l, r)일 조건을 찾아주면 된다...

백준 BOJ 24486번 : Counting Haybales 문제 난이도 : Diamond II 알고리즘 분류 : DP N개의 자연수가 주어지고, 크기 차이가 1인 인접한 두 수를 서로 swap할 수 있다고 할 때, 만들 수 있는 서로 다른 수열의 개수를 구하는 문제이다. 문제의 풀이는 USACO 사이트를 참고하였다. 먼저 관찰을 통해 알 수 있는 사실은 홀짝성이 같은 수들끼리는 순서가 바뀔 수 없다는 것이다. (이것은 오직 크기 차이가 1인 인접한 두 수만 교환이 가능하므로, 홀짝성이 같은 = 크기가 2 이상 차이나는 수는 서로 위치가 바뀔 수 없기 때문이다.) 원래 정석적인 풀이는 이 사실을 이용하여 그래프의 단방향 간선들을 만들 수 있으므로, 위상 정렬로 푸는 풀이로 보인다. 아무튼 홀짝성을 활용하..

백준에서 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. 쾨니그의 정리는 최대 매칭 수 = 최소 꼭짓점 덮개 수라는 정리이다. 여기서 최소 꼭짓점 덮개란 몇 개의 노드를 선택하여 이들과 이 꼭짓점들을 포함하는 간선들을 체크할 때, 모든 간선들이 체..