[백준 11055] 가장 큰 증가 부분수열(자바)_강의

안녕하세요 여러분! 티스토리 주인장 zzino 입니다.

오늘은 백준 11055 가장 큰 증가 부분수열문제를 같이 풀어볼까 합니다. 

이 문제는 기본적으로 dp알고리즘에 속해있는 문제고, 추가로 외판원 순회, 배낭 문제등에서와 같이 LIS 라는 테크닉이 사용되는 문제입니다. 물론 기본적으로 dp란게 뭔지는 알고계셔야 푸실 수 있고, LIS는 굳이 몰라도 풀 수 있습니다.

 

dp라는 알고리즘 특성상, dp풀이의 관건이자 핵심인 dp테이블의 정의세우기, 점화식 세우기, 초항처리, 구현 이렇게 나눌 수 있는데 말씀드린 4가지를 계속 생각하시면서 글을 읽어나가시면 좋습니다.

 

알고리즘 브론즈, 실5수준의 초보자의 입장에서 차근차근 논리전개를 해보겠습니다.

지금부터 문제를 크게 세 부분, 접근, 설계, 구현으로 쪼개어 풀어보겠습니다.

 

 

www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

---

 

1 - 접근, 설계

우선 문제를 읽습니다. 문제 자체는 2~3줄로 읽기도 괜찮고 매우 간단합니다.  증가하는 부분 수열중에서 합이 가장큰것을 구하라는구나...라고 요구조건을 명세합니다.

여기서 무슨 알고리즘을 써야되지? 그로 인한 시간복잡도는 어떻게되지? 라는 생각을 한 번 해봅니다. 떠오르는게 없어도 괜찮습니다.

 

떠오르는게 없다면, 예시를 한 번 분석해봅니다. 물론 초보단계에선 알고리즘 분류를 보고 dp임을 알고 바로 dp테이블의 정의와 점화식을 세워봐도 됩니다. 예시를 분석하는 경우부터 먼저 보시겠습니다.

 

예시를 분석해보는 경우 

예를 들어 문제에서 보여준 예시인 

1, 100, 2, 50, 60, 3, 5, 6, 7, 8 인 경우, 다음과 같이 생각해볼 수 있습니다.

"음..아직 잘 모르겠어. 근데 일단 60 같은 경우(왜 첫 항인 1부터 생각안해보냐고 물어보실수 있는데 점화식의 특성상 일반적인 관점에서 보는게 더 편해 중간정도에 위치한 항인 60으로 잡았습니다) 구하는게 1 + 2 + 50 + 60 이겠지?

근데 앞에 100을 내가 왜 안셌을까? 아 왜나면 60은 100보다는 작은데 1, 2, 50 보다는 크니까, 즉 증가하는 수열이니까 그런거구나.

그리고 60의 경우 1 + 2 + 50 같이 이 누적되있는 형태는 내가 for문으로 표시하면 편하지않을까? 반복을 없애기 위해 for문을 쓰니까.

내지는, 어 근데 여기서 50의 경우 1 + 2를 더하는건데 여기서 중복이 발생하는것 같다.

다시 말해, 60을 구하는데 1 + 2 라는 연산을 해야하고, 50을 구하는데도 1 + 2 라는 연산을 해야하는거면,

여기서 중복이 생기는데 이 중복, 그리고 중복연산으로 인한 시간복잡도의 증가를 어떻게 해결할 수 있을까?

아! dp를 써서 중간중간 결과를 저장해놓자! 라는 생각을 할 수있습니다.

 

만약 여기서 dp를 쓸 생각이 안들었다면,

적어도 memoization을 이용해서 중간중간 결과를 저장해놓을 생각은 챙기고 넘어가자. 라는 생각을 해 볼 수 있습니다.

이제 6의 입장에서 생각해보자. 6은 1 + 2 + 3 + 5 겠지? 

근데 내가 여기서 100을 왜 안셌을까? 아 60보다 크니까 그랬겠지. 그럼 2는 왜 셌을까?

아 60보다 작으니까 셌구나. 그러면 여기서 2가지 생각을 할 수 있는데

첫번째는, if문으로 검사하면 되겠구나( if( 이전항 < 6 then ~~~) 이렇게 if문 써서 구현해야지 라고 생각하고 넘어갑시다.)

두번째는, for문 써서 첫 항부터 6보다 바로 이전항까지 작은지 아닌지 일일이 검사해줘야되겠다.(라고 확실하게 정할수있죠?)

근데 아까 내가 memoization 쓸거라 그랬는데, 그 memoization을 이용하면 memo배열의 각 항에 그 증가 부분수열의 최댓값일때 각 항까지의 부분 증가수열의 합을 저장해 놓을 수 있고, 기준점 하나 잡고(위의 예에선 6) for문 돌면서 그때그때의 memoization 값 + 기준값을 계속 최댓값으로 갱신해나가면 되자않을까? 라는 생각을 할 수 있는데요, 여기서 말한게 곧 점화식이죠? 여기서 점화식을 쓸 필요성을 느끼고 dp를 써야겠다고 마음먹을 수 있습니다.

더 자세히 말씀드리자면, i 번째항을 기준으로 잡고 i번째 이전 항까지 다 for문안에서 증가수열인지 검사해보고, 증가수열이면 memo 값 + i번째 항으로 계속해서 최댓값 갱신을 해주면 되지않을까? 라는 생각을 해볼 수 있단겁니다.

