모든 자연수 x에 대해서 현재 값이 x이면 x가 짝수일 때는 2로 나누고, x가 홀수일 때는 3 * x + 1로 바꾸는 계산을 계속해서 반복하면 언젠가는 반드시 x가 1이 되는지 묻는 문제를 콜라츠 문제라고 부릅니다.
그리고 위 과정에서 거쳐간 모든 수를 기록한 수열을 콜라츠 수열이라고 부릅니다.
계산 결과 1,000 보다 작거나 같은 수에 대해서는 전부 언젠가 1에 도달한다는 것이 알려져 있습니다.
임의의 1,000 보다 작거나 같은 양의 정수 n이 주어질 때 초기값이 n인 콜라츠 수열을 return 하는 solution 함수를 완성해 주세요.
제한사항
- 1 ≤ n ≤ 1,000
나의 풀이
// 짝수
const even = (n) => {
return n / 2;
}
// 홀수
const odd = (n) => {
return 3 * n + 1;
}
function solution(n) {
let result = [];
result.push(n)
while (n > 1) {
n % 2 === 0 ? n = even(n) : n = odd(n);
result.push(n)
}
return result;
}재귀를 이용해서 풀고 싶었지만?... 고민하면서 코드 쓰다가 걍 풀어져버림. 어...? 하고 일단 제출 ㅎ
- 짝수일 경우의 연산과 홀수일 경우의 연산을 따로 함수로 빼두었다. 코드가 지져분해지는 것이 싫어서 그렇게 풀이함
- x의 값을 담을 빈 배열을 선언한 후 초기 값인 n을 먼저 배열에 넣어주었다.
- while 루프를 돌며 n이 1보다 클 경우에 한해 연산을 계속한다. 짝수일 경우 even()함수를 호출, 홀수일 경우 odd()함수를 호출하여 n에 재할당 해준다.
- 바뀐 n 값을 result 배열에 추가한다.
- 마침내 n이 1보다 작아지면 결과 배열(result)를 반환한다.
다른 풀이 1
function solution(n, arr = []) {
arr.push(n)
if (n === 1) return arr
if (n % 2 === 0) return solution(n / 2, arr)
return solution(3 * n + 1, arr)
}재귀 풀이 발견!!
- solution 함수에서 인자를 두 개 받는다. 하나는 현재 숫자 n과 결과 배열 arr이다.
- 먼저 현재 숫자 n을 결과 배열 arr에 추가한다.
- 만약 n이 1이라면 현재 결과 배열 arr을 반환한다.
- 만약 n이 짝수라면 n을 2로 나눈 값을 가지고 재귀적으로 solution 함수를 호출한다.
- 만약 n이 홀수라면 3 * n + 1의 값을 가지고 재귀적으로 solution 함수를 호출한다.
이 코드는 무한 루프에 빠지지 않으며 동작한다! 재귀 호출 시 n이 1이 되면 종료하기 때문이다.
위에서 내가 푼 코드는... while 조건문에 =을 붙일 경우 런타임 레어가 난다. 왜냐면 n이 1이 되었을 때도 계속해서 루프가 실행되기 때문이다. even 함수가 계속해서 n = n / 2를 수행하게 된다. (해보고 알았습니다)
다른 풀이 2
function* collatz(num) {
let value = num;
yield value;
while (value !== 1) {
value = value % 2 ? 3 * value + 1 : value / 2;
yield value;
}
}
function solution(n) {
return [...collatz(n)];
}대체 yield키워드가 머임...? 당황스러운 코드라서 찾아보고 왔다.
제너레이터 함수를 사용한 답안이라고 한다. (함수 실행을 일시 중지했다가 나중에 재개할 수 있는 특별한 함수)
collatz함수는 제너레이터 함수이다. 이는 입력받은 숫자 num에 대해 콜라츠 추측 과정을 반복하고 각 단계의 값을yield를 통해 반환한다.- solution 함수는 collatz 함수를 호출하고, 결과를 배열로 변환하여 반환한다.
제너레이터 함수 동작 방식
- collatz 함수가 처음 호출되면 value는 입력받은 num으로 초기화된다.
yield value는 현재 value를 반환하고, 함수 실행을 일시 중지한다.- 다음에 collatz 함수가 호출되면 이전에 중지된 지점부터 실행을 재개한다.
- value가 1이 될 때까지 반복적으로 value를 업데이트하고 yield value를 통해서 반환한다.
제너레이터 함수
함수 실행을 일시 중지했다가 나중에 재개할 수 있게 하는 자바스크립트의 고급 기능
ㅇㅅㅇ... 정말 이런 개념을 처음 알았다. 신기하다.
- 일반 함수와 다르게
function*으로 선언한다. - 함수 내부에서
yield키워드를 사용하면 함수를 일시 중지할 수 있다. - 다음에 제너레이터 함수가 호출되면 이전에 중지된 지점부터 실행을 재개한다.
- 제너레이터 함수는 값을 하나씩 순차적으로 반환할 수 있다.
**yield 키워드
- 제너레이터 함수 내부에서 사용된다.
- 함수 실행을 일시 중지하고, 현재 값을 반환한다.
- 다음에 제너레이터 함수가 호출되면, 이전에 yield에서 중지된 지점부터 실행을 재개한다.
- yield를 통해 값을 하나씩 순차적으로 반환할 수 있다.
제너레이터 함수의 장점
- 메모리 사용량이 적다.
- 복잡한 반복 작업을 간단하게 구현할 수 있다.
- 코드가 간결하고 가독성이 좋다.
- 무한한 시퀀스를 생성하거나 대용량 처리를 할 때 유용하게 사용할 수 있다.
