JUINTINATION
프로그래머스 코딩테스트 고득점 Kit - 동적계획법(N으로 표현, 정수 삼각형, 등굣길, 사칙연산, 도둑질) 본문
프로그래머스 코딩테스트 고득점 Kit - 동적계획법(N으로 표현, 정수 삼각형, 등굣길, 사칙연산, 도둑질)
DEOKJAE KWON 2024. 12. 25. 22:241번 문제: N으로 표현
https://school.programmers.co.kr/learn/courses/30/lessons/42895
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있다.
- 12 = 5 + 5 + (5 / 5) + (5 / 5)
- 12 = 55 / 5 + 5 / 5
- 12 = (55 + 5) / 5
5를 사용한 횟수는 각각 6,5,4 이고, 이중 가장 작은 경우는 4이다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성해야 한다. 여기서 최솟값이 8보다 크면 -1을 return해야 한다.
접근
12 = 55 / 5 + 5 / 5 에서 55처럼 N이 여러 개 붙여서 들어갈 수 있다. DP 처음 문제라서 간단한 탑다운 혹은 바텀업 코드를 작성하는 것으로 예상했는데.. 아니었다. 예를 들어 N이 5일 때 5 / 5로 1을 만들고, 그 뒤에 5를 붙여서 15를 만들 수 없어서 탑다운이나 바텀업같은 방식으로 문제를 해결할 수 없다.
그러면 어떻게 해야할까? 도저히 감이 안 잡혀서 구글링을 좀 해봤다. 지금까지 내가 DP 알고리즘 문제를 풀 때와 전혀 다른 방식으로 풀 수 있는데, N을 x번 사용하여 만든 숫자를 x번 Set에 저장하는 것이다.
먼저 1번부터 8번까지 저장할 수 있는 Set<Integer>[] 배열 setArr을 만들고, 각각을 초기화한다. 이후에 각각의 x번 Set에 N을 x번 붙여서 만든 수를 넣는다. 예를 들어 N이 5이고, x가 3이라면 3번 setArr[3]에 555를 넣는 것이다.
이렇게 초기화를 한 이후에 i와 j를 사용하는 이중 for문에서 j는 1부터 i - 1까지 돌며 setArr[j]에 있는 값들과 setArr[i - j]에 있는 값들에 대해 사칙 연산을 진행하여 setArr[i]에 add하는 과정을 거친다.
이후에 setArr[i]에 number가 들어있다면 사용횟수만 구하면 되기 때문에 i를 반환하고, i가 8까지 다 돈 이후에도 number가 포함된 Set이 없다면 마지막 -1를 반환한다.
코드
import java.util.*;
class Solution {
public int solution(int N, int number) {
if (N == number) return 1;
Set<Integer>[] setArr = new Set[9];
for (int i = 1; i <= 8; i++) {
setArr[i] = new HashSet<>();
Set<Integer> set = setArr[i];
StringBuilder sb = new StringBuilder();
for (int j = 0; j < i; j++) {
sb.append(N);
}
set.add(Integer.parseInt(sb.toString()));
}
for (int i = 2; i <= 8; i++) {
Set<Integer> set = setArr[i];
for (int j = 1; j < i; j++) {
for (int a : setArr[j]) {
for (int b : setArr[i - j]) {
set.add(a + b);
set.add(a - b);
set.add(a * b);
if (b != 0) {
set.add(a / b);
}
}
}
}
if (set.contains(number)) {
return i;
}
}
return -1;
}
}2번 문제: 정수 삼각형
https://school.programmers.co.kr/learn/courses/30/lessons/43105
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 한다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능하며, 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능하다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성해야 한다.
접근
익숙한 형태의 탑다운 방식 혹은 바텀업 방식을 사용하는 DP 문제이다. 나는 재귀를 사용하는 탑다운 방식을 채택했다.
먼저 Integer[][] 타입의 dp 배열은 dp[x][y]일 때 x 깊이의 y 인덱스까지의 최대값을 의미한다. 그리고 dynamicTriangle이라는 메서드는 triangle 배열과 깊이를 의미하는 dpth, 그리고 인덱스를 의미하는 idx를 매개변수로 갖으며, triangle.length - 1부터 시작하여 0까지 내려오게 된다. 이 재귀 함수가 끝나는 조건을 걸지 않았는데, 그 이유는 dp[dpth][idx]가 null이 아니면 그대로 dp[dpth][idx] 값을 반환하게 되는데, dp[0][0]은 삼각형의 맨 위에 있는 수가 최댓값이 될 수 밖에 없기 때문에 dp[0][0] = triangle[0][0]으로 초기화하고, dpth가 0, idx가 0이 되면 자연스럽게 dp[0][0]이 반환되고 함수가 종료되기 때문이다.
맨 아래에서부터 위로 올라오기 때문에 갈 수 있는 경로는 (dpth, idx)에서 (dpth - 1, idx)와 (dpth - 1, idx - 1)이다. 그런데 dp[dpth - 1].length는 idx보다 작을 경우도 있고, idx가 0일 경우도 있을 것이다. 그래서 이에 대한 조건문을 적용해야 한다.
그래서 결론적으로 dp[dpth][idx]가 null이라면 triangle[dpth][idx]에 dynamicTriangle(triangle, dpth - 1, dp[dpth - 1].length > idx ? idx : idx - 1)와 dynamicTriangle(triangle, dpth - 1, idx > 0 ? idx - 1 : 0) 중 더 큰 값을 재귀적으로 내려가며 더한다.
마지막으로 for문에서 0부터 triangle.length - 1까지 순회하는 i에 대해서 dynamicTriangle(triangle, triangle.length - 1, i)를 실행하고, 0부터 시작하는 answer와 dp[triangle.length - 1][i]의 값을 비교하여 더 큰 값을 answer에 넣고 마지막에 answer를 반환한다.
코드
class Solution {
Integer[][] dp;
public int dynamicTriangle(int[][] triangle, int dpth, int idx) {
if (dp[dpth][idx] == null) {
dp[dpth][idx] = triangle[dpth][idx] + Math.max(
dynamicTriangle(triangle, dpth - 1, dp[dpth - 1].length > idx ? idx : idx - 1),
dynamicTriangle(triangle, dpth - 1, idx > 0 ? idx - 1 : 0)
);
}
return dp[dpth][idx];
}
public int solution(int[][] triangle) {
dp = new Integer[triangle.length][];
for (int i = 0; i < triangle.length; i++) {
dp[i] = new Integer[triangle[i].length];
}
dp[0][0] = triangle[0][0];
int answer = 0;
for (int i = 0; i < triangle.length; i++) {
dynamicTriangle(triangle, triangle.length - 1, i);
answer = Math.max(answer, dp[triangle.length - 1][i]);
}
return answer;
}
}3번 문제: 등굣길
https://school.programmers.co.kr/learn/courses/30/lessons/42898
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
계속되는 폭우로 일부 지역이 물에 잠겨서 물에 잠기지 않은 지역을 통해 학교를 가려고 한다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있으며, 아래 그림은 m = 4, n = 3 인 경우이다.
가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타낸다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어질 때 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해야한다.
접근
문제의 예시를 그림으로 나타내면 아래와 같다.
위의 문제와 마찬가지로 탑다운 방식을 사용했다. 탑다운 방식을 사용하면 가독성이 좋고, 생각하기 쉽다는 이유도 있지만, 바텀업 방식을 사용하면 (x, 1) 또는 (1, x)에 물 웅덩이가 있을 때 dp 배열의 초기값을 잡기 애매해지는 것도 이유가 될 수 있다.
먼저 Integer[][] 타입의 dp 배열은 dp[x][y]일 때 (1, 1)부터 (x, y)까지 최단 거리로 올 수 있는 경우의 수를 의미한다. (0, 0)부터 시작하지 않기 때문에 dp 배열은 new Integer[m + 1][n + 1]로 초기화하고, dynamicSchoolWay 메서드는 m이 0이거나 n이 0일 때(이동할 수 없는 경로일 때) 0을 반환한다. 그리고 시작점인 (1, 1)은 갈 수 있는 경로가 1개이므로 m과 n이 모두 1이면 1을 반환하도록 설정했다.
위의 문제와 다르게 dp 배열을 먼저 초기화하지 않은 이유는 그냥 코드가 쓸데없이 지저분해보일까봐 그런 것이고, 딱히 큰 의미는 없다. 그래도 puddles 배열에 대해서는 초기화해주어야 하는데, 물 웅덩이가 있다면 갈 수 없으니 puddles에 있는 모든 배열 puddle에 대해 dp[puddle[0]][puddle[1]]은 0으로 초기화해준다.
이후 마지막에 dynamicSchoolWay(m, n)을 반환하는데, 해당 메서드에서 dp[m][n]이 null이라면 dp[m][n] = dp[m][n] = (dynamicSchoolWay(m - 1, n) + dynamicSchoolWay(m, n - 1)) % MOD로 초기화한 후 재귀적으로 반환하는 과정을 거친다.
코드
class Solution {
public final int MOD = 1000000007;
public Integer[][] dp;
public int dynamicSchoolWay(int m, int n) {
if (m == 0 || n == 0) {
return 0;
}
if (m == 1 && n == 1) {
return 1;
}
if (dp[m][n] == null) {
dp[m][n] = (dynamicSchoolWay(m - 1, n) + dynamicSchoolWay(m, n - 1)) % MOD;
}
return dp[m][n];
}
public int solution(int m, int n, int[][] puddles) {
dp = new Integer[m + 1][n + 1];
for (int[] puddle : puddles) {
dp[puddle[0]][puddle[1]] = 0;
}
return dynamicSchoolWay(m, n);
}
}4번 문제: 사칙연산
https://school.programmers.co.kr/learn/courses/30/lessons/1843
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않는데, 예를 들어 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나온다.
- (((1 - 3) + 5) - 8) = -5
- ((1 - (3 + 5)) - 8) = -15
- (1 - ((3 + 5) - 8)) = 1
- (1 - (3 + (5 - 8))) = 1
- ((1 - 3) + (5 - 8)) = -5
위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, -5, -5, 1, 1]이 되며, 이중 최댓값은 1이다. 문자열 형태의 숫자와, 더하기 기호("+"), 뺄셈 기호("-")가 들어있는 배열 arr가 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 return 하도록 solution 함수를 완성해야 한다.
접근
처음에 감이 아예 안 잡혀서 질문 목록에 있던 사칙연산 해설 글을 참고했다. 이 글에 나온대로 처음에 연산 기호를 스택에 넣고 dfs를 사용하면 되지 않을까 싶었는데, 배열 초기화도 애매하고, 빼기 연산이 나올 경우에 마냥 최댓값을 저장하는 dp 배열을 만든다면 "어떤 최댓값 - 그보다 더 큰 어떤 최댓값"이 된다면 음수가 나오면서 최댓값이 저장이 안 될 수가 있어서 중간에 멘붕이 왔던 것 같다.
그래서 빼기 연산이 있을 때를 대비해서 최솟값을 저장하는 dp 배열이 추가로 필요하다. 이 문제는 dp 배열 초기화와 같이 위와 같은 문제로 인해 탑다운 방식이 아닌 바텀업 방식을 사용했으며, int[][] 배열 maxDP와 minDP는 mDP[x][y]에 대해 x번째 숫자부터 y번째 숫자까지 연산했을 때의 각각 최댓값과 최솟값을 의미한다.
maxDP의 모든 값은 Integer.MIN_VALUE로, minDP의 모든 값은 Integer.MAX_VALUE로 초기화하고, 매개변수로 주어진 arr에 대해 숫자와 연산기호를 분리하기 위해 List<Integer> 타입의 numbers 리스트와 List<Character> 타입의 operators 리스트를 만들어 짝수 번째에 있다면 숫자, 홀수 번째에 있다면 연산기호로 분리하여 삽입한다.
그리고 x부터 x까지 연산한 최댓값은 당연히 x번째 숫자이므로 for문에서 0부터 arr에 있는 숫자의 개수를 의미하는 n까지 순회하는 i에 대해 maxDP[i][i] = minDP[i][i] = i로 초기화한다.
마지막의 삼중 for문에서 step은 현재 고려하고 있는 부분 문제의 길이를, i는 현재 부분 문제의 시작 인덱스를, j는 i + step으로 현재 부분 문제의 끝 인덱스를, k는 연산자를 나누는 분할점의 인덱스를 의미한다.
operators에 있는 k번째 연산기호에 대해 더하기라면 maxDP[i][j] = Math.max(maxDP[i][j], maxDP[i][k] + maxDP[k + 1][j])로, minDP[i][j] = Math.min(minDP[i][j], minDP[i][k] + minDP[k + 1][j])로 초기화한다.
그런데 여기서 빼기라면 maxDP[i][j] = Math.max(maxDP[i][j], maxDP[i][k] - minDP[k + 1][j])로, minDP[i][j] = Math.min(minDP[i][j], minDP[i][k] - maxDP[k + 1][j])로 초기화해야 한다. 최댓값을 저장하는 dp 배열에는 max - min을, 최솟값을 저장하는 dp 배열에는 min - max를 저장해야 하는 것이다.
마지막에 처음부터 끝까지 계산했을 때의 최댓값을 의미하는 dp[0][n - 1]을 반환한다.
코드
import java.util.*;
class Solution {
public int solution(String arr[]) {
int n = arr.length / 2 + 1;
int[][] maxDP = new int[n][n];
int[][] minDP = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
maxDP[i][j] = Integer.MIN_VALUE;
minDP[i][j] = Integer.MAX_VALUE;
}
}
List<Integer> numbers = new ArrayList<>();
List<Character> operators = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (i % 2 == 0) {
numbers.add(Integer.parseInt(arr[i]));
} else {
operators.add(arr[i].charAt(0));
}
}
for (int i = 0; i < n; i++) {
maxDP[i][i] = numbers.get(i);
minDP[i][i] = numbers.get(i);
}
for (int step = 1; step < n; step++) {
for (int i = 0; i < n - step; i++) {
int j = i + step;
for (int k = i; k < j; k++) {
char op = operators.get(k);
if (op == '+') {
maxDP[i][j] = Math.max(maxDP[i][j], maxDP[i][k] + maxDP[k + 1][j]);
minDP[i][j] = Math.min(minDP[i][j], minDP[i][k] + minDP[k + 1][j]);
} else {
maxDP[i][j] = Math.max(maxDP[i][j], maxDP[i][k] - minDP[k + 1][j]);
minDP[i][j] = Math.min(minDP[i][j], minDP[i][k] - maxDP[k + 1][j]);
}
}
}
}
return maxDP[0][n - 1];
}
}5번 문제: 도둑질
https://school.programmers.co.kr/learn/courses/30/lessons/42897
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
어떤 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있으며, 도둑이 이 마을을 털 계획을 하고 있다.
각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울리고, 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성해야 한다.
접근
money 배열의 길이를 n이라고 할 때 맨 처음 번호의 집(0번 집)과 맨 마지막 번호의 집(n - 1)은 동시에 털 수 없다. 그래서 무조건 맨 마지막 집을 털지 않는 경우와 터는 경우를 나누기 위해 dpExcludeLast 배열과 dpIncludeLast 배열을 만들었다. 두 배열은 모두 dp[x]에 대해 0번부터 x번까지 집을 돌았을 때 털 수 있는 돈의 최댓값을 의미한다.
dpExcludeLast 배열은 마지막 집을 털지 않으므로 처음 집을 털 수 있다. 따라서 dpExcludeLast[0]은 money[0]이다. 또한 예를 들어 n이 5일 때 5번 집을 털지 않을 때 1번과 4번 집을 털 수도 있고, 1번과 3번, 그리고 2번과 4번을 털 수 있다. 옆집은 방문할 수 없으므로 2씩 빼면서 값을 더해갈텐데 만약 1번 집의 값이 2번보다 크고, 4번 집의 값이 3번 집의 값보다 크다면 2씩 빼면서 값을 더해가는 연산으로는 4번 집과 1번 집의 값을 더할 수 없으므로, 2번(1번 인덱스) 집에 대해 dpExcludeLast[0]를 1번 집(0번 인덱스)과 2번(1번 인덱스) 집 중 값이 더 큰 값으로 초기화한다.
dpIncludeLast 배열은 마지막 집을 터는 경우이므로 처음 집을 털 수 없다. 그래서 1번(0번 인덱스) 집에 대한 dpIncludeLast[0]을 0으로 초기화하고, dpIncludeLast[1]은 money[1]이다. 위의 이유와 마찬가지로 dpIncludeLast[2]는 money[1]과 money[2] 중 더 큰 값으로 초기화한다.
이후 각각에 대해 dpExcludeLast[n - 2]과 dp[IncludeLast[n - 1]을 구한 뒤에 둘 중 더 큰 값을 반환한다.
코드
class Solution {
public int solution(int[] money) {
int n = money.length;
int[] dpExcludeLast = new int[n - 1];
dpExcludeLast[0] = money[0];
dpExcludeLast[1] = Math.max(money[0], money[1]);
for (int i = 2; i < n - 1; i++) {
dpExcludeLast[i] = Math.max(money[i] + dpExcludeLast[i - 2], dpExcludeLast[i - 1]);
}
int[] dpIncludeLast = new int[n];
dpIncludeLast[0] = 0;
dpIncludeLast[1] = money[1];
dpIncludeLast[2] = Math.max(money[1], money[2]);
for (int i = 3; i < n; i++) {
dpIncludeLast[i] = Math.max(money[i] + dpIncludeLast[i - 2], dpIncludeLast[i - 1]);
}
return Math.max(dpExcludeLast[n - 2], dpIncludeLast[n - 1]);
}
}결론
1번 문제부터 Set을 사용하는 DP 문제라니.. 지금까지 백준 문제를 풀면서 한 번도 경험하지 못 했던 유형이라 너무 당황스러웠고, 알고리즘의 세계는 무궁무진하다는 것을 깨달았다.
그리고 마지막 문제에서 처음에 아래와 같이 탑다운 방식을 사용했었다.
class Solution {
public int dynamicSteal(int[] money, Integer[] dp, int idx) {
if (idx < 0) {
return 0;
}
if (dp[idx] == null) {
dp[idx] = Math.max(
money[idx] + dynamicSteal(money, dp, idx - 2),
dynamicSteal(money, dp, idx - 1)
);
}
return dp[idx];
}
public int solution(int[] money) {
int n = money.length;
Integer[] dpExcludeLast = new Integer[n - 1];
dpExcludeLast[0] = money[0];
dpExcludeLast[1] = Math.max(money[0], money[1]);
dynamicSteal(money, dpExcludeLast, n - 2);
Integer[] dpIncludeLast = new Integer[n];
dpIncludeLast[0] = 0;
dpIncludeLast[1] = money[1];
dpIncludeLast[2] = Math.max(money[1], money[2]);
dynamicSteal(money, dpIncludeLast, n - 1);
return Math.max(dpExcludeLast[n - 2], dpIncludeLast[n - 1]);
}
}해당 문제에 질문도 남기긴 했는데, 이 코드는 정확성 테스트는 모두 통과했지만, 효율성 테스트에서 모두 "런타임 에러"가 발생한다. 같은 로직의 바텀업 방식을 사용한 코드는 통과하는 것을 보면 아마 StackOverflowError 문제인 것 같은데..
어쨌든 바텀업 방식으로만 풀어야 하는 DP 문제들도 많으니 이 방식도 열심히 연습해야겠다는 생각이 들었다.