[BaekJoon 1463][⚪3] 1로 만들기
❓ 문제
🎯 난이도
Silver ⚪3
🧠 풀이
1. 내 풀이 (DP - “Bottom-Up”)
- 알고리즘
Dynamic Programming
- 설명
DP 중에서도 Bottom-Up 방식을 사용하는 풀이이다.
Bottom-Up 방식이란 DP를 할 때, 밑에서부터 위로 올라가며 순차적으로 값을 '누적'해나가며 원하는 값을 마지막에 얻는 방식이다. 따라서 보통 반복문으로 이전의 낮은 값들을 사용해 현재의 높은 값을 갱신하는 방식으로 많이 구현이 된다.
구현 방식이 단순하고 반복문을 사용하므로 속도도 빨라서 가장 많이 사용되는 DP 방식이라고 볼 수 있다.
N의 값을 구하기 위해 N번 반복하므로 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iNum{};
cin >> iNum;
// iNum까지의 DP 배열
vector<int> vecDP(iNum + 1);
vecDP[1] = 0;
for(int i = 2; i < iNum + 1; ++i)
{
// -1 했을때를 최대값으로 잡음
vecDP[i] = vecDP[i - 1] + 1;
// 3으로 나눌 수 있는 경우
if(i % 3 == 0)
{
vecDP[i] = min(vecDP[i], vecDP[i / 3] + 1);
}
// 2로 나눌 수 있는 경우
if(i % 2 == 0)
{
vecDP[i] = min(vecDP[i], vecDP[i / 2] + 1);
}
}
cout << vecDP[iNum];
return 0;
}
2. 추가 풀이 (DP - “Top-Down”)
- 알고리즘
Dynamic Programming
- 설명
DP 중에서도 Top-Down 방식을 사용하는 풀이이다.
Top-Down은 구하고 싶은 값에서부터 순차적으로 아래로 내려가면서 필요한 값들을 모두 구한 뒤 한번에 원하는 값을 도출해내는 방식이다. 따라서 보통은 재귀 방식으로 구현이 되고, 필요한 값들을 실시간으로 저장하는 메모이제이션 방식이 필요하다.
보통 Bottom-Up에 비해 구현 방식이 복잡하고, 재귀와 메모이제이션으로 인해 메모리 할당, 실행 속도 모두 크게 늘어나기 때문에 특수한 경우에 많이 쓰이는 방식이다.
위와 같은 원리로 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int DP(vector<int>& vecDP, int iNum);
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iNum{};
cin >> iNum;
vector<int> vecDP(iNum + 1, -1);
cout << DP(vecDP, iNum);
return 0;
}
// 재귀 방식으로 DP를 구하는 함수
int DP(vector<int>& vecDP, int iNum)
{
// 1이면 0 반환
if(iNum == 1)
{
return 0;
}
// 현재 iNum 인덱스의 배열 값을 레퍼런스로 받아옴
int& iDP{ vecDP[iNum] };
// 값이 들어있는 경우 현재값 반환
if(iDP != -1)
{
return iDP;
}
// -1 했을 때를 최대값으로 잡음
iDP = DP(vecDP, iNum - 1) + 1;
// 3으로 나눌 수 있는 경우
if(iNum % 3 == 0)
{
iDP = min(iDP, DP(vecDP, iNum / 3) + 1);
}
// 2로 나눌 수 있는 경우
if(iNum % 2 == 0)
{
iDP = min(iDP, DP(vecDP, iNum / 2) + 1);
}
return iDP;
}
💭 후기
일단 성능상으로 보자면 첫 번째 방식의 Bottom-Up 풀이가 훨씬 좋다. 두 번째 풀이의 경우 '재귀'와 '메모이제이션' 때문에 메모리 '스택 프레임'에 계속해서 메모리 할당이 되고, 함수 호출 '오버헤드'로 속도가 느려지기 때문이다. 또한 상기한 이유로 구하려는 값이 커질 경우 스택 오버플로우의 위험 또한 존재한다.
하지만 Top-Down 방식도 상황에 따라선 쓸 데가 있고, 다만 이번 문제에서는 단순한 구현만으로도 쉽게 풀리는 문제였기 때문에 Bottom-Up 방식이 유리했을 뿐이다. 문제에 따라 어떠한 방식을 선택할지를 잘 고민하는게 중요하다.
Comments