| 작성자 | 이재영 |
| 일 시 | 2024. 10. 31 (목) 18:00 ~ 21:00 |
| 장 소 | 미래관 424호 자율주행스튜디오 |
| 참가자 명단 | 임혜진, 이재영, 성창민, 김명원, 장원준 |
| 사 진 |  |
이번 모각코는 지난 시간에 공부했던 DP를 활용하여 관련 백준 문제를 풀어볼 것이다.
1. 백준 1463 - 1로 만들기
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
정수 X에 대하여 세 가지의 연산 방법 중 연산 횟수가 가장 적은 최솟값을 출력하면 되는 문제이다. 지난 시간 DP 문제 푸는 기본적인 단계를 거쳐서 풀어보자.
1) 문제 분석 및 부분 문제 정의
1로 만들기 문제에서 큰 문제는 정수 X가 세 가지의 연산 방법을 최소한으로 거친 횟수를 구하는 것이고, 이것을 작은 문제로 나눈다면, 정수 X에서 각각 3으로 나누기, 2로 나누기, 1 빼기 연산을 했을 때의 최소 연산 횟수를 구하는 것이다.
2) 점화식 도출
만약 dp(n)이 정수 n의 최소 연산 횟수라고 한다면, 정수 X가 3과 2의 배수인 경우에는, dp(n//3), dp(n//2), dp(n-1) 중 최소값을 선택하므로, 이 부분을 min(dp(n//3), dp(n//2), dp(n-1)) + 1으로 계산하게 된다. 정수 X가 3의 배수일 경우, min(dp(n//3), dp(n-1)) + 1 이고, 2의 배수인 경우 min(dp(n//2), dp(n-1)) + 1, 다 아닐 경우 dp(n-1) + 1이 될 것이다. 그러나 여기서도 dp(n-1)이 중복으로 들어가니 이것을 따로 빼내어 준다면 조금 더 가독성이 높은 코드가 될 것이다.
3) 메모이제이션, 타뷸레이션 둘 다 해볼 것이다.
4) 초기 조건 설정
메모이제이션과 같은 경우에는 종료 조건을 잘 설정해주어야 한다. 우선 이 문제에서 가장 작은 단위는 dp(2), dp(3), dp(4)가 될 것이다. 각 방법들이 한번 씩 다 쓰이는 방법들이다. 때문에 배열 설정은 dp = [0, 0, 1, 1, 2] + [-1] * 10^6(10^6보다 작은 적수를 입력받기 때문에)으로 해준다. 조금 더 효율적으로 해준다면 dp = [0, 0, 1, 1, 2] + [-1] * (n+1) 로 해주면 좋다. 이미 배열에 초기값을 설정해주었고, 문제에서 저 밑으로 내려갈 상황은 없기에 멈추는 조건은 if dp[n] != -1: return dp[n]과 dp[n] 연산을 완료 후 return 해주는 것으로 끝을 낸다.
타뷸레이션과 같은 경우에는 비슷하게 dp = [0, 0, 1, 1, 2] + [math.inf] * n로 해준다. math.inf로 해주는 이유는 코드에서 최솟값을 쓰기 때문에 메모이제이션과 같이 -1로 해버릴 경우 값이 달라질 수가 있다.
# 메모이제이션
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
dp = [0, 0, 1, 1, 2] + [-1] * pow(10, 6)
def d(n):
if dp[n] != -1: return dp[n]
dp[n] = d(n-1) + 1
if n % 3 == 0:
dp[n] = min(d(n//3) + 1, dp[n])
if n % 2 == 0:
dp[n] = min(d(n//2) + 1, dp[n])
return dp[n]
n = int(input())
print(d(n))import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
dp = [0, 0, 1, 1, 2] + [-1] * pow(10, 6)
def d(n):
if dp[n] != -1: return dp[n]
if n % 3 == 0 and n % 2 == 0:
dp[n] = min(d(n//3), d(n//2), d(n-1)) + 1
elif n % 3 == 0:
dp[n] = min(d(n//3), d(n-1)) + 1
elif n % 2 == 0:
dp[n] = min(d(n//2), d(n-1)) + 1
else:
dp[n] = d(n-1) + 1
return dp[n]
n = int(input())
print(d(n))
# 타뷸레이션
import sys
import math
input = sys.stdin.readline
n = int(input())
dp = [0, 0, 1, 1, 2] + [math.inf] * n
for i in range(5, n+1):
dp[i] = dp[i-1] + 1
if i % 3 == 0:
dp[i] = min(dp[i//3] + 1, dp[i])
if i % 2 == 0:
dp[i] = min(dp[i//2] + 1, dp[i])
print(dp[n])import sys
import math
input = sys.stdin.readline
n = int(input())
dp = [0, 0, 1, 1, 2] + [math.inf] * n
for i in range(5, n+1):
if i % 3 == 0 and i % 2 == 0:
dp[i] = min(dp[i//3], dp[i//2], dp[i-1]) + 1
elif i % 3 == 0:
dp[i] = min(dp[i//3], dp[i-1]) + 1
elif i % 2 == 0:
dp[i] = min(dp[i//2], dp[i-1]) + 1
else:
dp[i] = dp[i-1] + 1
print(dp[n])
메모이제이션과 타뷸레이션에서 각각 2개 씩 코드를 작성하였다. 초반에 코딩했던 것이 아래쪽에 있는 코드, 해결 이후 검색해보며 찾은 방법이 위에 코드이다. 2개의 코드를 보았을 때 나는 크게 차이점을 느끼지 못하였다. 가독성의 차이만 있을 뿐이지 효율적인 방면으로 보았을 때 아래에 있는 코드가 좀 더 효율적일 것이라고 생각했다. 왜냐하면 위에 코드는 연산 횟수가 너무 많아지기 때문이다. 만약 계산하려는 n의 값이 2, 3의 배수 모두 포함이 된다면 n-1의 연산까지 총 3번의 업데이트를 거치게 된다. GPT를 통해 비교해본 결과는 다음과 같다.
첫 번째 코드는 가독성 면에서 유리하고, 대부분의 경우에서 충분히 효율적입니다.
두 번째 코드는 n이 매우 큰 경우 미세하게 더 효율적일 수 있지만, 성능 차이가 크지 않습니다.
따라서 첫 번째 코드를 더 권장합니다.
라고 하였다. 두 번째 코드가 더 효율적인 것은 맞지만, 그 차이는 미미하다 라는 것이 결론이다.
오늘은 최대한 나의 힘으로 DP를 풀려고 노력했다. DP는 많이 풀어야 감이 잡힌다는 얘기를 많이 들었다. 확실히 점화식을 도출해내고, 초기조건을 잘 설정하는 것은 한 두번 해본다고 잘할 수 있을 것 같지 않았다. 앞으로 좀 더 연습을 해야겠다.