https://icpc.me/9465 # 문제 분류 Dynamic Programming 풀이 접근 방법 : 1. 2행짜리 배열을 요리조리 왔다갔다하면서 최댓값이 결정된다는 것이 좀 골치아파 보이는 문제이다. 2. 하나를 제거하면 마주보는 변의 스티커는 제거할 수 없기 때문에, 대각선 방향으로 보는 것으로 생각하면 된다. 3. DP 배열을 3행으로 만들어서, 1, 2행은 각각의 스티커를 제거했을 때의 dp값을, 3행은 제거하지 않았을 때의 dp값을 저장. Line 32에서 i == j 일 때 continue 해준 것이 바로 마주보는 변의 스티커를 동시에 제거할 수 없음을 말하는 것이다. 점화식은 dp[i][j] = max(dp[i+][j-1], dp[i-][j-1] 1 2 3 4 5 6 7 8 9 10 1..
https://icpc.me/11060 # 문제 분류 Dynamic Programming 풀이 접근 방법 : 1. 칸에 있는 수만큼 오른쪽 칸들을 보고 dp[current]에 1을 더해서 dp[jumped]에 넣으면 된다. 2. 단순하네! 3. 점화식은 dp[current+jump] = min(dp[current+jump], dp[current] + 1)이다. 맨 처음 dp 배열 초기화할 때 INF로 설정해주고, 만약 dp[N-1]이 INF라면 도달할 수 없는 것이므로 -1을 출력한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include ..
https://icpc.me/10844 # 문제 분류 Dynamic Programming 풀이 접근 방법 : 1. 0으로 시작하는 수는 없다는 점을 생각하며 DP 테이블을 작성해보자. 2. 그러면 0 → 1 만 가능, 9 → 8 만 가능하다는 것이 보이게 된다. 3. dp[0] = prev[1], dp[9] = prev[8], dp[n] = prev[n-1] + prev[n+1] (n != 0, 9)로 점화식을 세울 수 있다. 밑 python 코드에서는 tmp 배열이 prev의 역할을 하며, 계속해서 갱신된 dp 배열을 tmp 배열로 deepcopy 해주는 방식. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import copy as cp size = int(input..
서로소 집합, 유니온 파인드 - Disjoint set, Union-Find
0) Introduction Disjoint-set 자료구조는 Union-find나 Merge-find set과 동의어이다. 서로소 집합 트리는 요소들을 서로소 집합으로 나누고, 찾을 수 있는 자료구조이다. → 최소 신장 트리(Minimum spanning tree)를 찾는 Kruskal Algorithm을 구현하는 데에 중요한 역할을 한다. 1) Operations of Union-find Union-find는 다음과 같은 연산들이 구현되어 있어야 한다. 제일 중요한것은 Find와 Union이긴 하지만,, 한번 알아보자. 1. MakeSet 단순히 서로소 집합 트리에 노드들을 집어넣는 연산이다. rank와 size를 초기화하는 것이 눈에 띄는데, 트리가 편중(skewed)되는 것을 Union 연산에서 ..
최단 경로 알고리즘 - algorithm for shortest path problem
최단 경로를 구하는 문제에서 적용할만한 알고리즘을 알아보자. 0) 모델링 그래프에 대한 정보는 인접 행렬이나 인접 리스트를 이용해 모델링할 수 있다. 1. Adjacency Matrix (인접 행렬) 노드 개수 V개가 있다면 V^2개의 배열에 간선의 정보를 저장하는 것이다. 구현이 쉽고 간편해 보이지만, 간선의 유무와 관계없이 전체를 탐색해 보아야 하기 때문에 전체 탐색시 O(V^2)이 걸린다. 그러나 배열의 특성상 특정 간선만 알고 싶을 때는 O(1) 밖에 소요되지 않는다는 장점이 있다. ex) i → j : edge[i][j] = true; 2. Adjacency List (인접 리스트) 간선의 정보를 배열에 저장하는 인접 행렬과 달리 벡터에 저장한다. 간선의 개수만큼의 메모리가 필요하므로 효율적이고..
https://icpc.me/4485 # 문제 분류 최단 경로 찾기 (Dijkstra Algorithm) 풀이 접근 방법 : 1. 결국 바둑판처럼 생긴 격자에서 최단 경로를 찾는 것과 다를 바가 없다. 2. 시작점 (0, 0)과 끝점 (n-1, n-1)이 정해져 있으므로 Dijkstra 알고리즘을 사용하자. 페어 두개를 사용해서 좌표와 가중치를 표현해줬는데, 벡터로 해도 될지는 모르겠다. 벡터는 비교 연산자가 잘 정의되어 있어서,,, 벡터로 시도해보지는 않았다. 정 해야겠다면 bool operator< overloading으로 해결할 수는 있을듯 ? 별 다른 것은 없다. 주의할 점은 0과 n-1에서 범위 제한을 해줄 필요가 있다는 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ..
https://icpc.me/1389 # 문제 분류 최단 경로 찾기 (Floyd-Warshall Algorithm) 풀이 접근 방법 : 1. 각각 노드 쌍에 대한 최단 경로를 모두 구해야 하므로 Floyd-Warshall 알고리즘을 사용하자. 2. 회장뽑기@2660 처럼 생각하면 가중치를 통해 서로 얼마나 떨어져있는지(또는 가까운지) 알 수 있다. 3. 한 명에 대한 나머지 사람들의 점수를 모두 합하면 케빈 베이컨 수를 구할 수 있다. 케빈 베이컨 수가 같은 경우 인덱스 순으로 먼저인 사람을 출력하라고 했으므로, 그 부분만 신경써서 처리해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ..
https://icpc.me/1238 # 문제 분류 최단 경로 찾기 (Dijkstra Algorithm) 풀이 접근 방법 : 1. input size가 크므로 Dijkstra 알고리즘을 사용한다. 2. 각각의 노드마다 Dijkstra하면 되므로, n번 돌리면 O(VElogV)이므로 가능하다. → 사실 엄밀히 말하면 Oworst(EV+ V^2 * logV)긴 하다 ,, 그래도 Floyd-Warshall 보다는 훨씬 빠르다! 3. 그래서 dist[i][X] + dist[X][i]가 학생 i 가 파티에 참석한 후 돌아오기 필요한 거리이므로 그 중 제일 긴 것 갱신. https://hsp1116.tistory.com/44 포스트를 보면 Floyd-Warshall 을 가지치기해서 시간을 줄이는 방법이나, 인접 리..