일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 트랜잭션
- 인터럽트
- CPU 스케줄링
- recoverability
- 김영한
- 개발남노씨
- 네트워크
- 반효경
- 운영체제와 정보기술의 원리
- B tree 데이터삽입
- 쉬운코드
- Git
- 백엔드
- SDK
- 데이터베이스
- 온디바이스AI
- 코딩애플
- BreadcrumbsComputer-Networking_A-Top-Down-Approach
- 시스템프로그래밍
- SQL
- 커널 동기화
- vite
- 시그널 핸들러
- 쉬운 코드
- 갤럭시 S24
- concurrency control
- 운영체제
- 프로세스 주소 공간
- 코딩테스트 [ ALL IN ONE ]
- Extendable hashing
- Today
- Total
티끌모아 태산
1463: 1로 만들기 본문
https://www.acmicpc.net/problem/1463
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
Dynamic Programming(동적계획법)
이 문제를 풀기 위해서는 '동적 계획법' 개념에 대해서 알고 있어야한다. DP는 큰 문제를 작은 문제로 나누어 푸는 알고리즘 기법이다. DP는 다음의 조건을 만족할 때 사용 가능하다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
따라서 동적 계획법은 작은 문제의 결과를 메모리에 저장해 두었다가, 같은 작은 문제가 나타날 때마다 이를 활용하여 문제를 풀 수 있다. 그렇기 때문에 메모리 공간을 사용하여 시간복잡도를 줄일 수 있다.
- O(N^2) -> O(f(n))으로 개선! 다항식 수준으로, 문제에 따라 다름. 일반적으로는 작은 문제의 정답을 저장해 두고 이를 활용하는 것이기 때문에 작은 문제의 수와 작은 문제를 푸는 시간의 곱이 된다. 따라서, 동적 계획법의 시간 목잡도는 다음과 같다. O(nk).
- n: 문제의 크기
- k: 작은 문제 수
동적 계획법의 구현 방법은 다음의 과정을 반복한다.
- 큰 문제를 작은 문제로 나눈다.
- 작은 문제를 풀어 정답을 구한다.
- 작은 문제의 정답을 저장한다.
- 큰 문제를 작은 문제로 나누어 1 ~ 3을 반복한다.
설명

위 와같이 연사 3가지를 활용해서 1을 만드는데 최소 연산 횟수를 구하는 것!

핵심 아이디어
- 상향식(bottom-up)으로 풀 수 있다.
예를들어, x=10인 경우, 1을 빼는 연산과 2 or 3으로 나누는 연산 중에 1을 더 빨리 만들기 위해서는 2 or 3의 배수를 먼저 만드는 것이 중요. 10 -> 9 -> 3 -> 1 과정을 거쳐 1이 되는데 9의 경우는 9 -> 3 -> 1과정을 거치며 3의 경우는 3-> 1의 과정을 거친다. 따라서 앞에서 구한 결과값을 저장해 두었다가 후에 사용하는 것!
먼저, 2 또는 3으로 나누어 떨어지지 않는 경우는 무조건 1을 빼는 연산을 수행한다.
- dp[i] = dp[i-1] + 1 에서 +1을 해주는 이유는 연산 횟수를 증가 시키는 것이기 때문
- 그리고 나서 dp[i]가 2와3으로 나누어 떨어지는 경우에는 dp[i](1을 빼는 경우)와 dp[i//2or3] + 1(나누었을 경우) 중 최솟값을 선택한다.
코드 구현
# 1 <= n <= 1000000
n = int(input())
# DP 테이블 초기화
# 연산 횟수를 저장하는 배열
d = [0] * 1000001 # 1번 인덱스부터 시작 가능
# 다이나믹 프로그래밍 진행(bottom-up)
for i in range(2, n+1): # 2부터 n까지 각 숫자에 대해 반복
# 현재의 수에서 1을 빼는 경우
d[i] = d[i-1] + 1 # +1 은 연산 횟수 1 증가의미
# 현재의 수가 2로 나누어 떨어지는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i//2] + 1)
# 현재의 수가 3으로 나누어 떨어지는 경우
if i % 3 == 0:
d[i] = min(d[i], d[i//3]+1)
# n을 1로 만드는 데 필요한 최소 연삿 횟수
print(d[n])
이 문제를 해결하기 위해, DP 테이블을 사용하여 작은 문제부터 차근차근 큰 문제로 나아가며, 각 숫자를 1로 만드는 최소 연산 횟수를 저장해 나간다. DP 테이블은 이러한 연산 횟수를 저장하는 배열이다.
d = [0] * 1000001 # DP 테이블을 초기화, 실제 계산은 1번 인덱스부터 시작
bottom-up 방식은 작은 문제들의 해를 바탕으로 점차 큰 문제의 해를 구해나가는 방식. 이를 통해 반복적으로 동일한 계산을 줄이고, 최종적인 문제의 해를 효율적으로 구할 수 있다.
print(d[1:11])
[0, 1, 1, 2, 3, 2, 3, 3, 2, 3]
print(d[10])
3
'백준 문제 > DP' 카테고리의 다른 글
2579: 계단 오르기 (0) | 2024.03.09 |
---|---|
1149: RGB거리 (0) | 2024.03.09 |
9095: 1,2,3 더하기 (0) | 2024.03.09 |