그림으로 나타내면 다음과 같습니다.

 

 

즉, 점화식을

dp[i] = Math.max(dp[0] + arr[i], dp[1] + arr[i], .... , dp[k] + arr[i], ..... , dp[i - 1] + arr[i]) (단, arr[k] < arr[i]) 

이렇게 잡을 수 있습니다. 이 점화식꼴을 보면 이제는 정말 이중 for문을 써야겠다는 생각이 들어야합니다!

 

요런 일련의 사고과정을 해볼 수 있습니다. 만약 예시를 해석해봐도 답이 안나온다 싶으면 알고리즘 분류를 눌러

사용되는 알고리즘이 뭔지 확인한 후 다시 푸셔도 되는데요, 

사실 실1수준에서는 이 문제가 왜 dp인건지도 중요하지만, dp를 사용해서 어떻게 풀어야되는가도 매우 중요하기때문에

바로 dp 알고리즘 문제임을 알고 푼다면 바로 점화식을 세우시게 될건데, dp테이블 정의를 세울때 조금 주의를 하셔야 합니다. 만약 아래와 같이 dp테이블을 정의한다면,

 

dp임을 알고, 바로 dp테이블의 정의와 점화식을 세우는 경우

dp[i] 의 정의 : i 번째 항까지의 증가부분수열의 최댓값의 최댓값.

다시말해 위에서 예시로 든 경우를 보면, (초항이 1부터 시작한다고 가정하겠습니다)

dp[1] = 1

dp[2] = 101

dp[3] = 101

dp[4] = 101

dp[5] = 113

이렇게 되는데요, 이러면 올바른 점화식을 세울 수 없습니다. 본인이 이렇게 세웠다면 수많은 삽질을 해봤을건데, 이게 도저히 답도 안나오면 한 발 물러나서 아 혹시 내가 dp테이블 정의를 잘못 세운게 아닐까? 하는 생각도 해봐야 합니다.

 

그럼 어떻게 정의 해야할까요?

앞에서 말씀드렸듯이 

dp[i] = '부분'증가수열에서 'i번째 항'이 '최댓값'인 부분증가수열의 누적합.

이렇게 dp테이블을 정의하고 나면

dp[1] = 1

dp[2] = 101

dp[3] = 3

dp[4] = 53

dp[5] = 113

...

그럼 점화식도 세울수 있겠죠?

dp[i] = Math.max(dp[0] + arr[i], dp[1] + arr[i], .... , dp[k] + arr[i], ..... , dp[i - 1] + arr[i]) (단, arr[k] < arr[i])

 

이렇게 되는겁니다. 사실, 실3수준이하의 dp문제에서는 문제에서 요구하는 것이 곧 dp테이블의 정의가 되는 경우가 다반사지만, 점점 난이도 어려운 dp문제를 풀수록 dp테이블의 정의가 문제에서 요구하는것과 1:1로 대응하지않을뿐더러, dp테이블이 일차원이 아닌 이차원배열을 사용해야하는 경우, 필요에 따라 memoization 배열을 2개 이상 선언해서 필요한 정보를 저장해야 하는 등 많은 경우들이 존재합니다.

하지만 걱정마세요! 여러분한텐 zzino가 함께하니깐요~ㅎㅎ 

는 장난이구요... 일반적으로 코테 수준에선 이런 문제도 있구나 저런 문제도 있구나 하면서 경험을 많이 쌓으시다보면 어느새 실력이 출중해진 자신의 모습을 보실 수 있을겁니다 :)

 

2 - 구현

이제 구현만 남았는데요, 구현은 어떻게 해야하나....하는 생각이 드시겠지만 이미 접근과 설계 단계에서 많은 생각을 떠올렸고, 이를 코드로 옮기기만 하면 됩니다. 

여담이지만 실력이 올라갈수록 자연어로(한국어, 영어) 내 생각을 써가는것보다 코딩으로 내 생각을 써가는게 더 빠르다고 느껴질 때가 올겁니다. 물론 이는 minimum 골드1, 플레 다이아 분들의 이야기이니 너무 주눅들지 말고 합시다 ㅎㅎ

 

구현은 사실 여러분이 직접 해보는게 좋아서, 위에 접근과 설계편 읽으셨다면 한 번 보지말고 잠시 스크롤 멈춰놓은 다음, 혼자 해보시기 바랍니다.

그래도 못풀겠다면 부담없이 봅시다. 남의 코드 읽는건 항상 좋은 습관입니다 :)

 

package Tistory;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ11055 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1];
        int[] I = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            I[i] = Integer.parseInt(st.nextToken());
        }

        dp[1] = I[1]; //초항처리
        //dp[i] : '부분'증가수열에서 'i번째 항'이 '최댓값'인 부분증가수열의 누적합
        for (int i = 1; i <= N; i++) {
            dp[i] = I[i]; // 디버깅하면서 알아가도 좋음.왜 이문장이 들어가야하는지.
            for (int j = 1; j < i; j++) {
                if (I[i] > I[j]) {
                    dp[i] = Math.max(dp[j] + I[i], dp[i]);
                }
            }
        }

        int max = Integer.MIN_VALUE;
        for (int i : dp) {
            max = Math.max(i, max);
        }
        System.out.println(max);

    }
}

 

긴 글 읽어주셔서 감사합니다! 다음 편에서 또 찾아뵙겠습니다 :)

 

감사인사하는 zzino