[Algorithm] 재귀 알고리즘 문제 Javascript

 

 

피보나치 문제

 

문제

0<= N <= 15 자연수를 입력받아 피보나치 수열의 N 번째 요소를 출력하라

 

입력

0<= N <= 15

 

소스코드 

function fibonacci(num) {
    switch(num){
        case 0: return 0;
        case 1: return 1;
    }

    return fibonacci(num-1) + fibonacci(num-2);
  }

 

 

배열의 곱

 

문제

배열을 입력받아 모든 배열의 요소의 곱을 출력하라

 

입력

number 타입의 요소를 가진 배열

 

소스코드 

간단한 재귀 알고리즘 문제다. 먼저 탈출조건을 생성해준다. 모든 요소를 순회 후 마지막 탈출지점에 도달했을 때는 배열의 길이가 0이기 때문에 이를 조건으로 걸고 1을 반환한다. 

재귀 조건에는 배열의 가장 앞 요소를 출력하고 나머지 요소를 담은 배열을 매개변수로 다음 재귀 함수에 인자로 전달한다. 

function recurProduct(arr) {
    
    // 탈출조건
    if(arr.length === 0) return 1;

	// 재귀 조건
    return arr.shift() * arrProduct(arr);
  }

 

 

 

배열의 특정 요소 추출하기

 

문제

임의의 자연수 N과 배열을 입력받는다.  차례대로 N개의 요소만 포함된 새로운 배열을 반환하라.

 

소스코드 

재귀함수의 탈출조건은 주어진 자연수가 0이 되거나, 배열의 길이가 0인 경우(빈 배열을 입력받는 경우) 두가지 조건에서 빈 배열을 반환하고 재귀 함수를 종료한다.

 

주어진 임의의 자연수 갯수만큼 배열의 요소를 출력한다. 첫번째 배열의 요소부터 차례대로 출력해야 하기 때문에 먼저 배열을 Head와 Tail로 분리한다.

 

새로운 요소가 포함된 새로운 배열을 반환하기 위해서 head를 먼저 배열에 넣어주고 Javascript 배열 내장 메소드 중 concat() 메소드를 사용해서 재귀 함수를 수행한다. push와 concat 메소드가 헷갈린다면 [Javascript] 배열 메소드 Array Method 정리 를 참고하길 바란다.

 

function takeElement(num, arr) {
  
  // Base Case  
  if(num === 0 || arr.length===0 ) return [];

  // Recursive Case
  const [head, ...tail] = arr;

  return [head].concat(take(num-1, tail))
}

 

 

※ 배열 내장 요소 추가 함수 

Javascript 배열 내장 함수에는 크게 push()와 concat()이 있다. push는 요소를 추가하고 기존 배열을 변형시킨다. 출력값으로는 새로 추가된 요소의 위치값을 반환한다.

반면 concat() 메소드는 원본 배열을 변형시키지 않고, 참조값을 가지고 새로운 요소가 추가된 새로운 배열을 반환한다.

 

 

논리합 재귀 알고리즘 문제

 

문제

배열을 입력받아 모든 요소의 논리합을 리턴한다. 빈배열이 주어질 경우 false를 반환한다.

 

소스코드

Base Case에서 빈 배열의 경우 false를 반환한다.

주어진 배열을 head와 tail로 나눈 후 논리합을 리턴하는 재귀 함수를 호출한다.

function or(arr) {
	// Base Case
    if(arr.length === 0) return false;

	// Recursive Case
    const [head, ...tail] = arr;
    return head || or(tail);
}

 

 

순서가 뒤집힌 배열 구하기

 

문제

배열을 입력받아 순서가 뒤집힌 새로운 배열을 반환한다. 빈 배열의 경우 주어진 배열을 그대로 반환한다.

 

소스코드

빈 배열의 경우 배열 그대로를 반환하는 탈출 조건을 생성한다. 

주어진 배열을 head와 tail로 구분한 후 tail과 head를 뒤집은 형태로 재귀함수를 호출한다.

function reverseArr(arr) {
	// Base Case
    if(arr.length === 0) return arr;

	// Recursive Case
    const [head, ...tail] = arr;

    return reverseArr(tail).concat(head);

}

 

 

Matryoshka 인형 찾기

 

문제

러시아 전통 인형 Matryoshka에 관한 정보를 담은 객체와 임의의 정수가 주어진다. 주어진 조건에 맞는 인형이 존재하는지 Boolean 값을 반환하라.

• 객체는 Matryoshka, size 두개의 키~값으로 구성된다.
• matryoshka.matryoshka는 null 혹은 matryoshka 객체로 구성된다.
• matryoshka.size는 중첩될 수록 작아진다.

 

소스코드

Base Case에서는 빈 객체인 경우와 matryoshka 객체가 null 인 경우 false값을 반환한다.

 

Recursive Case에서는 주어진 size가 객체 내 존재하는지 확인 후 true값을 반환한다. 이 후 자기 자신을 호출하는 재귀함수를 반환하면서 재귀 알고리즘을 구성한다.

 

