안녕하세요, 코딩테스트를 준비하고 있는 여러분! 오늘은 정수를 1로 만드는 문제를 함께 풀어보겠습니다. 이 문제는 알고리즘의 기초를 다지기에 아주 좋은 연습문제이며, 코틀린을 사용하여 해결해보도록 하겠습니다.
문제 설명
정수 N이 주어질 때, N을 1로 만드는 최소의 연산 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 아래와 같습니다:
- N이 3으로 나누어 떨어지면, N을 3으로 나눈다.
- N이 2로 나누어 떨어지면, N을 2로 나눈다.
- 1을 빼준다.
예를 들어, N이 10일 경우, 10 -> 9 -> 3 -> 1의 과정으로 3번의 연산이 필요합니다.
문제 접근 방법
이 문제를 해결하기 위해 다이나믹 프로그래밍(DP) 기법을 사용할 것입니다. DP는 기존의 문제들을 잘게 나누어 푸는 방식입니다. 이 문제의 경우, N을 1로 만들기 위한 각 숫자의 최소 연산 횟수를 저장하는 배열을 만들어 사용할 것입니다.
단계별 접근
- 배열 초기화: 정수 N의 크기만큼 배열을 만들고, 각 인덱스에 기본값으로 -1로 초기화합니다.
- 기저 사례 설정: 배열의 1번 인덱스에는 0을 저장합니다. 이는 1을 만드는 데 필요한 연산이 0임을 나타냅니다.
- 반복문을 통한 DP 테이블 업데이트: 2부터 N까지 반복문을 통해 각 숫자에 대해 최소 연산 횟수를 계산합니다. 이때, 나누기 연산과 빼기를 통해 새로운 값을 계산하고 이를 배열에 저장합니다.
- 결과 출력: 마지막에 계산한 N의 값을 메인 배열에서 가져와 출력합니다.
코틀린 코드
fun minOperationsToOne(n: Int): Int {
// 다이나믹 프로그래밍 테이블 초기화
val dp = IntArray(n + 1) { Int.MAX_VALUE }
dp[1] = 0 // 1은 1로 만들기 위해 0개의 연산 필요
for (i in 2..n) {
// 1 빼기
dp[i] = dp[i - 1] + 1
// 2로 나누기
if (i % 2 == 0) {
dp[i] = minOf(dp[i], dp[i / 2] + 1)
}
// 3으로 나누기
if (i % 3 == 0) {
dp[i] = minOf(dp[i], dp[i / 3] + 1)
}
}
return dp[n]
}
fun main() {
val n = 10 // 테스트 입력
println("정수를 1로 만드는 최소 연산 횟수: ${minOperationsToOne(n)}")
}
코드 설명
위 코드는 주어진 정수 N을 1로 만드는 최소 연산 횟수를 계산합니다. minOperationsToOne 함수는 정수를 입력받아 동적 프로그래밍을 통해 최소 연산 횟수를 구합니다. 각 연산별로 조건을 체크하여 가능한 최소 횟수를 업데이트합니다. 특히 2로 나누기와 3으로 나누기는 조건문으로 체크하여 적절한 경우에만 연산을 수행합니다.
실행 결과
위의 코드를 실행시키면, 주어진 입력 N에 대해 정수를 1로 만들기 위한 최소 연산 횟수가 출력됩니다. 예를 들어, N이 10인 경우, ‘정수를 1로 만드는 최소 연산 횟수: 3’이 출력됩니다.
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(N)입니다. 배열을 한 번 스캔하며 각 연산에 대해 상수 시간의 작업을 하기 때문에 효율적인 계산이 가능합니다. 공간 복잡도는 O(N)으로 DP 배열을 저장하기 위한 공간이 필요합니다.
결론
오늘은 정수를 1로 만드는 문제를 다루었습니다. 코틀린을 사용하여 문제를 풀면서 다이나믹 프로그래밍의 기초를 익힐 수 있었습니다. 이와 같은 유형의 문제는 취업 준비과정에서 자주 출제되므로, 꾸준히 연습하시는 것을 추천드립니다. 다음 강좌에서도 유익한 내용을 가지고 돌아오겠습니다!
참고 자료
감사합니다!