[BOJ] 1463번: 1로 만들기

문제 링크: https://www.acmicpc.net/problem/1463

문제 상황

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

\(X\)가 \(3\)으로 나누어 떨어지면, \(3\)으로 나눈다.
\(X\)가 \(2\)로 나누어 떨어지면, \(2\)로 나눈다.
\(1\)을 뺀다.

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

입력

Line 1: 정수 \(N (1 ≤ N ≤ 1,000,000)\)

출력

연산을 하는 횟수의 최솟값

1. 문제해결 전략

문제를 보자마자 전략이 바로 떠오르지 않았다. 1부터 한번 그냥 세보자.

1의 경우 (0)
2의 경우 (2→1 , 1)
3의 경우 (3→1 , 1)
4의 경우 (4→2→1 , 2)
5의 경우 (5→4→2→1 , 3)
6의 경우 (6→3(2)→1, 2)
7의 경우 (7→6→3→1, 3)
8의 경우 (8→4→2→1, 3)
9의 경우 (9→3→1, 2)
10의 경우 (10→9→3→1, 3)
11의 경우 (11→10→9→3→1, 4)

직접 하나씩 구해보면서 느낀거지만, 재활용이 가능하다. 예를들어 7의 경우를 생각해보면 7은 어차피 2, 3의 배수가 아니므로 1을 빼 6이 되야한다. 6에서 연산을 계속 이어나가면 되므로 7의 경우 연산의 수는 (6의경우 연산의 수 + 1) 이다. 수열로 나타낼 수 있겠다.

\(a_n=min(a_{n-1},^Ǝa_{n/2},^Ǝa_{n/3})+1,\) \(when (n＞1)\)

\(a\)수열의 \(n\)번째 원소는 \(n-1\)번째 원소, (\(n\)이 \(2\)의 배수 일때만) \(\frac{n}{2}\)번째 원소, 와 (\(n\)이 \(3\)의 배수 일때만) \(\frac{n}{3}\)번째 원소중 가장 작은 값에 \(1\)을 더한 값이다. 의외로 쉽게 끝났다.

2. 전략 구현

C99로 구현하였다.

앞서 이야기 해본 전략을 구현해보자.

2-1. 재귀 함수

int operation(int n){
    int ret,tmp;
    if(n==1) return 0;
    ret=operation(n-1);
    if(!(n&1)){
    	tmp=operation(n/2);
        if(ret>tmp) ret=tmp;
    }
    if(!(n%3)){
    	tmp=operation(n/3);
        if(ret>tmp) ret=tmp;
    }
    return ret+1;
}

앞서 말한 전략을 그대로 구현했다. \(n\)이 \(1\)이면 연산이 필요 없어 \(0\)이고, \(2\) 이상인 경우 가능한 경우에 한해, \(n-1\), \(\frac{n}{2}\), \(\frac{n}{3}\) 번째 원소 중 가장 작은 값에 \(1\)을 더한 값을 반환하도록 하였다.

하지만 메모이제이션을 통해 재귀함수의 중복호출을 회피할 수 있다는 걸 우린 이미 알고 있다.

2-2. 타뷸레이션 (Tabulation)

메모이제이션하고 약간의 개념 차이가 있다. 함수 호출이 예상되는 값들을 미리 계산해 놓는 것이다. 어차피 계산은 처음부터 시작해야 제대로 참조가 가능하고,(i 인덱스가 i-1이나 \(\frac{i}{2}\), \(\frac{i}{3}\)을 참조해야 하기 때문이다.) 필요한 값은 배열의 가장 마지막 값이니 0으로 초기화된 배열에서 2부터 마지막 N까지 연산하도록 해야겠다.

for(int i=2;i<=N;++i){
    array[i]=array[i-1];
    if(!(i&1) && array[i]>array[i>>1])
    	array[i]=array[i>>1];
    if(!(i%3) && array[i]>array[i/3])
    	array[i]=array[i/3];
    ++array[i];
}
printf("%d",array[N]);

보다시피 함수를 쓰지 않아도 구현이 가능하여 반복문 안에서 해결하였다.

3. 전략 수정

3-1. 수정 전략 찾기: 낭비 되는 곳 찾기

앞선 단계에서 구현한 코드를 사용하여도 제한시간 내 실행이 가능하다. 그래도 좀 더 살펴보자. \(2\)나 \(3\)으로 나누는 연산은 먼저 나누어 떨어지는지 확인해야하는데, 나누어 떨어지지 않으면 나머지는 나머지대로 계산하고 시간을 낭비한다. 나누어 떨어졌더라도 이번엔 몫을 구하는 연산을 해서 조금 마음에 들지 않는다. 짱구를 굴려보자. ~~데굴데굴~~

위 예시에서 \(11\)의 경우를 보면 \(9\)까지 줄이기 위해 \(2\)번의 연산이나 소모한다. 뭔가 아깝다. \(11\)에서 바로 \(9\)를 찾을 수 있는데…

a[11] = a[9] + 2;
a[11] = a[11-(11%3)] + (11%3);
a[11] = (1 + a[11/3]) + (11%3);

