파이썬 코딩테스트 강좌, 정수를 1로 만들기

코딩테스트에서 자주 출제되는 문제 중 하나는 주어진 정수를 1로 만드는 방법입니다. 이 강좌에서는 이 문제를 해결하기 위해 필요한 알고리즘, 접근법, 그리고 실제 코딩 예제를 통해 자세히 설명하겠습니다. 우리의 목표는 주어진 정수가 1이 될 때까지 최소한의 연산을 수행하는 것입니다.

문제 설명

주어진 정수 X가 있습니다. 다음의 세 가지 연산을 이용하여 이 X를 1로 만들고, 필요한 최소 연산의 횟수를 구하는 문제입니다:

  • 1. X - 1
  • 2. X / 2 (단, X가 2로 나누어떨어질 때만 가능)
  • 3. X / 3 (단, X가 3으로 나누어떨어질 때만 가능)

예를 들어, X = 10일 때, 다음과 같이 계산할 수 있습니다:

  • 10 → 9 (1회)
  • 9 → 3 (2회)
  • 3 → 1 (3회)

따라서, 총 연산 횟수는 3이 됩니다.

문제 해결 접근법

효율적인 방법으로 이 문제를 해결하기 위해선 DP(동적 프로그래밍)를 사용할 수 있습니다. DP는 문제를 작은 부분 문제로 나누고, 각 부분 문제의 해답을 저장해 중복 계산을 줄이는 방식입니다. 아래 과정을 통해 이 접근법을 자세히 설명하겠습니다.

1단계: DP 테이블 초기화

DP 테이블을 생성하여 각 인덱스 i에 대해 i를 1로 만드는 데 필요한 최소 연산 횟수를 저장합니다. 테이블의 크기는 X + 1로 설정합니다.

X = int(input("정수를 입력하세요: "))
dp = [0] * (X + 1)

2단계: 기저 사례 설정

기본적으로 dp[1]의 값은 0입니다. 왜냐하면, 1은 이미 목표이므로 추가적인 연산이 필요 없기 때문입니다.

dp[1] = 0  # 1은 0번의 연산으로 나타낼 수 있습니다.

3단계: 점화식 설정

각 정수 i에 대하여 가능한 모든 연산을 수행해 dp[i]의 값을 업데이트합니다.

  • 일단 i에서 1을 빼는 경우: dp[i] = dp[i-1] + 1
  • 그리고 i가 2로 나누어떨어질 때: dp[i] = min(dp[i], dp[i // 2] + 1)
  • 또한 i가 3으로 나누어떨어질 때: dp[i] = min(dp[i], dp[i // 3] + 1)

즉, 우리는 dp[i]의 값을 최소한의 연산으로 업데이트해 나가는 것입니다.

4단계: 최종 결과 도출

모든 정수에 대해 DP 테이블을 다 채운 뒤, dp[X]가 우리가 원하는 결과, 즉 X를 1로 만드는 데 필요한 최소 연산 횟수가 됩니다.

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

print("최소 연산 횟수:", dp[X])

전체 코드

아래는 앞서 설명한 내용을 바탕으로 작성한 전체 코드입니다:

def min_operations_to_one(X):
    dp = [0] * (X + 1)
    dp[1] = 0  # 기저 사례: 1은 0번의 연산으로 나타낼 수 있습니다.

    for i in range(2, X + 1):
        dp[i] = dp[i - 1] + 1  # 1을 뺄 경우
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2] + 1)  # 2로 나눌 경우
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i // 3] + 1)  # 3으로 나눌 경우

    return dp[X]

# 사용자 입력
X = int(input("정수를 입력하세요: "))
result = min_operations_to_one(X)
print("최소 연산 횟수:", result)

복잡도 분석

위의 알고리즘은 시간 복잡도가 O(N)입니다. 이는 X에 대해 반복문을 통해 DP 테이블을 채우기 때문입니다. 공간 복잡도 또한 O(N)입니다. 이는 DP 배열을 저장하기 위한 공간을 필요로 하기 때문입니다.

결론

이 글에서는 주어진 정수를 1로 만드는 문제를 통해 동적 프로그래밍의 기법을 사용해 문제를 해결해 나가는 과정을 설명하였습니다. 코딩테스트를 대비하여 DP의 다양한 활용법을 익히는 것은 매우 중요합니다. 더 많은 연습 문제를 통해 능력을 키우고, 코딩테스트에서 좋은 성과를 거두길 바랍니다!