코딩 시험은 점점 더 많은 기업들에서 필수적으로 진행되고 있으며, 자바스크립트는 웹 개발에서 가장 인기 있는 언어 중 하나입니다.
이 강좌에서는 자바스크립트를 사용하여 코딩 시험에서 흔히 나오는 알고리즘 문제를 풀어보겠습니다.
오늘의 주제는 ‘타임머신으로 빨리 가기’라는 문제입니다.
문제 설명
당신은 타임머신을 조작할 수 있는 과학자입니다. 타임머신은 특정 시간으로 이동할 수 있으며,
두 개의 정수 a, b가 주어졌을 때, a에서 b로 이동하는 데 걸리는 최소 시간 (이동 횟수를 의미)
을 계산해야 합니다. 타임머신은 다음과 같은 규칙을 따릅니다:
- 현재 위치에서 1을 더하거나 1을 뺄 수 있습니다.
- 현재 위치를 2배로 만들 수 있습니다.
주어진 a와 b에 대해 최소한 몇 번의 이동으로 a에서 b로 이동할 수 있는지를 계산하는 함수를 작성하세요.
입력 형식
– 두 개의 정수 a (0 ≤ a ≤ 105), b (0 ≤ b ≤ 105)가 주어집니다.
출력 형식
– a에서 b로 이동하기 위한 최소 이동 수를 정수로 출력합니다.
예제
입력: a = 2, b = 9
출력: 4
입력: a = 5, b = 22
출력: 7
문제 풀이 접근 방법
이 문제를 해결하기 위해 우리는 BFS(너비 우선 탐색)를 사용할 것입니다. BFS는 최단 경로를 찾는 데 적합한 알고리즘으로,
주어진 상태에서 가능한 모든 상태를 탐색하여 목표 상태에 도달하는 가장 최소한의 이동 경로를 찾는 방식입니다.
이 경우, 각각의 상태는 타임머신이 위치할 수 있는 시간을 나타냅니다.
1단계: BFS 알고리즘 사용 준비
BFS를 구현하기 위해, 우리는 큐를 사용할 것입니다. 먼저, 시작 위치인 a를 큐에 추가합니다.
그리고 현재 위치에서 가능한 모든 이동을 큐에 추가하면서 목표 위치인 b에 도달할 때까지 반복합니다.
각 위치에서 가능한 이동은 다음과 같습니다:
- 현재 위치에서 1을 더하기
- 현재 위치에서 1을 빼기
- 현재 위치를 2배로 만들기
목표 위치에 도달할 때까지 각 이동의 횟수를 기록할 것이며, 목표에 도달했을 때의 이동 횟수를 출력합니다.
2단계: 코드 구현
function minimumMoves(a, b) {
if (a >= b) return a - b; // a가 b보다 크거나 같으면 정해진 시간 만큼 차감하는 것으로 이동 횟수 결정
const queue = [[a, 0]]; // [현재 위치, 이동 수]
const visited = new Set(); // 방문한 위치 기록
visited.add(a); // 시작 위치를 방문 처리
while (queue.length > 0) {
const [current, moves] = queue.shift();
// 가능한 모든 이동
const nextMoves = [current - 1, current + 1, current * 2];
for (let next of nextMoves) {
if (next === b) return moves + 1; // 목표 위치에 도달하면 이동 수 반환
if (next < 0 || next > 100000 || visited.has(next)) continue; // 유효 범위 내에서 방문하지 않은 경우만
visited.add(next); // 다음 위치 방문 처리
queue.push([next, moves + 1]); // 다음 위치와 이동 수 큐에 추가
}
}
}
3단계: 알고리즘 복잡도 분석
알고리즘의 시간 복잡도는 O(n) 입니다.
최악의 경우 모든 가능한 위치를 탐색해야 하므로 O(n)에 해당하고,
공간 복잡도도 O(n)입니다. 큐와 방문 기록을 위한 공간을 고려하면 이러한 복잡도가 발생합니다.
4단계: 최적화 가능성
이 알고리즘은 이미 BFS를 기반으로 하여 최단 경로를 탐색하고 있으므로
추가적인 최적화는 필요하지 않습니다. 그러나 상황에 따라
DFS(깊이 우선 탐색)를 적용할 수도 있지만, 이 문제에서는 BFS가 더 효과적입니다.
5단계: 결론
‘타임머신으로 빨리 가기’ 문제를 통해 BFS의 원리를 간단히 이해하고,
자바스크립트를 활용하여 문제를 해결하는 방법을 배웠습니다.
이런 방식으로 다양한 문제를 해결할 수 있으며,
코딩테스트에서 좋은 성적을 얻기 위해 기본적인 알고리즘을 숙지하는 것이 중요합니다.
추가 자료
– BFS 알고리즘에 대한 심화 연구 및 다양한 문제 풀이를 연습하기 위해 다음의 자료를 추천드립니다.