https://www.acmicpc.net/problem/14442 자바로 한번 구현해봤더니 파이썬의 편리함을 다시 한번 깨닫게 해준 문제... 문제 풀이는 간단하다.(i, j) 위치에 k번의 벽 부수기 횟수가 남은 상태로 도착했을 때, 그때의 최단 이동 경로를 다 저장하면된다.최악의 경우 1000*1000*10 = 1000만 칸의 배열을 채워야 하는데, 2초 시간 제한과 512MB 의 메모리 제한이라면 충분히 채울 수 있다. 만약 이동하려는 칸이 벽이라면 현재 칸에서 남은 벽 부수기 횟수를 1 감소시켜서 이동시키고, 이동하려는 칸이 벽이 아니라면 남은 횟수를 그대로 가져가면서 이동하면 된다. import java.io.BufferedReader;import java.io.IOException;impor..
https://www.acmicpc.net/problem/1949 지금까지 푼 트리 DP 문제와 같은 방법으로 풀면 된다.다만 3번 조건이 애매하게 마음 속에 걸렸다.뭔가 직감적으로는 내 풀이가 3번 조건을 자연스럽게 만족하는 정답을 도출할 것 같은데 확실하진 않은 느낌.. 우선 풀이는 다음과 같다.현재 노드를 루트로 하는 서브트리에 대해 현재 노드가 우수마을인 경우, 최적해와 우수마을이 아닌 경우 최적해를 저장하는 DP 테이블을 짜고 다음과 같이 점화식을 세운다. dp[node][우수마을o] = sum( dp[child][우수마을x], ... )dp[node][우수마을x] = sum( max(dp[child][우수마을o], dp[child][우수마을x]), ... ) 부모 노드가 우수마을이 아닌 경우,..
https://www.acmicpc.net/problem/2533 트리 DP 문제DP 테이블을 다음과 같이 정의한다. dp[i][j] = i 번째 노드가 루트인 트리에 대해 이 노드가 얼리어답터 인지 (j = 0) 아닌지 (j = 1) 에 따른 그 트리에서의 얼리어답터 최소 수 점화식은 다음과 같이 쓸 수 있다. dp[i][0] = i 번째 노드가 루트인 트리에 대해 이 노드가 얼리어답터인 경우, 모든 자식노드는 얼리어답터여도 되고, 아니어도 된다. 두 경우를 모두 구해서 최소 값을 취한다. 따라서 sum( min( dp[k][0], dp[k][1] ) ) + 1, ( k 는 직접 연결된 자식 노드들의 번호 ) dp[i][1] = i 번째 노드가 루트인 트리에 대해, 이 노드가 얼리어답터가 아닌 경우, ..
https://www.acmicpc.net/problem/2213 트리를 구성하는 정점에 가중치가 있을 때, 인접하지 않은 정점들로만 구성된 정점의 부분집합에 대해 가중치의 합이 최대가 되는 부분 집합을 구하는 문제이다. 그에 더해 이 문제는 이 가중치의 합의 최댓값에 더해, 그 값이 나오도록 하는 부분 집합의 원소까지 구해야 한다. 이 문제는 트리 DP 로 유명하다.트리는 그 형태가 이미 재귀적이기 때문에 DP 로 표현하기가 매우 좋다. 이 문제의 DP 테이블을 다음과 같이 정의해보자. DP[i][j] = i 번째 노드를 루트로 하는 트리에 대해, 이 노드를 정점에 포함 (j = 0) 또는 포함하지 않을 때 (j = 1) 의 가중치 합의 최댓값 이제 점화식을 세워보면 만약 i 번째 노드를 계산에 포함한..
https://www.acmicpc.net/problem/1135 트리 구조로 이루어진 조직도가 있을 때, 제일 높은 조직의 사람이 자신의 직속 부하들에게 한번에 한 명씩 전화를 돌리며 뉴스를 전파한다.직속 부하들도 전화를 받은 뒤엔 자신의 직속 부하에게 한번에 한 명씩 전화를 돌리며 뉴스를 전파한다.이때 모든 직원들에게 뉴스가 전파되는 최소 시간을 구하는 문제이다. 나는 트리디피와 그리디가 섞인..? 느낌으로 풀었다. (DP보다는 그리디에 가까운 것 같아서 기여할 때는 그리디로만 기여했다.) 문제 이해하기전화를 그냥 돌리면 간선의 수 만큼 시간이 소요되지 않을까? 왜 최소 시간을 구하라고 한 것일까?예제 입력 2번을 보면 알 수 있다. 상사가 1번과 2번 중 어떤 사람에게 먼저 전화를 돌리는지에 따라 ..
최단 경로 스터디 자료를 만들다가 BFS로 최단 경로를 찾는 연습문제로 숨바꼭질이 생각나서 다시 풀어봤다.그런데 단순하게 BFS로 풀릴 줄 알았는데 맞왜틀을 해서 충격을 받았다.. (심지어 과거의 나는 1트만에 풀었었다..) 과거에 풀었던 풀이는 우선순위 큐를 이용한 다익스트라 풀이였다.이 풀이는 정말 다익스트라의 최단 경로 알고리즘을 곧이 곧대로 사용하는 것이니 틀릴 여지가 거의 없다. 그런데 BFS로 이 문제를 푸는 경우에는 여러가지를 고려해야 했다.from collections import dequen, k = map(int, input().split())visit = [False] * 200001d = deque()d.append((n, 0))visit[n] = Truewhile d: now..
https://www.acmicpc.net/problem/19663 정말 어려웠던 세그트리 연습문제처음에는 뭔가 DP일 것 같았고, 실제로 분류에도 DP가 있어서 DP로 풀이를 짜고, 세그트리로 최적화시키는 건가 싶었다.하지만 아무리 고민해도 DP 점화식이 생각이 안났고, 세그트리로 구현하는 방법만 계속 떠올랐다. 문제 이해수열이 주어질 때, 주어진 수열에서 인덱스 순에 맞게 3개의 수를 뽑아 만든 임의의 튜플 (x, y, z) 에 대해, x 첫 번째 시도알고리즘 분류에 있는 '정렬' 에서 힌트를 얻어 먼저 데이터를 높이순으로 정렬한다.어떤 기준점 y가 정해졌을 때, 이 값보다 작은 값들 중, y보다 왼쪽에 있는 값의 개수, 오른쪽에 있는 값의 개수를 센 뒤,두 값을 곱한 결과를 정답에 더해주면 된다...
https://www.acmicpc.net/problem/11003 티어는 플레티넘 5인데, 우선순위 큐로 너무나도 간단히 풀리는 최강 날먹(?) 문제질문 게시판을 보니, 덱을 이용해서 O(n) 에 풀 수 있도록 최적화 하는 것이 이 문제의 의도같은데, 입출력값이 너무 많아서 O(N) 으로 딱 제한을 두기가 힘든 모양이다.. 그럼에도 불구하고 파이썬 시간 제한이 9초대도 통과되는 건 너무 봐준 것 아닌가 싶기도.. 우선순위 큐 풀이는 최소힙에 (원소값, 원소 인덱스) 튜플을 저장하고, 범위가 늘어날 때마다 현재 보고 있는 원소를 우선순위 큐에 넣은 뒤, 최소힙에서 최소값을 본다.만약 본 값이 현재 최소값을 찾는 범위에 있는 값이라면 출력하고, 아니라면 최소힙에서 빼는 과정을 반복한다. 결과적으로는 N번의..
https://www.acmicpc.net/problem/1600 3차원 BFS 문제이다.dist[i][j][k] 를 (i, j) 위치에 있을 때 현재 남은 말 이동 횟수가 k 인 경우 그때까지 최소 이동거리라고 정의한 뒤, 일반 이동을 하는 경우dist[next_i][next_j][now_k] = min(dist[next_i][next_j][now_k], dist[now_i][now_j][now_k] + 1) 말로 이동하는 경우 k 를 소모하므로dist[next_i][next_j][now_k-1] = min(dist[next_i][next_j][now_k-1], dist[now_i][now_j][now_k] + 1) 이렇게 식을 세운뒤, dist 배열은 초기값을 INF 값 (파이썬은 보통 9876543..
https://www.acmicpc.net/problem/11780 학교 알고리즘 분석 전공 수업시간에 배웠던 내용을 그대로 이용하면 쉽게 풀 수 있는 문제이다.플로이드 알고리즘은 dp 를 이용하는 방법으로, node 개수가 많지 않을 때 사용할 수 있는 알고리즘이다.시간복잡도는 node 개수가 n개 일 때, O(n³) 의 시간복잡도를 갖는다. 두 노드 a, b 사이의 최단거리 a, b 를 dist[a][b] 라고 할 때, dist[a][b] = min( for k in range 1 .. n, dist[a][k] + dist[k][b] ) 로 정의할 수 있다. 글로 정리하면, 두 노드 사이의 최단 거리는 그 노드 사이를 k 번 노드를 경유해서 갈 때 더 짧다면 그 값으로 갱신하는 과정을 거치면 된다...
