[알고리즘] 백준 알고리즘 1463 1로 만들기(Top-Down/Bottom-Up, 피보나치수열) C++

안녕하세요 감자 코딩 & 감자개발자입니다. 이번 강의부터 알고리즘의 핵심인 DP문제를 많이 풀어보게 될것인데요. 

DP(Dynamic Programming)동적계획법 이라고 불리오는 방법으로 문제를 풀어볼 예정입니다. 사실 이문제에 대해서는 전에 Java로 포스팅해놓은적이 있습니다만, 자세한 사항을 설명해놓지 않아서 이번기회에 C++로 재 포스팅하겠습니다.

일단 문제풀이에 앞서서 동적계획법(DP)에 대해서 간단히 복습을 하고 시작하겠습니다. 아주전에 제가 한번 정리해놓은 자료가 있는데요. 그쪽을 참고하셔도 됩니다.

관련 링크(동적계획법 DP)

http://kgh940525.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-DPDynamic-Progamming-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95

1. 동적계획법이란 무엇인가?

간단히 말해서 큰문제를 작은문제로 나누어서 푸는 기법이라고 할 수 있습니다.

=(유사) 분할정복방법과 비슷합니다.

2. 동적 계획법의 대표적인 예

이항계수(nCr)의 계산이라고 할 수 있습니다.

3. 메모이제이션(memoization) 이란?

동적계획법에서는 중복을 막기위해서 저장된 값을 배열에 저장한 뒤, 다음 계산이 필요할때는 저장된 값을 불러와서 중복을 없애면 함수호출이 줄어들게 됩니다. 그러면, 시간복잡도도 훨씬 줄어들게 됩니다.

DP를 설명하기 앞서, 피보나치수열에 대한것을 알고가겠습니다. 가장 대표적인 예제로 많이쓰입니다.

* 피보나치수열

• 피보나치 수열은 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다 라고 정의되어있습니다.

• 밑에 있는 예제를 이해하기 위해서 가장 중요한것이 있습니다. F(n)으로 기준으로 삼아 예를 들겠습니다. F(0) = 1, F(1)=1, F(2) = 2 일경우 n=2 이고, F(n) = F(n-2) + F(n-1)의 점화식이 성립되게 됩니다.

• 하지만, 이 점화식이 다음 진행단계를 계속해서 진행될경우 어떻게 될까요? 그 다음 단계는 F(n+1) = F(n-1) + F(n)이 될것입니다. F(n+1) = 3, F(n-1) = 2, F(n) =1이 될것입니다.

• 겹치는 부분이 보이시나요? 연산 과정에 있어서 겹치는 부분이 계속해서 발생하게 됩니다. 이때 메모이제이션(Memoization)이라는 개념이 등장하게 됩니다. 잠시 저장해놨다가 그 필요에 따라 써먹겠다는 뜻입니다. 이 개념을 알고계시면 이해하시는데 좀더 수월하실겁니다.

4. TOP-DOWN 방식

재귀와 같은 방식으로 위에서 아래로 내려오는 방식입니다.

이때, 함수의 호출을 줄이기 위해서 memoization을 사용합니다. 간단하게 말하여서 재귀호출시에 발생하는 공통되는 연산부분을 기억하였다가, 동일한 결과를 호출할시에 그 부분만 가져다가 쓰기때문에 번거로이 연산을 할 필요가 줄어들게 됩니다. 밑에 예제는 피보나치수열을 이용한 예제입니다.

(Recursive Call)

1 2 3 4 5

long long fib(long long n){     if (n == 1 || n == 2)   return 1;     return fib(n - 1) + fib(n - 2); } Colored by Color Scripter

cs

(DP방식-memoization 적용)

