백준 1463번 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있으며, 해당 부분 지적은 감사히 받습니다.

문제를 보자.

이땐 몰랐다.

힌트가 나에게 어떤 걸 이야기해 주려는지..

 

처음 나의 생각은 연산 횟수가 제일 적으려면, 수를 제일 작게 하는 연산을 해야 한다 생각했다.

그래서 초기 코드는

 

a = int(input())
count=0
while a>=1:
 if (a%3 == 0):
  count+=1
  a/=3
 elif (a%2 == 0):
  count +=1
  a/=2
 else:
  count+=1
  a-=1
print(count)

 

이렇게 작성하였고, 제출했다.

틀렸다.

 

나는 나의 논리에 오점이 있을 거라 생각하지 못했기에, 현실 부정하며 한번 더 제출했다.

 

결과는 냉정했다.

 

통학시간이 다가왔기에, 준비를 하며 복잡한 머릿속을 정리했다.

 

통학을 하면서도 계속 생각했다.

 

학교에 도착해, 첫 번째 수업이 끝나도 떠오르지 않았다.

 

그래서 검색했다.

 

DP 문제란다.

 

필자는 컴퓨터 알고리즘에 대해 단 1도 공부한 적이 없어, 이 접근 방식에 대해 더욱 긴 시간을 투자했어도 생각할 수 없었을 거다.

 

어쨌든 DP에 대해 알아보자.

 

Dynamic Programming ( 동적 프로그래밍 )

 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

 

DP에는 2가지 기법이 있다.

1. Bottom Up

2. Top Down

 

간단히 Bottom Up은 작은 단위에서 큰 단위로, Top Down은 큰 단위에서 작은 단위로 계산해 나가는 방식이다.

이 문제는 Botom Up이 적합하다.

 

또 DP를 사용하기 위해 아래 조건을 만족해야 한다.

1. Overlappint subproblems (겹치는 부분 문제)

2. Optimal substructure ( 최적 부분 구조 )

 

해석해 보면

1. 동일한 작은 문제들이 반복해서 계산될 때

2. 부분 문제의 최적 결괏값을 통해 전체 문제의 최적 결괏값을 낼 수 있을 때 

    다시, 부분 문제의 최적 결괏값이 전체 문제에서도 동일 적용되어 결과가 변하지 않을 때

 

두 가지 경우를 만족할 때 DP를 사용할 수 있다.

 

이 문제에서는 3과 2로 나누거나 1을 빼는 연산을 계속 반복하기에 1번 조건을 만족시킨다.

n의 입력값이 2와 3일 때 각 1, 1이라는 부분 문제에 대해 결괏값이 변하지 않으므로 2번 조건을 만족시킨다.

 

따라서 이 문제는 DP를 사용하여 해결할 수 있다.

 

이 문제는 결괏값이 변하지 않는 부분 문제가 입력값 2와 3의 케이스가 있기에 Bottom Up 형식으로 구현할 것이다.

 

코드

a = int(input())

array=[0] * (a+1)

 

