Algorithm/BOJ (19) 썸네일형 리스트형 [BOJ 28703] Double It 우선순위 큐 문제 https://www.acmicpc.net/problem/28703 [문제 설명] 구해야 하는 답이 매 순간마다의 최댓값과 최솟값의 차이고, 가능한 연산은 2를 곱해주는 것밖에 없으므로 어렵지 않게 최소 우선순위 큐를 떠올릴 수 있을 겁니다. 그러나 이 문제가 어려워 보이는 이유는 2를 곱하는 연산에 대해 횟수 제한이 없기 때문입니다. A의 원소들에 대해 적절히 2를 곱해주는 작업을 얼마나 해야 차가 최소가 되는지 직관적으로 알 수 없기 때문에 어려워 보입니다. 배열 A의 최솟값이 $m$, 최댓값이 $M$, $M - m$을 $r$이라고 하겠습니다. A의 모든 원소에 2를 곱해보겠습니다. 최솟값은 $2m$, 최댓값은 $2M$이 되고, 차를 구하면 $2(M-m) = 2r$이 됩니다. A의 .. [BOJ 28218] 격자 게임 게임 이론 문제 https://www.acmicpc.net/problem/28218 [문제 풀이] 문제를 요약하자면 두 사람이 번갈아 가면서 특정 칸부터 (N, M)까지 오른쪽으로 한 칸씩, 아래로 한 칸씩, 혹은 대각선으로 K칸을 이동하는 게임을 할 때, 첫 번째로 이동하는 사람이 이길 수 있는지 묻는 문제입니다. 특정 칸에서 시작해서 무조건 이길 수 있는지 확인하는 것은 상당히 머리가 아픕니다. 생각을 달리 해볼 필요가 있습니다. 직관적으로 떠올릴 수 있도록 위해 예시를 들겠습니다. N = 6, M = 8, K = 3이고 막힌 칸이 없는 보드를 예시로 보겠습니다. 동그라미가 있는 위치에서 (N, M)으로 이동할 때 누가 이길지 직관적으로 떠올리기는 매우 어렵습니다. 하지만 해당 위치에서 (N, M)으.. [BOJ 1867] 돌멩이 제거 이분 매칭 문제 https://www.acmicpc.net/problem/1867 [문제 풀이] https://kangwlgns.tistory.com/128 [소스 코드] / C++ #include #include #include using namespace std; int N; vector adj[501]; int B[501]; bool visited[501]; void BtR() { for (int i = 0; i < 501; i++) { B[i] = -1; } } void setVisited() { for (int i = 1; i < N + 1; i++) { visited[i] = false; } } bool dfs(int cur) { visited[cur] = true; for (int next .. [BOJ 3295] 단방향 링크 네트워크 이분 매칭 문제 https://www.acmicpc.net/problem/3295 [문제 풀이] 결론부터 말하면 그냥 이분 매칭 문제입니다. 모든 노드에 대한 연결 관계를 간선으로 추가한 후에 최대 매칭을 구하면 됩니다. 이게 왜 평범한 이분 매칭 문제인지 설명해 보겠습니다. 이 문제를 설명하기에 앞서 상어의 저녁 식사와 결이 비슷하여 먼저 설명하겠습니다. 상어 문제는 상어가 서로 먹을 수 있는 관계가 주어졌을 때 서로 먹을 수 있는 최댓값을 구하는 문제입니다. 모든 상어를 이분 그래프 양쪽 집단에 전부 배치하고 먹을 수 있는 관계로 간선을 그어주면 이분 매칭 문제라는 걸 알 수 있습니다. 그런데 이미 먹힌 상어가 다른 상어를 먹을 수 없다는 조건이 붙어있습니다. 이 조건을 해결하는 핵심은 우선 매칭을 .. [BOJ 16570] 앞뒤가 맞는 수열 KMP 문제 https://www.acmicpc.net/problem/16570 KMP 실패 함수 응용 문제입니다. [문제 풀이] 앞에서부터 수열을 잘라가면서 접두부와 접미부가 일치하는 최대 길이와 그 길이가 가능한 방법의 수를 구하는 문제입니다. 아주 간단하게 생각해보면 수열을 앞에서부터 하나씩 자르면서 자른 수열의 앞뒤가 같은지 비교하고, 앞뒤가 다르다면 제일 앞의 수를 또 자르고 비교(생략)하면 됩니다. 그러나 이렇게 푼다면 앞에서부터 잘린 수열의 개수 N개에 대해 수열의 앞뒤를 비교하게 되는데, 1 1 1 ... 1과 같이 수열의 모든 요소가 같다면 위의 생략 과정이 없어지기에 시간복잡도는 $O(N^2)$이 됩니다. N이 1,000,000이니 당연히 시간 초과입니다. 접두, 접미에 관한 내용이 나.. [BOJ 1106] 호텔 배낭 문제 https://www.acmicpc.net/problem/1106 https://www.acmicpc.net/problem/12865 해당 문제를 응용한 문제입니다. [문제 풀이] 전형적인 배낭 문제입니다. 적어도 C명을 늘리기 위한 최소한의 비용을 내야 합니다. 이 '적어도'가 중요하지만 지금은 넘어가겠습니다. 근본적인 해결 방법은 배낭 문제(다이나믹 프로그래밍)와 같습니다. 부분 문제로 나눠주면서 메모이제이션을 적용하면 됩니다. 한 개의 도시에 대해 할 수 있는 선택지는 다음과 같습니다. 1. 해당 도시에 홍보를 한다. (홍보 비용을 지불하고 고객 수를 늘림) 2. 해당 도시에 홍보를 하지 않는다. (홍보 비용을 지불하지 않음) 1번 선택지를 고른다면 해당 도시에 홍보 비용을 지불하기 전에.. [백준 14750] Jerry and Tom 최대 유량 문제 www.acmicpc.net/problem/14750 www.acmicpc.net/problem/2188 www.acmicpc.net/problem/17387 위의 두 문제를 먼저 푸는 것을 권장합니다. 해당 문제들을 풀이할 수 있다고 생각하고 설명하겠습니다. [문제 풀이] n개의 벽에 k마리가 들어갈 수 있는 구멍 h개와 m마리의 쥐가 존재할 때 구멍에 들어갈 수 있는 쥐의 수의 최댓값을 구하는 문제입니다. 다른 모든 조건은 생각하지 않고 k마리가 들어갈 수 있는 구멍 h개에 쥐 m마리를 넣을 때의 가능한 최대 마릿수를 생각해봅시다. m마리의 쥐를 h개 구멍에 넣는 최댓값. 최대 유량을 떠올릴 수 있어야 합니다. 최대 유량이 떠오르지 않았다면 백준 2188번 축사 배정을 풀어보는 것을 .. [백준 20152] Game Addiction 조합론 문제 www.acmicpc.net/problem/20152 [문제 풀이] (N, N)에서 (M, M)으로 가는 최단경로의 개수 중, $y x$는 사용하지 않습니다. (N, N) 지점의 dp테이블 값을 0으로 설정한 뒤, 오른쪽 위로 이동하면서 dp테이블의 값을 (왼쪽의 dp테이블 값) + (아래쪽의 dp테이블 값)으로 설정해주면 풀이가 가능합니다. 점화식으로는 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]입니다. 그러나 이 문제는 조합으로도 풀이가 가능합니다. 우선, $y > x$인 부분을 사용하지 않는다는 조건이 없었다면 더 쉬운 문제입니다. 높이가 h고 너비가 w인 2차원 평면에서 양 끝점으로 이동하는 최단 경로의 개수는 $\dbinom{h + w}{h}$입니다. 해당 .. 이전 1 2 3 다음
