문제 www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 풀이 간단한 DP문제이지만 수열의 길이가 1인 경우의 예외 처리가 실수를 유발하는 듯하다. 우리가 현재의 숫자에서 확인해야 하는 것은 3가지 경우이다. 1. 다음 숫자가 더 큰 경우 2. 다음 숫자가 더 작은 경우 3. 다음 숫자와 같은 경우 본인의 경우 수열의 마지막 숫자부터 처음 숫자로 가는 역순으로 구성하였다. cache값을 2차원 배열(cache[100000][2])로 선언하여 cache[idx][0]..

문제 www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 풀이 Top_bottom 풀이 해당 순서(order)의 설정된 볼륨(volume)에서 다음 볼륨의 설정 값을 더하거나 빼주는 경우로 분기한다. 이때 두 가지 분기의 결과 중 더 큰 값을 저장하여 같은 값의 연산을 방지해준다. 모든 순서에서의 볼륨값을 탐색하여도 시간 복잡도는 O(NM)이므로 충분히 시간 안에 계산이 가능하다. 만약 현재의 볼륨에서 다음 설정 값으로 모두..

문제 www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 풀이 간단한 DP문제로 간단한 점화식 dp[r][c] = dp[r-1][c] + dp[r][c-1] 으로 경로의 수를 계산할 수 있다. k가 0인 경우와 아닌 경우만 나누어 k가 0이 아니라면 두 가지 문제로 분할해서 계산된 값들을 곱해주면 된다. 하지만 본인의 경우, 아래와 같은 실수로 애먹었다. 경유지인 행, 열 위치 계산을 아래와 같이 진행한다면 큰 오류가 발생한..

문제 www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍 문제이지만 메모이제이션을 적용할 방법이 떠오르지 않아 답을 봐버렸다... 해당 문제는 (r,c)위치가 1이라면 (r-1,c-1), (r-1,c), (r,c-1)위치를 확인하여 가장 작은 값 +1이 (r,c)에서의 가장 큰 정사각형의 변의 길이이다. 즉, 해당 위치를 오른쪽 아래 모서리로 삼는 가장 큰 정사각형의 길이를 저장한다. 이러한 연산을 모든 배열 값에 대해 실행해주면 이전의 값을 사용하여 빠르게 답을 구할 수 있다. 아래와 같은 예제로 예를 들..

문제 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 다이나믹 프로그래밍 문제. 만약 상근이가 0이상 20이하의 수만을 안다는 제한이 없다면 메모제이션할 양이 너무나 커서 구현할 수 없었을 것이다. 상근이는 0이상 20이하의 수 만을 다룰 수 있기 때문에 다음 수와 의 +나 -결과가 범위를 벗어난다면 계산을 진행할 필요가 없었다. 메모이제이션 기법으로 최적화하기 위해서는 어떤 값들이 중복 계산되는지 알아야한다. 아래와 같은 예제가 ..

문제 www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 다이나믹 프로그래밍과 DFS가 결합된 문제이다. 메모이제이션으로 값을 재사용하는 최적화를 하기 위해서는 어떤 부분에서 중복된 계산이 이루어지는지 확인해야 한다. 해당 문제에서 DFS로 시작점에서 더 작은 수로 재귀 호출을 한다고 해보자. 문제에서 주어진 예제는 아래와 같다. 출발점인 50에서 45로 분기하였다고 가정하면 32에서 20이나 30으로 진행하는 두 가지 경로로 나뉜다. 해당 호출들에서는 아래와 ..

문제 www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이 해당 문제는 다이나믹 프로그래밍 문제이다. 본인의 경우 여기에 BFS기법을 추가해서 문제를 해결했다. 일단 입력으로 받는 동전의 값이 10,000 이하의 수 일 때만 coin_value에 그 값을 저장한다. 가치의 합은 최대 10,000이기 때문에 그 이상의 값은 문제를 해결하는데 전혀 도움이 되지 않기 때문이다. 이후 coin_value를 정렬하고 BFS를 구현한다. ..

문제 https://algospot.com/judge/problem/read/WILDCARD algospot.com :: WILDCARD Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 algospot.com 풀이 다이나믹 프로그래밍 문제이지만, 단순히 메모이제이션을 적용할 수 없어서 어려웠다. 풀이는 알고리즘 문제 해결 전략(일명 종만북)을 참조하였다. 와일드 카드(wild_card)와 파일명(file_name)을 한 글자씩 비교하여 진행할 경우 글자가 같은 경우와 와일드 카드의 ? 문자는 다음 칸으로 넘어가는 것으로 간단히 구현이 가능하다. 하지만 와일..

문제 www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 다이나믹 프로그래밍 문제이므로 일단 직관적인 top-down 방식으로 풀어보았다. 메모이제이션을 위한 배열 max_stair[300][2] 선언하는데 2차원으로 선언하는 이유는 해당 위치가 직전 계단과 연속되는지를 저장하기 위해서이다. max_stair[ ][ 0 ] 에는 두 계단을 뛰어 연속되는 계단이 없는 경우를, max_stair[ ][ 1 ] 에는 한 계단만 올라가 이전의 계단과 연속되는 경우를 저장한다...

문제 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 전형적인 다이나믹 프로그래밍 문제이다. 이런 문제의 특징인 부르트 포스로 모두 계산하기에는 경우의 수가 너무 많다. 이러한 경우의 수들 중 중복계산을 수도 없이 호출하기 때문에 우리는 계산된 값들을 저장하여 최적화를 할 수 있다. 해당 문제에서 모든 집들을 단순히 3가지 색으로 칠하는 경우의 수는 3^1000 이므로 시간 초과가 발생한다. 하지만 메모이제이션으로, 해당 순서의 집..