오늘부터 랜덤하게 백준 문제를 푼 뒤, 알고리즘을 풀어나가는 과정을 기록한다.
문제를 무작정 많이 풀어나가기 보다는 내가 무슨 생각을 하는지 관찰해보자.
백준에 있는 실버 2 티어 문제 A -> B이다.
어떤 정수 A를 B로 바꾸는 데에, 최소 몇 번의 연산이 필요한 지 묻고 있다.
연산의 종류는 X2, N1이다.
나는 이런 문제를 풀 때, 주어진 조건의 범위를 가장 먼저 봐야한다고 생각한다.
문제에 보면, 위와 같이 10^9 즉, 10억의 범위를 가진다.
이는 연산을 진행했을 때, 정수형의 최대 범위인 21억을 넘을 가능성이 있으므로,
우선 long long 자료형을 사용해야할 것 같다.
그럼 이제 문제의 로직을 한 번 생각해보자. 어떤 식으로 풀어야 할까?
단순히 for문을 이용해서 풀 수 있을까? 한 번 생각해보았다.
X2에 대한 연산은 for문의 iterator를 이용하여 계산할 수 있다.
하지만 N1과 같이 숫자 뒤에 1을 붙여야 하는 연산은?
단순히 for문으로는 계산할 수 없다.
그럼 재귀함수를 이용해서 계산을 하며 넘겨주는 건 어떨까?
시작하는 A와 B의 차이가 매우 클 때, Stack overflow의 위험이 살짝 걱정된다.
한 번 진행해보자.
#define ll long long
ll start = 0, target = 0, answer = 999999999;
bool isPossible = false;
void recursion(ll depth, ll result) {
if (result == target) {
isPossible = true;
answer = min(answer, depth);
return;
}
if (result > target)
return;
recursion(depth + 1, result * 2);
string temp = to_string(result);
temp = temp + '1';
recursion(depth + 1, stoll(temp));
}
int main(){
cin >> start >> target;
recursion(1, start);
if (isPossible)
cout << answer;
else
cout << -1;
return 0;
}위의 코드로 예제를 돌려보니 모두 잘 나옴을 확인했다.
제출을 했을 때, 운이 좋게도 정답이었다!
내가 문제를 푼 방식은 DFS(깊이 우선 탐색) 방식이다.
해당 방식은 leaf node까지 쭉 들어갔다가 나오는 방식이기 때문에,
stack 자료구조를 통해서도 구현이 가능한 방식이다.
내가 위에서 푼 방식은, X2 연산만 먼저 쭉~ 진행을 한 다음에,
목표로 하는 수인 B보다 커지면 return, 즉 stack에서 pop을 한다.
이 때, 다음 함수인 N1 연산을 한 번 진행하고, 다시 X2 연산을 하게 된다.
깊이 우선으로 탐색하는 것은 다양한 연산의 조합을 시도하기엔 부적절한 것 같다.
BFS(너비 우선 탐색)를 사용하게 된다면 어떨까?
leaf node를 쭉 들어가는 것이 아닌, 이웃 노드들부터 차례로 탐색한다.
그렇기에, queue 자료구조를 통해서 구현을 하는 방식이다.
그렇다면 X2 연산을 진행해서 queue에 넣어보고, 이후 해당 node를 탐색할 때,
X2와 N1을 둘 다 연산해서 queue에 넣어볼 수 있는 것이다.
이 방식이 다양한 연산의 조합을 통해 결과를 찾기에는 더 적합한 것 같다.
아마 결과를 찾아내는 속도 또한 DFS보다는 BFS가 더 빠를 것이라고 생각된다.