💻관련 알고리즘 문제
DP(동적프로그래밍)이란?
피보나치 수열
동적 계획법의 등장 배경은 피보나치 수열을 통해 알 수 있다. 피보나치 수열은 제2항까지는 1이고 제3항부터 바로 앞의 두 항을 더한 수로 정의된다.
프로그래밍에서 피보나치 수열은 보통 재귀를 통해 표현한다.
int fibo(int n)
{
if (n<=2)
return 1;
else
return fibo(n-1) + fibo(n-2);
}요런식으로 말이다!
그런데 이 코드는 상당히 비효율적인 코드라고 할 수 있다.
왜냐하면 fibo(6)을 실행한다고 할 때 fibo(4)와 fibo(3), fibo(2),fibo(1)이 여러번 실행되는데 어차피 이들은 모두 같은 결과를 내기 때문이다.
📚동적계획법의 개념과 원리
위의 예시처럼 이미 했던 연산이 반복되는 결점을 보완하기 위해서 동적계획법이 고안되었다.
원리는 처음 진행되는 연산은 기록해두고, 이미 진행했던 연산이라면 다시 연산하는 것이 아니라 기록되어 있는 값을 가져오는 것이다.
따라서 동적 계획법에 따른 피보나치 수열을 구하는 함수는 다음과 같다.
int fiboData[100] = {0,};
int fibo(int n)
{
if (n<=2) //fibo(1)과 fibo(2)는 1로 저장
return 1;
if (fiboData[n]==0) //fibo(3)부터 만약 값이 저장되어있지 않다면 이전의 두 결과값을 더한 값으로 값 새로 저장
fiboData[n] = fibo(n-1) + fibo(n-2);
return fiboData[n];
}이런식으로 구현을 하게 되면 만약 연산값이 존재한다면 굳이 다시 계산하는 것이 아니라 바로 fiboData를 통해 해당 값을 반환하게 된다. 중복연산이 사라진다는 엄청난 성능상 이점이 있다!
🌟동적프로그래밍의 핵심
동적 계획법은 문제를 풀 때 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해 최종 목적에 도달하는 방식의 알고리즘이다
메모이제이션(Memoziation)
동일한 문제를 반복해야 할 경우, 한 번 계산된 결과를 저장해 두었다가 활용하는 방식으로 중복 계산을 줄이는 것을 메모이제이션이라고 한다.
📌동적프로그래밍의 활용
앞서 여러 차례 강조했다 시피 동적프로그래밍을 써야하는 상황은
- 반복되는 계산이 존재한다.
- 하나의 값이 이전의 값들의 영향을 받아 결정된다.
- 정해진 특정 값은 변하지 않고 고정적이다.
할 경우에 사용할 수 있다.
1. 조합(Combination) 경우의 수 구하기
조합의 경우의 수를 구할 때 우리가 흔히 위와 같은 공식을 알고 있다.
하지만 여기서 조합의 성질을 이용하여 변형식을 만들어내면 위에서 언급한 동적프로그래밍을 활용할 수 있는 조건으로 식이 바뀌게 된다.
다음과 같이 이전의 값들이 다음 값의 결과에 영향을 주고 aCb의 형태의 값은 불변하다.
동적프로그래밍을 쓰기에 최적의 조건이 되었다!
이제 각 조건을 반영한 동적프로그래밍 알고리즘만 구현해주면 된다 😇 어렵지 않다.
int[][] dp = new[a][b]; // 각 aCb에서 a와 b에 해당하는 최대값을 적으면 된다
main() {
int T = input(); // 반복횟수
for(int i = 0; i < T; i++) {
int N = input();
int M = input();
// M개중 N개를 뽑는 경우이므로 nCr 에서 n = M, r = N이다.
print(combi(M, N));
}
}
int combi(int n, int r) {
// 이미 탐색했던 경우 바로 반환
if(dp[n][r] > 0) {
return dp[n][r];
}
// 2번 성질
if(n == r || r == 0) {
return dp[n][r] = 1;
}
// 1번 성질
return combi(n - 1, r - 1) + combi(n - 1, r);
}2. 숫자 덧셈 조합 구하기
숫자 덧셈 조합이란 예를 들어 1,2,3 숫자를 활용해서 4를 만드는 덧셈식을 구하는 문제이다.
3+1 ,1+1+1+1, 2+1+1, 1+2+1
2+2, 1+1+2
1+3
다음 7개의 경우의 수를 구해낼 수 있다.
그런데 잘 따지고 보면 이러한 숫자 조합 덧셈에는 규칙이 존재한다.
dp[n]을 1,2,3을 가지고 n을 만들 수 있는 숫자 조합 덧셈의 경우의 수라고 할 때,
dp[1] = 1, dp[2] = 2 dp[3] = 4이다.
여기서 위의 4를 만드는 식들을 자세히 들여다보면 뭔가 규칙이 보일 것이다.
첫째 줄은 각 식에서 마지막 +1을 제외하고는 모두 3을 만드는 4가지 경우의 수고
두번째 줄은 각 식에서 마지막 +2를 제외하고는 모두 2를 만드는 2가지 경우의 수이며
마지막 줄은 마찬가지로 주어진 식에서 +3을 제외하면 1을 만드는 1가지 경우의 수이다.
이는 5,6,그리고 그 어떤 수에도 적용이 된다.
덧셈 조합 숫자의 범위가 3이기 때문에 이 패턴은 결국 dp[n] = dp[n-3]+dp[n-2]+dp[n-1]로 반복된다.
3. 1로 만들기
왜... 왜.. 혹시 메모제이션 쓰나? 했다가 에이 아니네 하고 넘겼던걸까..이 망충아..
백준 1로만들기와 같이 어떤 수에서 연산을 해서 1로 만드는 연산의 최소횟수는 그 수에 따라 고정되어있고 큰 수에서 작은 수로 연산해나가면서 계속 기존의 계산값의 영향을 받는 것인데 ㅠㅠㅠㅠㅠㅠ
4. RGB거리
문제에서 말도 안되게 적은 시간을 요구하면 일단 메모제이션을 쓴다고 보는게 맞다..
혹시.? 에이 아니겠지 하고 넘기지 말고 끈질기게 메모제이션으로 어떻게 구현할 수 있을지 고민해야 한다.
대충 보고 저장되어 누적되는 값이 없다고 넘기지 말자.... 😥
