공부하자

1520번: 내리막 길 (acmicpc.net) 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 배열을 순차적으로 순회하는 게 아니라 사방으로 움직이며 연산이 진행되기 때문에, DFS/BFS + DP의 조합으로 문제를 풀어야 한다. 1. DFS: 현재 지점에서 접근할 수 있는 곳의 모두 경우의 수를 더해가며, 출발점으로 되돌아온다. dp를 0으로 초기화하면, 경우의 수가 0일 때와 혼동되므로 -1로 초기화한다. 현재 지점을 이미 방문했다면 더 DFS를 들어갈 필요 없이 현재 저장된 D..

11722번: 가장 긴 감소하는 부분 수열 (acmicpc.net) 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 다이나믹 프로그래밍 문제이다. 두 가지 방식으로 풀 수 있다. 이중 for문: 현재 인덱스와 그 앞에 있는 모든 수를 비교한다. O(N^2) bisect 사용: 반복문 안에서 이진탐색을 수행한다. O(NlogN) 1. dp 배열에 현재 수를 포함해 만들 수 있는 수열의 길이를 저장한다. 앞에 있는 어떤 수가 현재 수 보다 ..