[알고리즘] 대표적인 DP 문제들에 대한 알고리즘과 수도코드 - 점화식 기초

면접 준비 용으로 대표적인 알고리즘 문제들을 풀어보려 한다.

비전공자들을 대상으로 보는 면접이라 생각하고, 어려운 문제는 제외했다.

문제가 길지 않고 간단하며, 정답 수도코드도 짧게 나올 수 있는 문제 위주로

 

---

 

1. 피보나치 수열

문제: https://www.acmicpc.net/problem/2748

코드:

// 재귀
int fibo(int n) {
	if(n==1) return 0;
    else if(n==2) return 1;
    else return (fibo(n-1) + fibo(n-2));
}

// 반복문
int fibo2(int n) {
	int f[n];
    f[0] = 0;
    f[1] = 1;
    if (n>1) {
    	for(i in 2~n-1) {
        	f[i] = f[i-1] + f[i-2];
        }
    }
    return f[n-1];
}

- 반복문으로 하는 게 시간 효율은 더 좋다. 하지만 나한테 직관적인 건 재귀인 것 같다.

 

2. 1 2 3 더하기

문제: https://www.acmicpc.net/problem/2579

코드:

int add(int n) {
	int d[n];
    int d[0] = 1;
    int d[1] = 2;
    int d[2] = 4
    for (i in 3~n-1) {
    	d[i] = d[i-1] + d[i-2] + d[i-3];
    }
    return d[n-1];
}

- 위와 비슷한 점화식 문제. 위와 동일한 이유로 반복문만 찾았습니다.
- 원리
: d[4]는 (1을 더했다 생각하고 나머지 3을 만드는 방법) + (2를 더했다 생각하고 나머지 2를 만드는 방법) + (3을 더했다 생각하고 나머지 1을 만드는 방법)의 합이다. (x+2y+3z=n)
: 4 = 1+3 = 2+2 = 3+1
: 5 = 1+4 = 2+3 = 3+2
- 미리 1, 2, 3을 잡아두고 나머지를 더한다 생각하면 쉽다.

 

3. 2xn 타일링

- 문제: https://www.acmicpc.net/problem/11726

- 코드: 

int tile(int n) {
	int d[n];
    int d[0] = 1;
    int d[1] = 2;
    for (i in 2~n-1) {
    	d[i] = d[i-1] + d[i-2];
    }
    return d[n-1];
}

- 이것도 위 문제랑 똑같다.
- 어차피 2x1 타일을 쌓으려면 아래 2x1을 쌓아야 해서 그냥 새로 칼럼만 보고 1짜리를 놓냐, 2짜리를 놓냐만 생각하면 된다.
- 즉, 1이나 2를 더해서 n을 만드는 것 (x+2y=n)
- 위 문제랑 똑같은 원리다. 1 타일을 먼저 1개 놓았다고 생각하고 나머지를 놓거나 or 2 타일을 놓았다고 하고 나머지를 놓거나

 

4. 이항계수 구하기

- 문제: nCk 를 구하라

- 코드:

bino(int n, int k) {
	b[n][k];
    
    for (i in 0~n):
    	for (j in 0~min(i, k)):
        	if(j==0 or j==i) b[i][j]=0;
            else b[i][j] = b[i-1][j-1] + b[i-1][j];
    
    return b[n][k];   
}

- 파스칼의 삼각형을 이용한다. nCk를 구하기 위해서 팩토리얼로 계산하지 않고 n-1Ck-1 + n-1Ck = nCk임을 이용하는 것.
- min(i, k) 이유: 우선 iCj임을 보았을 때, j>i일 수는 없다. 또 파스칼의 삼각형에서 필요한 곳만 보면 C의 우항이 k 이상인 부분은 알 필요가 없다.
- 아래는 2차원 배열 b[][]를 형상화한 모습이다. 5C2를 구하려 했을 때, 굳이 3C3과 4C3, 4C4는 구할 필요가 없다. (볼드처리)

	0	1	2	3	4
0	1
1	1	1
2	1	2	1
3	1	3	3	...
4	1	4	6	...	...
5	1	5	10

 

 

---

 

여기까지 해보니 DP는 결국 점화식으로 귀결된다는 느낌이다. 이 점화식 규칙을 찾는 나만의 방법을 만드는 게 좋을 거 같다.

 

---

참고

https://won-percent.tistory.com/3

좋은 DP 문제들 추천