안녕하세요! 이번 강좌에서는 자바스크립트 코딩테스트 문제 중 하나인 “정수를 1로 만들기” 문제를 다루어 보겠습니다. 이 문제는 다양한 알고리즘 기법을 통해 해결할 수 있으며, 코드 작성 과정과 접근 방법을 함께 살펴보겠습니다. 문제의 접근 방식, 알고리즘 구현, 테스트 케이스, 그리고 최적화 방법에 대해 깊이 있게 설명하겠습니다.
문제 설명
정수 x가 주어질 때, 다음의 두 가지 작업 중 하나를 수행하여 이 정수를 1로 만드는 최소 작업 횟수를 구하세요:
- 짝수인 경우:
x → x / 2 - 홀수인 경우:
x → x - 1
예를 들어, x = 8이라면 다음과 같은 과정을 통해 1로 만들 수 있습니다:
8 → 4 → 2 → 1
위와 같은 경우 최소 작업 횟수는 3입니다.
접근 방법
이 문제를 해결하기 위해 상태 기반 접근 방식을 사용할 수 있습니다. 주어진 정수 x를 1로 만들기 위한 최적의 경로를 찾기 위해 BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)를 활용할 수 있습니다. 그러나 이 문제의 경우 BFS가 더 적합합니다.
BFS를 사용하여 해결하는 이유는 각 상태에 도달하기 위해 고려해야 할 경로가 여러 개인 경우가 많기 때문입니다. BFS는 각 단계에서 가능한 모든 경로를 탐색하므로 최적의 경로를 효율적으로 찾을 수 있습니다.
BFS 알고리즘 구현
이제 BFS 알고리즘을 사용하여 문제를 해결할 수 있는 자바스크립트 코드를 작성해 보겠습니다. 코드는 다음과 같습니다:
function minStepsToOne(x) {
const queue = [];
const visited = new Set();
queue.push(x);
visited.add(x);
let steps = 0;
while (queue.length > 0) {
const size = queue.length; // 현재 레벨의 노드 개수
for (let i = 0; i < size; i++) {
const current = queue.shift();
// 현재 숫자가 1이면 steps 반환
if (current === 1) {
return steps;
}
// 짝수일 경우
if (current % 2 === 0 && !visited.has(current / 2)) {
queue.push(current / 2);
visited.add(current / 2);
}
// 홀수일 경우
if (current > 1 && !visited.has(current - 1)) {
queue.push(current - 1);
visited.add(current - 1);
}
}
steps++; // 한 레벨 끝남
}
return steps;
}
// 예시 호출
console.log(minStepsToOne(8)); // 출력: 3
코드 설명
위 코드에서 사용한 알고리즘의 주요 내용을 설명하겠습니다:
- 큐(Queue) 사용: BFS는 큐 자료구조를 사용하여 구현됩니다. 큐에 각 상태를 추가하고, 하나씩 꺼내어 처리합니다.
- 방문 기록: 중복 방문을 방지하기 위해 방문한 상태를
Set자료구조에 기록합니다. - 단계 카운팅: 각 BFS 레벨을 진행할 때마다 단계를 증가시켜 총 작업 횟수를 기록합니다.
테스트 케이스
모든 문제 해결 과정에서 다양한 테스트 케이스를 고려하는 것이 중요합니다. 다음은 몇 가지 테스트 케이스입니다:
// 테스트 케이스
console.log(minStepsToOne(1)); // 출력: 0 (이미 1)
console.log(minStepsToOne(2)); // 출력: 1 (2 → 1)
console.log(minStepsToOne(3)); // 출력: 2 (3 → 2 → 1)
console.log(minStepsToOne(10)); // 출력: 5 (10 → 5 → 4 → 2 → 1)
console.log(minStepsToOne(25)); // 출력: 6 (25 → 24 → 12 → 6 → 3 → 2 → 1)
console.log(minStepsToOne(100)); // 출력: 7 (100 → 50 → 25 → 24 → 12 → 6 → 3 → 2 → 1)
최적화 방법
위의 BFS 알고리즘으로도 효율적인 결과를 얻을 수 있지만, 추가적인 최적화도 가능합니다. 예를 들어, 상태를 저장할 때 메모이제이션(Memoization)을 사용할 수 있습니다. 이 방법으로 이전에 계산한 값을 저장하여 불필요한 중복 계산을 줄일 수 있습니다.
결론
이번 강좌에서는 자바스크립트를 사용하여 “정수를 1로 만들기”라는 문제를 해결했습니다. BFS를 활용한 알고리즘을 설명하고, 코드 구현, 테스트 케이스, 그리고 최적화 방법까지 아우르는 자세한 내용을 다루었습니다. 다음 코딩 테스트에서도 이러한 문제 해결 능력을 발휘하실 수 있기를 바랍니다.