문제 개요
숫자 1에서 시작해 매 단계마다 5를 더하거나 3을 곱하는 연산을 반복하면, 무한히 많은 새로운 숫자를 만들어낼 수 있습니다. 우리가 작성해야 할 함수는 하나의 숫자를 입력받아, 이러한 덧셈과 곱셈의 조합으로 해당 숫자를 만들어낼 수 있는 수열이 존재하는지 찾고, 그 결과를 불리언(Boolean) 값으로 반환하는 것입니다.
예시
숫자 13은 먼저 3을 곱한 뒤 5를 두 번 더하면 만들 수 있습니다(1 × 3 + 5 + 5 = 13). 따라서 함수는 13에 대해 true를 반환해야 합니다. 반면 숫자 15는 어떤 조합으로도 만들 수 없기 때문에 false를 반환해야 합니다.
접근 방법
이 문제는 재귀(recursion)를 활용해 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재 값(
curr)에서 갈 수 있는 두 가지 경로, 즉 '5를 더하는 경우'와 '3을 곱하는 경우'를 모두 재귀적으로 시도합니다. - 현재 값이 목표 숫자보다 커지면 더 이상 답이 될 수 없으므로
false를 반환합니다. - 현재 값이 목표 숫자와 정확히 일치하면 수열이 존재한다는 뜻이므로
true를 반환합니다. - 두 경로 중 하나라도 성공하면 전체 결과는
true입니다. 이를 논리 OR(||) 연산자로 간결하게 표현할 수 있습니다.
구현 예제
const sequenceExists = (num, curr = 1) => {
if(curr > num){
return false;
};
if(curr === num){
return true;
};
return sequenceExists(num, curr+5) || sequenceExists(num, curr*3);
};
console.log(sequenceExists(18));
console.log(sequenceExists(15));
console.log(sequenceExists(32));
console.log(sequenceExists(167));
console.log(sequenceExists(17));
console.log(sequenceExists(1119));실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
true
false
true
true
false
true
동작 원리 살펴보기
sequenceExists(13)을 호출하면 다음과 같은 흐름으로 동작합니다.
- curr = 1 → 3을 곱해 curr = 3 탐색
- curr = 3 → 5를 더해 curr = 8 탐색
- curr = 8 → 5를 더해 curr = 13에 도달 →
true반환
반면 15의 경우, 가능한 모든 경로를 탐색해도 정확히 15에 도달하지 못한 채 목표 값을 초과하게 되므로 최종적으로 false가 반환됩니다.
각 단계마다 두 가지 선택지가 있으므로 이 알고리즘의 최악의 시간 복잡도는 O(2ⁿ)입니다. 다만 curr > num인 분기를 조기에 잘라내는 가지치기(pruning) 덕분에 실제 탐색 범위는 크게 줄어들어 효율적으로 동작합니다.