본문 바로가기

동적계획법

(3)
[백준] 2098 - 외판원 순회 www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 컴공 전공필수 과목인 알고리즘 수업을 들으면 동적계획법/DP을 배우게되면 대표적으로 배우게 되는 사례가 피보나치 수열과 외판원 순회 TSP(Travelling salesman problem)이다. 그런데 대학 졸업한지가 이미 10년이 넘은 시점에 이 문제를 보니, 전형적인 외판원 순회 문제라면서 문제 설명이 이것도 친절하지가 않다;;; 외판원 순회 문제에 대한 설명은 내가 ..
[백준] 5626 - 제단 www.acmicpc.net/problem/5626 5626번: 제단 첫째 줄에 가능한 제단의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 문제 설명이 너무 불친절하다. 이해하는데만 한참이 걸렸다. 동적계획법/DP 문제다. DP는 점화식을 세우는게 관건인데, 이게 문제마다 점화식을 도출하는 방식이 워낙 다양하다보니 잘하는데에 왕도가 없다. -_-;;; 그냥 많이 풀어보는 것 밖에는 답이 없는 듯... 이 문제는 DP의 사이즈를 제단의 사이즈만큼 모두 잡아버리게 되면 10000 x 5000 x 4 바이트의 저장공간이 필요하게 되는데 이러면 메모리 초과가 난다. 그래서 점화식을 세우면서 메모리를 절약하는 방법에 대한 고민을 해결하는게 포인트다. N번째 제단 열에서 가..
[백준] 1103 - 게임 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 문제에서 제시하는 map의 사이즈가 최대 50x50이라 시간초과가 날 일은 없을 것이라 생각하고, DFS(깊이우선 탐색)을 통한 완전 탐색을 하면 될 줄 알았다. 그런데 문제를 다시 읽어보니 말을 움직이는데 있어 중간에 사이클이 생길 수 있네? 사이클에 대해서는 같은 map 사이즈로 visited 배열을 선언해서 이전에 방문한 적이 있으면 -1을 출력 후 리턴을 하게 해주었는데, 같은 위치를 가더..