찾은 듯 하다. \(11\)에서 \(1\)을 계속 빼서 \(3\)으로 나누는 경우를 탐색하는 경우 \(11 mod 3\), 나머지만큼의 추가 연산이 들어간다는 것을 한번에 계산할 수 있다는 것을 발견했다. 그리고 \(9\)의 경우를 더하면 되는데 \(11\)에서 \(9\)를 찾아내는 법이 좀 더럽다. 하지만 어차피 \(3\)으로 나눠 줄 것이기 때문에 바로 \(3\)으로 나눠버리면 나눗셈 계산에서 int에는 버림이 되기 때문에 쉽게 처리가 가능하다. 때문에

a[n] = a[n/3] + (n%3) + 1;

로 \(9\),\(10\),\(11\)은 처리가 될 것 같다. 이제 굳이 \(1\)을 빼는 연산은 안 세도 되는 것이다. \(2\)로 나누는 연산도 같은 방법으로 처리하면 훨씬 간단해지겠다.

3-2. 재귀 함수의 수정

int operation(int n){
    int a,b;
    
    if(n<4)	return (n!=1);
    
    a = operation(n>>1) + (n&1);
    b = operation(n/3) + (n%3);
    return (a<b ? a+1 : b+1);
}

덕분에 간결해졌다. 확인도 안하고 2와 3으로 나누고 시작하기 때문에 4 미만은 위와 같이 걸러줬다. 가볍게 2개의 변수를 선언해 각각 2로 나눌 경우, 3으로 나눌 경우를 계산 후 작은 값을 반환했다.

3-3. 타뷸레이션의 수정

array[2]=array[3]=1;
for(int i=4;i<=N;++i){
    int a,b;
    a = array[i>>1] + (i&1) +1;
    b = array[i/3] + (i%3) +1;
    array[i] = (a<b ? a : b);
}
printf("%d",array[N]);

마찬가지로 4미만은 2나 3으로 나누면 의미가 없으니 4부터 시작한다. 2와 3은 1로 초기화하고, 나머지 배열 원소들은 0으로 초기화 되어 있다.

4. 최종 코드

4-1. 재귀 함수로 구현한 최종 코드

#include <stdio.h>

int operation(int n){
    if(n<4)	return (n!=1);
    
    int a,b;
    a = operation(n>>1) + (n&1);
    b = operation(n/3) + (n%3);
    return (a<b ? a+1 : b+1);
}

int main(void){
    int N;
    scanf("%d",&N);
    printf("%d",operation(N));
    return 0;
}

결과	메모리	시간	코드 길이
`맞았습니다!!`	1116KB	0ms	252B

제출 소스 확인하기

4-2. 타뷸레이션으로 구현한 최종 코드

#include <stdio.h>
#include <malloc.h>

int main(void){
    int N,*array;
    
    scanf("%d",&N);
    array=calloc(N+1,sizeof(int));
    array[2]=array[3]=1;
    
    for(int i=4;i<=N;++i){
    	int a,b;
        a = array[i>>1] + (i&1) +1;
        b = array[i/3] + (i%3) +1;
        array[i] = (a<b ? a : b);
    }
    printf("%d",array[N]);
    
    free(array);
    return 0;
}

결과	메모리	시간	코드 길이
`맞았습니다!!`	5024KB	4ms	322B

제출 소스 확인하기

5. 고찰

Dynamic Programming에서도 Memoization이나 방금 이용한 Tabulation는 필요한 내용을 경우에 따라 저장하고 필요할때 사용하여 (공간복잡도를 다소 희생해) 시간복잡도를 개선하는 방법이다. 특히 재귀함수에서 반복된 재귀호출로 중복되는 연산이 발생하는 경우 이러한 방법을 애용했었다. 그런데 이번에는 시간이나 메모리, 심지어 코드복잡도 측면에서 모두 손해를 보았다.

코드 복잡도 부분이야 당연하게도 재귀함수로 구현된 수열이 귀납적 정의로 좀 더 간략하고 핵심적으로~~컴팩트하게~~ 구현이 가능한 것이었고. 공간 역시 (함수 스택의 오버헤드도 있겠지만) Memoization & Tabulation이 기본적으로 공간복잡도 \(O(n)\)을 가지므로 불리하다.

시간의 경우 재귀함수로 구현한 코드가 더 짧게 걸렸다는 것은 (연산의 종류에 따라 연산 시간의 차이는 있지만) 연산이 더 적었다는 것을 의미하기도 한다.

타뷸레이션의 경우 어떤 수가 \(n\)을(또는 \(1\)을 뺀 수들을) \(2\)로, \(3\)으로 나눈 수인지 판별해서 그것만 계산하기는 어려워, \(4\)부터 \(n\)까지 모두 계산하였다.

반면 재귀함수로 구현한 경우는 필요한 부분만 탐색하였으며, 중복되는 함수호출의 경우가 거의 없어서 낭비도 적었다. (메모이제이션으로 그러한 중복연산도 해결할까 했지만 별 의미 없는 작업인 것 같아 접었다.)