☆ 코드를 다 작성하고 보니 간단하지만 객체를 순회하는 재귀 알고리즘을 구성하는게 자칫 헷갈릴 수 있다. 객체가 비어있는 경우는 Object.keys()로 확인한다. 이 메소드는 객체내의 키 값을 배열형태로 반환해준다. 

function findMatryoshka(matryoshka, size) {

	// Base Case
    if(matryoshka === null || Object.keys(matryoshka).length===0) return false;

	// Recursive Case
    if(matryoshka.size === size) return true;

    return findMatryoshka(matryoshka.matryoshka, size);
  }

 

 

 

다차원 배열 선물상자 풀기

 

문제

선물 상자에 대한 정보를 담은 배열과 탐색할 문자열을 입력받는다. 조건에 맞는 문자열이 배열내 존재하는지 확인 후 Boolean 값을 반환하라.

입력값으로는 문자열과 배열이 무작위로 섞여 재귀적으로 정의된 배열을 입력받는다. 문자열은 선물 상자 내 존재하는 선물의 이름을 의미한다. 

 

소스코드

solution1 Array.prototype.reduce() 내장 메소드 사용

reduce 메소드를 사용해서 재귀 함수를 누적으로 호출한다. 

① 첫번째 조건문에서 문자열이 배열내 존재하는지 확인 후 true 값을 반환한다.

② 두번째 조건문에서 만약 배열의 요소가 배열의 형태면 재귀 함수를 호출하고, 결과값을 누적값과 논리합한다.

③ 마지막으로 문자열과 일치하지 않고, 배열도 아닌 상태라면 누적값을 반환한다.

④ reduece 메소드의 초기값은 false로 시작한다.

function unpackGiftbox(giftBox, wish) {

    /*
        Solution 1 : reduce 메소드 사용
    */
	
    const result = giftBox.reduce((acc, cur)=>{
        if(cur === wish){
            return true
        }else if(Array.isArray(cur)){
            return unpackGiftbox(cur, wish) || acc;
        }else{
            return acc;
        }
    }, false);

    return result;
}

 

for 반복문 사용

① 배열의 모든 요소를 순회한다.

② 만약 배열의 요소가 문자열을 포함하면 true를 반환한다. 

③ 만약 요소가 배열이라면 result 변수에 unpackGiftbox 메소드의 결과값을 저장한다. 만약 결과값이 true라면 true를 반환한다.

④ 결과값의 초기값은 false로 지정한다.

 

function unpackGiftbox(giftBox, wish) {

    /*
        Solution 2 : For 반복문 사용
    */

    for(let i=0; i<giftBox.length; i++){
        if(giftBox[i].includes(wish)) return true;
            if(Array.isArray(giftBox[i])) {
                let result = unpackGiftbox(giftBox[i], wish);
                if(result) return true;
        }
    }

    return false;
}

 

 

평평한 배열 만들기

 

문제

입력값으로 다차원 배열을 받아 1차원 배열로 변환하여 반환한다.

 

제약조건

• Array.prototype.flat, Array.prototype.flatMap() 함수 사용은 금지한다.
• 반복문(for, while) 사용은 가능하다.
• 입력받은 배열은 함수 호출뒤 원본값을 유지한다.
• 빈 배열을 입력받는 경우 빈 배열을 리턴한다.

 

소스코드

 

① 입력 배열의 첫 요소 부터 반복문으로 순회한다.

② 만약 배열의 요소가 배열이면 재귀함수를 사용해서 rest 파라미터를 사용해서 요소값들을 반환하고, 새로운 배열에 push 한다.

③ 만약 배열의 요소가 배열이 아니면 해당 요소를 새로운 요소에 추가한다.

④ 새로운 배열 result를 반환한다.

function flattenArr(arr) {

    let result = [];

    for(let key of arr){
        
        if(Array.isArray(key))
            result.push(...flattenArr(key));
        else{
            result.push(key);
        }
    }
    return result;
    
}

 

 

정리

 

재귀 알고리즘을 사용한 알고리즘 문제들을 풀어봤다. 원칙적으로는 Base Case와 Reculsive Case로 구분해서 알고리즘 로직을 구성하면 되지만, 문제는 Reculsive Case를 어떻게 설계하느냐다.

 

재귀 로직은 무한히 실행될 수 없다. 모든 재귀 알고리즘은 반복문으로 구현이 가능하다. 다만, 반복 횟수를 알수 없을 때 재귀 알고리즘이 효과적으로 작동할 수 있다.

 

재귀 알고리즘을 잘 풀기 위한 유일한 방법은 많은 재귀 알고리즘 문제를 만나 해결해보는 것이다. 조건값의 분기를 구성하고, 콜 스택에서 해제되어 반환되는 값을 어떻게 처리할 것인지에 대한 고민이 쌓이다 보면 재귀 알고리즘으로 파워풀한 소스코드를 작성할 수 있게 된다.

 

 

 

 

 

 

[Algorithm] 하노이의 탑 알고리즘 Javascript 구현하기

 

[Algorithm] 재귀 알고리즘이란 recursion algorithm