for i in range(2, a+1):

    array [i] = array[i-1] +1

    if(( i % 3 ) == 0):

        array [i] = min(array [i], array[i//3] + 1)

    if(( i % 2 ) == 0):

        array[i] = min(array[i], array [i//2] + 1)

print(array [a])

 

형식으로 구현하였다.

 

Bottom Up 전개의 단점은 코드의 가독성이 낮다.

 

따라서 자세한 설명을 추가한다.

 

배열의 각 요소에 0을 담아 a +1의 크기로 만든다.

각 배열에는 0부터 a까지의 최소 연산 횟수가 들어갈 것이다.

 

 이 문제를 풀기 위해 기본 전제조건에 대한 이해가 필요하다.

 

전제 조건 

1. 모든 자연수는 2로 나뉘지 않을 때, -1을 하면 반드시 나뉜다.

 

너무나 당연한 이야기다.

하지만 이 당연한 사실로부터 아래 코드를 파생시키는 것은, 사전 지식 없이는 쉽지 않다.

array [i] = array [i-1] +1 

 

이 부분이 가장 이해하는데 어려웠다.

배열의 i번째 자리에는 i-1번째의 자리의 최소연산 횟수 보다 1회 많다.

이게 무슨 소리인가 싶다.

이해를 돕기 위한 먼저 설명하자면, 모든 경우의 수에 해당되는 게 아니라, 그러한 경우가 있다.

해당 케이스로 6의 최소연산 수는 6 > 2 > 1로 2회이다. 

그렇다면  i가 7일 때 7은 2로 나누어지지 않으니, 1을 빼는 연산이 필연적으로 수행되어야 한다.

따라서 array [i] = array [i-1] +1  코드는 2로 나누어지지 않는다고 가정하고 미리 넣어두는 수이다.

min() 함수를 모른다면, 이 부분이 가장 이해하기 어려울 것이다.

 

필자는 그랬다.

 

이제 밑 if문에서 3으로 나누어질 때, 2로 나뉠 때 min 함수를 사용해서 최소 연산 수를 배열에 삽입할 것이다.

 

if(( i % 3 ) == 0):

        array [i] = min(array [i], array [i//3] + 1)

 

간단하게 해석해 보자

array [i] = 최솟값(  2로 안 나뉠 때 최소 연산, 3으로 나뉠 때 최소 연산)

중 더 작은 값을 array [i]번째에 넣겠다는 이야기이다.

아래 코드 또한 숫자만 다르지 같은 이야기다.

 if(( i % 2 ) == 0):

        array [i] = min(array[i], array[i//2] + 1)

 

하지만 여기서 의문이 생길 수 있다.

왜 if, elif 가 아니라 if, if일까?

간단하다.

i가 6의 배수일 경우 3으로도, 2로도 나뉠 수 있지만 if, elif형식으로 작성하면 6의 배수에서 연산누락이 생기는 경우의 수가

존재하기 때문이다.

 

아래 코드를 통해 10^6의 숫자 중 연산누락으로 인해 제대로 연산되지 않는 경우를 출력시켰다.

 

직접 해보고 싶다면, 코드는 첨부한다.

추천은 하지 않는다.

출력값이 많아 렉이 걸리기 때문이다.

 

a = int(input())
array = [0] * (a+1)
array2 = [0] * (a+1)
diff_positions = []

for i in range(2, a+1):
    array [i] = array[i-1] + 1
    if i % 3 == 0:
        array [i] = min(array[i//3] + 1, array[i], array[i//2] + 1)
    if i % 2 == 0:
        array[i] = min(array [i//2] + 1, array [i])

for i in range(2, a+1):
    array2 [i] = array2[i-1] + 1
    if i % 3 == 0:
        array2 [i] = min(array2[i//3] + 1, array2[i])
    elif i % 2 == 0:
        array2[i] = min(array2 [i//2] + 1, array2 [i])

for i in range(0, a+1):
    if array [i]!= array2 [i]:
        diff_positions.append(i)

print("Different positions:", diff_positions)

 

그냥 위 코드의 결과를 통해 elif문을 사용했을 때의 오차의 경우가 존재한다는 것을 알 수 있다.

그것도 꽤 많이.

 

이 정도면 충분히 설명되었을 거라 생각한다.

 

배운 점

1. array = [0] * a // 0으로 채워진 a크기의 배열을 선언

2. min() // 최솟값을 선택함

3. 연산자 ' // ' // 정수형으로 몫을 반환해 줌

4. DP // Dynamic Programing으로 부분 문제의 최적 결괏값이 변하지 않고, 부분 문제의 최적 결괏값으로 전체의 최적

결과를 계산할 수 있어야 하며, 문제를 작은 연산들의 반복으로 쪼갤 수 있을 때 사용할 수 있다.

5. Memoization // 한번 수행한 연산은 다시 수행하지 않아, 시간 효율을 올린다.