6. Evaluation Strategy(평가 전략)

6.1 Eager Evaluation vs Lazy Evaluation

Wikipedia: Evaluation Strategy

Evaluation strategies are used by programming languages to determine two things — when to evaluate the arguments of a function call and what kind of value to pass to the function.

함수가 값을 어떻게 전달하는지 (call by value, reference and pass by reference, etc.)도 해당하지만 앞선 단계 고찰과 연관이 없으니 논외로 하자.

결국 언제 어떻게 값을 평가하느냐, 즉 값을 찾아내고 계산하느냐에 관한 이야기이다.

Eager Evaluation(조급한 계산법), Lazy Evaluation(느긋한 계산법) 이 이번에 살펴 볼 것들이다.

Wikipedia: Eager evaluation

In eager evaluation, an expression is evaluated as soon as it is bound to a variable.

An opposite alternative to eager evaluation is lazy evaluation, where expressions are evaluated only when a dependent expression is evaluated depending upon a defined evaluation strategy.

말은 저렇게 써 놨지만, Eager Evaluation은 (단순 초기화 때 값을 넣어놓고 시작하는 것 뿐 아니라) 계산을 미리 해놓고 시작하는, 그 다음에야 값을 찾는 evaluation strategy다. Tabulation이 이에 해당하겠다.

Lazy Evaluation은 종속된 expression이 계산될때, 좀더 일반적으로 생각해보면 결국 필요할때, 요구될때만 계산하는 evaluation strategy이다. 중복된 계산이 있든 말든 재귀함수 호출로 해결해 버리는 게 대표적인 lazy evaluation이고, 한번 연산한건 기억해놨다가 나중에 또 쓸때 가져다 쓰는 memoization도 결국엔 계산을 미루다 필요할 때만 계산하는 것은 마찬가지이니 lazy evaluation에 해당한다.

Wikipedia: Lazy evaluation

The benefits of lazy evaluation include:

The ability to define control flow (structures) as abstractions instead of primitives.

The ability to define potentially infinite data structures. This allows for more straightforward implementation of some algorithms.

Performance increases by avoiding needless calculations, and avoiding error conditions when evaluating compound expressions.

However, for lengthy operations, it would be more appropriate to perform before any time-sensitive operations, such as handling user inputs in a video game.

문서에 잘 서술 되어 있듯 lazy evaluation은 불필요한 계산을 줄일 수 있을 뿐 아니라, 동적이어서 처리과정에서 다른 동적인 처리가 실시간으로 가능하다. 하지만 초기화 시간은 여유롭지만 동작 과정이 실시간으로 요구되는 경우 (게다가 처리량이 많다면) eager evaluation으로 미리 초기화를 시켜놓고 값을 가져다 쓰는 방식이 이득이다.

6.2 Top Down vs Bottom Up Design (하향식 vs 상향식 접근)

다루면 할 얘기가 많지만, 간략하게만 정리하고 넘어가고자 한다. ~~귀찮다~~ 이 문제를 예시로 들자면, 우리가 N이란 수를 입력받으면,

array[N]
operation(N)

들 중 하나를 계산하여 출력하였다. 기본적으로 두 경우 모두, N번째를 구하기 위해서는 \(N-1\)이나 \(\frac{N}{2}\), \(\frac{N}{3}\)번째를 구하여 비교해야 한다.

Tabulation의 경우 \(2\)이상 또는 \(4\)이상의 값부터 \(N\)까지 오름차 순으로 구하는데, 숫자의 순서로 볼때나, 순차적으로 우리가 아는 곳으로부터 목표지점에 도달하는 것으로 볼때나 아래에서 위로, bottom up (상향)을 지향하는 접근방식으로 보인다. Tabulation은 bottom up (상향식 접근)에 해당한다.

Memoization의 경우 \(N\)번째를 먼저 호출하고, 필요한 재귀함수 호출에 따라 \(N-1\), \(\frac{N}{2}\), \(\frac{N}{3}\)번째 들이 호출되었다. 인덱스 순서가 위에서 아래로 줄어드는 것도 그렇고, 결과(목표)에서부터 우리가 아는 곳까지 찾아오는 방식도 그렇고 위에서 아래로, top down(하향)을 지향하는 접근방식으로 보인다. Memoization은 top down (하향식 접근)에 해당한다. 출처: geeksforgeeks

앞서 살펴본 것들로,

eager evaluation vs lazy evaluation
bottom up design vs top down design
tabulation vs memoization

가 있다. 이 글로 비추어 볼때 결국 같은 두가지 방식을 다른 세가지 관점에서 바라본 것이 되었다. 그렇다고 eager evaluation이 곧 bottom up design이고 이는 tabulation이라고 단정짓거나 같다고 보기는 어렵다. 저 세가지는 그저 각각 evaluation strategy, programming design, 그리고 이것들의 dynamic programming에서의 구현 일 뿐이다.

뭐 쨌든 좀 더 자세히 조사해 엄밀하게 정리하고 싶지만, 차차 나중에 하도록 하자.

PREVIOUS1932번: The Triangle

NEXT13305번: 주유소