스위프트 코딩테스트 강좌, 정수를 1로 만들기

코딩 테스트는 소프트웨어 엔지니어로서의 능력을 평가하는 중요한 요소입니다. 이 글에서는 ‘정수를 1로 만들기’라는 주제를 가지고 스위프트로 구현할 수 있는 알고리즘 문제를 다루고, 그 해결 과정을 상세히 설명할 것입니다.

문제 설명

주어진 정수 x에 대해 다음과 같은 규칙을 적용하여 1로 만들고자 합니다:

x = x - 1 (1을 뺀다)
x = x / 2 (2로 나눈다. 단, x가 짝수일 때만 가능)
x = x / 3 (3으로 나눈다. 단, x가 3의 배수일 때만 가능)

위의 세 가지 연산을 이용하여 최소 몇 번의 연산으로 x를 1로 만들 수 있는지를 계산하는 프로그램을 작성하시오.

입력 형식

첫 번째 줄에 정수 x (1 ≤ x ≤ 10⁶)이 주어진다.

출력 형식

정수를 1로 만들기 위해 필요한 최소 연산 횟수를 출력한다.

예제

입력:
10

출력:
3

설명:
10 → 9 → 3 → 1 (3번의 연산)

문제 해결 접근

이 문제는 Dynamic Programming, 즉 동적 프로그래밍 기법을 사용하여 해결을 시도해볼 수 있습니다. 문제의 상태는 현재의 정수 x이며, 이를 1로 만드는 방법을 이전의 상태들을 이용하여 해결할 수 있습니다.

메모이제이션을 통해 중복 계산을 피할 수 있고, 각 상태에서 필요한 최소 연산 횟수를 저장하여 효율적으로 문제를 해결할 수 있습니다.

알고리즘 계획

1부터 x까지의 모든 수에 대해 최소 연산 횟수를 저장할 배열 dp를 생성합니다.
초기 상태인 dp[1]을 0으로 설정합니다 (1은 이미 1입니다).
루프를 이용하여 2부터 x까지 반복합니다:

dp[i] = dp[i-1] + 1 (1을 빼는 경우)
만약 i가 2로 나누어 떨어진다면 dp[i] = min(dp[i], dp[i/2] + 1) (2로 나누는 경우)
마찬가지로 i가 3으로 나누어 떨어진다면 dp[i] = min(dp[i], dp[i/3] + 1) (3으로 나누는 경우)

최종적으로 dp[x]를 출력합니다.

스위프트 구현 코드


import Foundation

func minOperationsToOne(_ x: Int) -> Int {
    var dp = Array(repeating: Int.max, count: x + 1)
    dp[1] = 0
    
    for i in 2...x {
        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]
}

let input = Int(readLine()!)!
print(minOperationsToOne(input))

성능 평가

이 알고리즘의 시간 복잡도는 O(n)입니다. n은 주어진 정수 x입니다. 각 정수에 대해 최대 3번의 연산을 고려하기 때문에 효율적입니다.

공간 복잡도는 O(n)으로, dp 배열을 사용하여 모든 상태를 저장합니다. 이는 메모리 사용량이 많을 수 있으므로, 필요에 따라 더 최적화할 수 있습니다.

결론

정수를 1로 만드는 알고리즘 문제는 동적 프로그래밍의 기본적인 원리를 잘 보여줍니다. 이 문제를 해결함으로써 스위프트 코딩 테스트에 대한 이해를 높이고, 동적 프로그래밍 기법을 적용하는 방법을 배울 수 있습니다.

문제를 해결하는 과정에서 각 연산에 대한 이해와 최적해를 찾기 위한 사고 과정을 기를 수 있습니다. 다양한 입력 값에 대하여 알고리즘의 성능을 시험해보고, 에러 핸들링 및 다양한 최적화 방법에 대해서도 고민해보시기 바랍니다.

이 글에서 다룬 ‘정수를 1로 만들기’ 문제는 실전 코딩 테스트에서도 자주 등장할 수 있는 유형이므로, 충분한 연습을 통해 숙달하시기를 권장합니다.