long long fib(long long n){
    if (n == 1 || n == 2)
        return 1;
    if (!memo[n])
        return memo[n];
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

5. 그러면 동적계획법은 언제 사용되는 것인가요?

동적계획법(DP)는 알고리즘의 최적값을 구할때 사용합니다.

6. 동적계획법(DP)의 동작 과정을 살펴봅시다.

(1) 몇차원 (=변수 개수) DP를 할 것인가?

(2) 변수의 개수가 정해졌으면 각각의 변수는 무엇을 의미하는가?

(3) DP값이 어떤 의미인가?

(4) 어떤 DP값과 다른 DP값의 관계가 있는가? 있으면 어떤관계인가?

(5) 4의 점화식을 사용하여 재귀 또는 for문 DP로 계산한다.

7. 동적계획법의 초기화

동적계획법에서는 memoization말고 중요한것은 바로 "초기화" 입니다.

이미 계산한 것을 다시 계산하지 않기 위해서는 계산한 것과 계산하지 않은 것의 차이가 있어야 한다는것 알아두세요.

*계산하지 않은 값은 초기값(초기화한 값) 그대로이고 계산한 값은 바뀌어있기 때문에 그것으로 구분되어집니다.

 따라서 동적 계획법에서 계산한 값의 범위를 대략적으로 알아내서 그 범위에 있지 않은 값으로 초기화를 해주어야 한다. 계산된 값이 0일수 있는 동적계획법의 경우에는 보통 -1(또는 무한대 값이라고 부르는 int_max)을 사용하고 계산된 값이 0일수 없는 경우에는 그냥 전역변수로 선언합니다.

 8. TOP - DOWN VS BOTTOM - UP

TOP - DOWN 방식 에 memoizationd을 했다는 가정하에 시간복잡도는 같습니다.  하지만 실제 걸리는 시간은 TOP - DOWN DP가 더 깁니다. 재귀 DP의 장점은 점화식 그대로 호출이 되기 때문에 형식/순서에 얽매이지 않습니다. for문 DP의 장점은 시간이 (조금은) 적게 걸린다는것입니다.

---

말이 길어졌네요. 이제 그러면 1463번 1로만들기 문제를 살펴볼까요? 

문제링크 

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

---

1로 만들기 성공

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초 128 MB 58921 19143 12340 32.115%

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.

X가 2로 나누어 떨어지면, 2로 나눈다.

1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1 

2

예제 출력 1 

1

예제 입력 2 

10

예제 출력 2 

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

---

문제 해결 방법

1) 

문제에서 가장 중요하게 여기는 부분이

X가 3으로 나누어 떨어지면, 3으로 나눈다.

X가 2로 나누어 떨어지면, 2로 나눈다.

1을 뺀다.

이 세가지 조건입니다. 

보통 의식의 흐름대로 코딩을 하였으면 당연히 3으로 나눠지는것 -> 2로 나눠지는것 -> 그다음 1을 빼면 되지 않을까 라는 생각을 하시는분들이 대부분일겁니다.

하지만, 친절하게도 이 문제에서는 우리에겐 힌트가 주어졌습니다. 

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

라는 조건을 주었습니다. 

2) 이 힌트가 과연 얼마나 큰 도움이 될까 라는 생각이 드실지 모르겠지만, 상당히 중요한 힌트입니다.

예를 들어보겠습니다.

10의 경우에서 위의 조건에 따라 2가지 경우로 1을 만들수있을겁니다.

1. 10 -> 5 -> 4 -> 2 ->1 총 4번의 과정을 거칩니다.

2. 10 -> 9 -> 3 -> 1 총 3번의 과정을 거칩니다.

우리의 의식의 흐름대로 알고리즘을 해결하였다면, 당연히 10의 값이 3으로 나누어지지않으니까 2로 나누어보고 5는 3이랑 2랑도 나누어지지 않네? 라고 생각을 하고 -1을 빼게 될 것입니다. 그리고 4는 2로 나누어 지고, 또 나눈값인 2는 2로 나누거나, -1을 빼거나 둘중하나의 값으로 1로 만들 수 있을겁니다.

네 여기서 무엇을 써야할지 감이 오셨나요? 그렇습니다. 아 재귀호출을 사용해야겠다 라는느낌이 오셨나요? 왜냐하면 우리의 의식의 흐름이 아닌 2번째 방식은 -1을 먼저 빼버리고 2를 나눠버리고 ... 불상사를 일으키게하였기 때문이죠.

3) 위에서 말씀드렸다 시피, 다이나믹프로그래밍(DP)에서는 두가지 방법으로 문제를 해결 할 수 있습니다.

TOP-DOWN(큰문제 -> 작은방식)으로 BOTTOM-UP(작은방식-> 큰방식)으로 나누어 해결하는 방식입니다.

이 방식으로 해결을 하게 된다면, 우리의 의식의 흐름을 바꿔버릴 수가 있겠지요? 하나하나 문제를 해결하면서 이미 구해진값들은 memoization에 저장하고 불필요한 연산을 줄이겠다는 말입니다. memoization이라는 말이 어려우시다면, 단지 값을 저장해놨다가 나중에 쓰겠다는 말입니다. 자세한 사항은 코드로 구현해보겠습니다. 저는 이번에 top-down(recursive call), bottom-up방식으로 모두 구현해보았습니다.

Recursive 호출 순서 

recursive(10)

 num = 10 , recursive(10-1) +1  -> dp[num] + 1 (num-1 일경우) -> recursive(num-1)값 반환

recursive(9)

 num = 9 , recursive(9-1) + 1   -> dp[num] + 1(num%3 일 경우) -> recursive(num/3) 재귀 호출 및 recursive(num-1)값 비교

recursive(8)

 num = 8 , recursive(8-1) + 1   -> dp[num] + 1(num%2 일 경우) -> recursive(num%2) 재귀 호출 및 recursive(num-1)값 비교

