공부공간

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net N번째 큰수를 구하기위해서 N^2의 배열을 선언한다 메모리제한이 12mb이므로 1500*1500*4 = 9mb를 사용하고 index의 최댓값을 저장할 일차원배열을 선언한다. N번 돌면서 일차원 배열의 최댓값을 구하고 그 인덱스를 하나 줄여준다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTo..

문제 해결 접근 별로 어렵지 않은 형태의 기본적인 동적 프로그래밍의 문제로 보인다. 입력받은 점수 행렬은 3개의 열을 가지며 항상 최대, 최소 값을 갱신하도록 알고리즘을 설계하여 준다. 해당 문제의 점화식은 다음과 같다. minDP[i][0] = min(minDP[i-1][0] , minDP[i-1][1]) + map[i][0] minDP[i][1] = min(minDP[i-1][0], min(minDP[i-1][1], minDP[i-1][2])) + map[i][1] minDP[i][2] = min(minDP[i-1][1] , minDP[i-1][2]) + map[i][2] 한 행이 진행 될때마다, 이전 행렬의 합산 값을 비교하여 최소 혹은 최대의 값과 현재 행렬의 값을 더해준다. 따라서 다음과 같이 ..

3중 for 문을 활용하여 풀어야 하는 동적 프로그래밍 문제이다. 파일은 연속되는 것들만 합치기가 가능하며, 파일을 계속 합치며 도출 되는 비용이 최소가 되도록 알고리즘을 구성해야 한다. 알고리즘 풀이에 쓰이는 배열 1. dp[i][j] 배열은 i 부터 j 장까지 최소 비용이라고 정의하고, 첫 번째 장부터 마지막 장까지 최소 비용의 값을 갱신하며 값을 도출한다. 이러한 정의로 다음과 같은 점화식을 도출할 수 있다. 2. cost[i] 배열은 주어진 파일을 합치는 비용을 저장하는 배열이다. 3. sum[i] 배열은 i 까지의 파일을 합하는데 필요한 비용을 나타낸다. 예를 들어, 첫 번째 경우 예제 입력에서 주어진 값을 사용한다면, sum[2] = 70 이고 sum[i] = sum[i-1] + cost[i]..

주어진 상자의 크기가 위와 같이 각각 1, 5, 2, 3, 7 의 경우 1, 2, 3, 7 의 크기 차례로 상자에 넣을 수 있다. 예제의 경우 8개의 상자 크기가 주어질 때 1, 2, 3, 5, 6 의 순으로 상자를 넣는 것이 가장 많은 상자의 개수를 출력하게 된다. 따라서, 해당 문제는 가장 긴 부분 수열과 같은 방법으로 해결하는 문제이다. 가장 긴 부분 수열을 구하는 문제와 같이, 2중 for 문을 활용하여 인덱스 마다 상자를 넣을 수 있는 최대 개수를 갱신하는 DP 알고리즘을 통하여 문제 해결이 가능하다.

https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net DP는 너무나도 어려운것 같다. 점프는 맵에 표시된 수만큼 오른쪽과 아래로 점프한다. 최종 목적지까지 가는 경로를 찾아주면된다. 중간에 한 지..

준규는 1,1 에서 출발하여 주어진 N,M 까지 이동하며 이동하는 칸의 사탕을 가져간다. N,M 칸에 도달할 때 준규가 가질수 있는 최대의 사탕 개수를 도출하는 문제이다. 해당 문제의 접근법은 다음과 같다. 1. 이동하는 방법은 오른쪽, 아래, 오른쪽 대각선으로 정해져 있다. 2. 준규가 이동할 수 있는 미로 칸마다 사탕을 가져올 수 있는 최대값을 갱신하며 진행한다. 3. 최대값을 갱신할 때, 위 칸에서 내려오는 경우, 대각선 칸에서 내려오는 경우, 왼쪽 칸에서 오는 경우를 비교한다.

BOJ - 2293) 동전 1의 변형 문제이다. 동전 1의 경우, 주어진 금액을 나타내는 최대의 경우의 수를 출력하는 반면 동전 2의 경우 최소 경우의 수로 해당 금액을 나타내는 문제이다. 주의하여 생각해야할 점은 동전 1과 큰 차이가 없다. 1. 동전 1과 같이, 동전의 종류 별 경우의 수를 갱신한다. 2. 경우의 수를 갱신할 때, 배열 d 의 인덱스 값보다 적은 가치의 동전만을 생각한다. 3. 기존의 배열 d의 값과, 도출된 d 의 값을 비교하여, 적은 값을 선택한다. 4. 주어진 k 값이 도출되지 않을 경우(값이 갱신되지 않았을 경우) -1 을 출력한다. d[j] 의 값을 갱신할 때마다 기존의 d[j] 의 값과 배열에서 동전의 가치만큼 뺀 뒤 1을 더해준 값과 비교하여 더 작은 값을 갱신하고, 값이..

특정 금액을 다른 가치를 가진 동전으로 나타낼수 있는 최대 경우의 수를 구하는 문제이다. 기본적인 유형의 동적 프로그래밍 문제이다. 2중 for 문을 사용하여, 주어진 동전의 가치만을 사용할 때의 경우만 생각하며 일정 금액보다 사용할수 있는 동전의 가치가 낮은 경우, 동전의 가치를 뺀 경우의 수를 더하여 갱신함으로써 문제를 해결한다. ex) 4원을 위의 예제 입력으로 나타내는 경우, 예제의 1원만 사용할 경우를 생각하여 배열에 값을 갱신한다. i = 1) d[1]~d[4] = 1 i = 2) d[1] = 1, d[2] 의 경우 입력된 동전의 가치보다 크거나 같기 때문에, 기존의 d[2] 배열에 가지수를 추가하여 준다. d[4] = d[4](1로만 나타낸 경우의 수) + d[2](1과 2, 2로만 나타낸 ..