dp 뿌시기 1(feat 양치기)

이 글은 고급 알고리즘인 dp의 이해를 위해 작성하였습니다. 

다른 알고리즘 같은 경우 설명과 코드를 보면 이해가 단 번에 이해가 갔지만, dp의 경우에는 일반적 사고와는 달라 이해하기 쉽지 않았습니다. 

이를 위해 dp의 다양한 유형을 분석하므로써 dp의 사고흐름을 정확히 이해하기 위해 작성하였습니다. 아래 문제들은 백준 골드 정도 되는 문제들로 구성되어있습니다. 

문제풀이에서 가장 중요한 건 어떤 알고리즘인지 파악하는 게 중요하기 때문에 dp문제라는 것을 미리 알고있지만, 문제를 처음 보았을 상황을 가정해서 dp 문제풀이를 해보도록 하겠습니다. 

또, 하나 dp의 사고과정을 위해 작성한 글이기 때문에 코드를 직접 작성하지 않겠습니다. 

 

---

#1번째 문제: 백준10942  팰린드롬?

https://www.acmicpc.net/problem/10942

 

문제설명에 앞서 팰린드롬을 먼저 설명하자면 팰린드롬이란 앞에서부터 읽어도 뒤에서부터 읽어도 똑같은 글자를 말합니다. 예를 들면 기러기 토마토 스위스 우영우가 있겠죠.

▸ 알고리즘 설명

가장 직관적인 방법은 주어진 인덱스를 배열에서 찾아 판별하는 것입니다. 그렇다면 시간 복잡도는 O(NM)이므로 1,000,000 x 2,000 = 2백억이기 떄문에 시간초과가 납니다. 그래서 우린 다른 방법을 찾아야 합니다.

팰린드롬 규칙

• 길이가 1인 경우 무조건 팰린드롬입니다
• 길이가 2인 경우 두 숫자가 동일해야 합니다.
• 길이가 3이상인 경우 양끝이 동일해야 하고 그 안에 있는 숫자들은 팰린드롬이어야 합니다.

 

위 규칙을 코드로 표현한 것입니다. 특히  else 부분 때문에 dp라고 말하는 것입니다. 그 안에 있는 숫자들이 팰린드롬인지 판명하기 위해서입니다. arr[i+1][j-1]이 뜻하는 바는 시작과 끝을 제외한 숫자들이 팰린드롬인지 나타내는 것입니다.

▸주요코드

        for(int j=1;j<=n;j++){
            int temp = Integer.parseInt(st.nextToken());
            input[j]=temp;
            for(int i=1;i<=j;i++){
                if(i==j)arr[i][j]=1;
                else if(j-i==1) arr[i][j] = (input[j]==input[i])?1 : 0;
                else {
                    arr[i][j] = (input[j]==input[i] && arr[i+1][j-1]==1)?1 : 0;
                }
            }
        }
출처: https://lahezy.tistory.com/26 [기룩기록:티스토리]

아래 그림 처럼 위에서 아래로 채워집니다. arr[i][j]가 뜻하는 바는 i번째부터 j까지 팰린드롬인지 아닌지 1과 0으로 나타낸 것입니다. 

 

 

[배운점]

dp의 핵심은 이전 탐색값을 어떻게 이용할 것인가입니다. 점화식을 먼저 세워 푸는 사람이 있는 방면 저는 dp배열을 만들어 어떻게 채워 넣을지를 새각하는 게 더 이해하기 쉽다는 것을 알았습니다. 저처럼 평소 점화식이 잘 이해가지 않았던 분들은 이 방법을 사용하시면 좋을 것 같습니다.

---

# 2번 째 문제: 백준11049 행렬 곱셈 순서

https://www.acmicpc.net/problem/11049

1번째 문제에서 배웠던 점을 토대로 배열을 그려 어떤 값을 먼저 알아야 다음 값을 채울 수 있을까를 먼저 생각했습니다. 그랬더니 아래와 같이 dp배열을 채워야 답을 구할 수 있다는 것을 알았습니다.

▸ 주요코드 

for(int i=2; i<n+1; i++) { // 구간 간격 i 
	for(int j=0; j<n-i+1; j++) { // 구간 시작점 j (0~j+i-1))
		dp[j][j+i-1] = INF;
		for(int k=j; k<j+i-1; k++) { // 중간 지점 k (j~ j+i-1)) 
			int value = dp[j][k]  + dp[k+1][j+i-1] + (data[j]*data[k+1]*data[j+i]);
			dp[j][j+i-1] = Math.min(dp[j][j+i-1], value);
		}
	}
}

출처: https://loosie.tistory.com/365#h1

 

이해해보려고 노력하였으나 3중for문을 이해하고 짜기에는 아직은 역부족이라 다음에 다시 정복하도록 하겠습니다..