DP(동적 계획법)을 풀기 위한 나만의 팁
백준에서 알고리즘을 공부할때마다 DP라는 태그가 붙은 것을 확인하면 문제를 풀기 싫었을때가 많았습니다.
점화식이라는 게 이해가 안됐고 풀이를 보더라도 어질어질했습니다. ㅠㅠ
하지만 저에게 DP를 푸는 팁을 준 문제가 있었습니다.
바로 외판원순회라는 문제로
https://www.acmicpc.net/problem/2098
2098번: 외판원 순회
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j
www.acmicpc.net
DP를 사용하기 위한 배열의 정의를 살펴보면...
DP[도시방문상태][현재도시위치] //현재 상태에서의 최소비용 |
- 상태를 배열을 통해서 표현하고 있었습니다!! -
다른 문제들도 마찬가지였습니다.
https://www.acmicpc.net/problem/2342
2342번: Dance Dance Revolution
입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마
www.acmicpc.net
DP[i번째발판을 누를차례][왼발위치][오른발위치] //i번째까지 도달하는데 사용한 최소힘 |
https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
DP[i번째발판에 있는 상태] //i번째까지 도달하는데 얻은 최대 점수 |
저는 DP문제를 풀때 먼저 배열로 상태를 표현할수있는지 확인합니다.
배열로 표현 할 수 있는 모든 상태를 표현할 수 있다면
점화식을 쉽게 유추할 수 있습니다.
많은 문제를 해당 스킬을 적용해서 풀수 있었고 현재도 애용하는 방법중하나입니다.
모든 문제에 해당 스킬을 적용할 수 있다고 장담할 수 없지만 DP문제를 푸는데 도움이 되는 스킬이라고 생각됩니다.
-----------------------------------------------------------------------------------------------------------------------------------
팁을 드렸지만 DP를 잘풀기 위해서는 역시 문제를 많이 풀어보는게 중요합니다.
<개인적으로 추천해드리고 싶은 DP문제들입니다.>
https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
점화식이 별로 어렵지 않아요 위에서 말해준 DP배열의 정의를 이용해서 점화식을 만드는 훈련을 해봅시다.
https://www.acmicpc.net/problem/2342
2342번: Dance Dance Revolution
입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마
www.acmicpc.net
조금 점화식 만들기 어려울수도있지만 위에서 정의해준 상태배열로 점화식을 만들어봅시다.
https://www.acmicpc.net/problem/11062
11062번: 카드 게임
근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는
www.acmicpc.net
N * N * 2 크기의 배열로 게임의 현재상태를 표현할 수 있어요 스스로 배열을 정의해보는 훈련을 해봅시다.
https://www.acmicpc.net/problem/2098
2098번: 외판원 순회
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j
www.acmicpc.net
비트필드로도 상태를 표현 할 수 있어요 해당 문제의 배열을 정의해봅시다.
-----------------------------------------------------------------------------------------------------------------------------------
질문은 언제나 환영합니다.