recursive(7)

 num = 7 , recursive(7-1) + 1   -> dp[num] + 1(num-1 일경우) ->recursive(num-1)값 반환

recursive(6)

 num = 6 , recursive(6-1) + 1   -> dp[num] + 1(num%3 일 경우) -> recursive(num/3) 재귀 호출 및 recursive(num-1)값 비교

recursive(5)

 num = 5 , recursive(5-1) + 1   -> dp[num] + 1(num-1 일경우) -> recursive(num-1)값 반환

recursive(4)

 num = 4 , recursive(4-1) + 1   -> dp[num] + 1(num%2 일 경우)-> recursive(num/2) 재귀 호출 및 recursive(num-1)값 비교

recursive(3)

 num = 3 , recursive(3-1) + 1   -> dp[num] + 1(num%3 일경우 )-> recursive(num/3) 재귀 호출 및 recursive(num-1)값 비교

recursive(2)

 num = 2 , recursive(2-1) + 1   -> recursive(2-1)은 종료되어 버리므로 0 + 1 / dp[num] return 

recursive(1)

 num = 1 , recursive(1-1) + 1   -> return 0 (함수 종료)

---

코드리뷰

TOP-DOWN방식

//

//  1463(1로만들기).cpp

//  beakjoon_algorithm

//

//  Created by kgh on 24/12/2018.

//  Copyright © 2018 kgh. All rights reserved.

//

#include <stdio.h>

#include <iostream>

using namespace std;

// TOP - BOTTOM 방식 큰 문제 dp[100001] -> 작은문제로

int dp[1000001];

int recursive(int num){

    

    // 1일 경우 순회하지 않고 종료

    if(num == 1){

        return 0;

    }

    // dp값이 0보다 큰 경우(값이 있는경우== 값이 저장되어있는경우)

    if(dp[num] > 0){

        return dp[num];

    }

    // 10의 경우를 대비해서 num % 3, num % 2 , num -1 의 경우가 아니라

    // 1. num - 1을 기본적으로 깔고 들어가서 값을 저장시켜놓기 위함

    dp[num] = recursive(num-1) + 1;

    // 2.  num % 3으로 나누어질 경우

    if(num % 3 == 0){

        int save = recursive(num/3) + 1;

        // 왜 값을 비교하고 다시 저장하느냐? 최소값을 구하기 위함입니다. num/3으로 나눈 값이 dp[num]값보다 작으면 최소값이 되기때문입니다.

        if(dp[num] > save){

            dp[num] = save;

        }

    }

    // 3. num % 2으로 나누어질 경우

    if(num % 2 == 0){

        int save = recursive(num/2) + 1;

        // 왜 값을 비교하고 다시 저장하느냐? 최소값을 구하기 위함입니다. num/2으로 나눈 값이 dp[num]값보다 작으면 최소값이 되기때문입니다.

        if(dp[num] > save){

            dp[num] = save;

        }

        

    }

    return dp[num];

    

}

int main(void){

    int num;

    cin >> num;

    cout << recursive(num) << endl;

    return 0;

}

---

Bottom - UP 방식

//

//  1463(1로만들기)-bottomup.cpp

//  beakjoon_algorithm

//

//  Created by kgh on 26/12/2018.

//  Copyright © 2018 kgh. All rights reserved.

//

// BOTTOM UP 문제

#include <stdio.h>

#include <iostream>

using namespace std;

int dp[1000001];

int main(void){

    int num;

    cin >>num;

    // 가장 작은 문제를 1로 둔다. 왜? 여기서 원하고하자는것은 1에 최소횟수이므로, dp[num==1]일 경우를 가장 작은문제로 두고 푸는것임.

    dp[1] = 0;

    

    // 가장 작은문제로 두었기때문에 그다음문제부터 입력한 수까지의 값을 반복문을 돌리게 한다.

    for(int i=2; i<=num; i++){

        dp[i] = dp[i-1] + 1;

        

        // i를 3으로 나누었을때 0 이며, 나눈값이 기존의 dp[num]값보다 작을때 값을 바꿔준다.(최소값)

        if(i % 3 == 0 && dp[i] > dp[i/3] + 1){

            dp[i] = dp[i/3] +1;

            

        }

        // i를 2으로 나누었을때 0 이며, 나눈값이 기존의 dp[num]값보다 작을때 값을 바꿔준다.(최소값)

        if(i % 2 == 0 && dp[i] > dp[i/2] + 1){

            dp[i] = dp[i/2] + 1;

        }

    }

    

    // 출력

    cout << dp[num] << endl;

  

    return 0;

}

이렇게 DP문제에서의 TOP-DOWN / BOTTOM-UP방식으로 문제풀이 및 코드리뷰를 마치겠습니다. 자세한 사항은 주석에 달아놓았으니, 확인하시면 될것같습니다.

이상 감자코딩 & 감자개발자였습니다 감사합니다 : D