[Algorithm] 재귀 알고리즘 배열 javascript 기본 문제 정리

 

 

Recursive Algorithm 기초

 

재귀 알고리즘은 base case 부터 시작한다. 먼저 탈출 조건을 세워놓고, 전체적인 문제를 분해해가면서 함수가 자신을 호출하는 구조를 세부적으로 구성하면서 답을 찾아낸다.

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

 

간단한 재귀 알고리즘을 살펴보자.

 

정수의 합

정수를 받아서 1까지의 합을 구하는 문제를 풀어보자. 

재귀의 단계가 반복되면서 입력값인 num을 넘겨주기 때문에 0 이하인 경우 탈출조건을 만들어 준다.

재귀 로직에서는 입력받은 num-1을 매개변수를 가지고 다시 함수 자신을 호출한다. 

function sum(num){

	// base case
    if(num<=0) return 0;
    
    // recursive logic
    return sum(num-1) + num;
}

 

홀수 구하는 재귀 알고리즘 로직

정수를 입력을 받아서 홀수 여부를 확인하는 로직이다. 손쉬운 계산을 방지하기 위해서 나누기와 나머지 연산(/, %)은 하지 않는 제약조건을 추가한다. 

입력값 : 15
출력값 : true

입력값 : 10
출력값 : false

 

먼저 탈출조건인 입력값이 0에 도달하는 경우 return 값을 false를 반환한다. 1 혹은 -1을 매개변수로 입력받는 경우 홀수이므로 true를 반환한다. 

재귀 로직으로는 odd() 함수 자신을 다시 호출해서 매개변수를 절대값으로 변형한 뒤 -2를 연산하여 매개변수로 전달해준다. 

function odd(num) {
  // TODO: 여기에 코드를 작성합니다.
  
  // 탈출 조건

  if(num===0) return false; // 짝수인 경우
  else if(num === 1 || num === -1) return true; // 홀수인 경우
  

  // 재귀 로직
  return odd(Math.abs(num)-2)
}

 

 

팩토리얼 값 구하는 문제

팩토리얼은 재귀 알고리즘에서 반드시 나오는 문제다. 5! = 5*4*3*2*1 식으로 계산하기 때문에 팩토리얼 값을 구할 때는 재귀 알고리즘을 사용한다.

 

문제 :

임의의 수를 입력받아 팩토리얼 값을 반환한다. 반복문은 사용하지 않고, 음수를 입력받지 않는다고 가정한다.

 

풀이 : 

먼저 탈출 조건을 세워준다. 입력값을 -1씩 더해주면서 함수를 호출하기 때문에 입력값이 0에 도달하는 경우를 탈출 조건(base case)로 구성한다. factorial(0)은 1을 반환한다.

재귀 로직에서는 현재 입력값과 함수 자신을 호출하는 로직을 구성한다. 재귀 로직을 풀어서 생각하면 num * (num-1) * ((num-1)-1) * ... 1 식으로 이어지게 된다.

 

function factorial(num) {
  // TODO: 여기에 코드를 작성합니다.
  
  if(num===0) return 1;

  return num*factorial(num-1);
}

 

 

피보나치 재귀 문제

문제 : 

임의의 수를 입력받아 피보나치 수열의 n 번째 요소를 리턴한다. 반복문을 사용하지 않는다. 

풀이 : 

피보나치는 0과 1에서 출발한다. n-2+n-1 = n 이 되는 식이다. 파보나치 수열은 0 1 1 2 3 5 8 13 --- 식으로 진행된다. 먼저 base case를 세워준다. 재귀 로직이 계속 이어지기 때문에 입력값 num이 0과 1인 경우 재귀로직이 끝나게 된다. 

소스코드 : 

function fibonacci(num) {
    // TODO: 여기에 코드를 작성합니다.
    
    switch(num){
        case 0: return 0;
        case 1: return 1;
    }

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

  }

 

 

배열 재귀 알고리즘 문제

배열에서 재귀는 인자를 사용해야 한다. 배열은 haed와 tail을 통해 재귀 알고리즘을 구성할 수 있다. head는 배열의 가장 첫번째 요소를, tail은 배열에서 head를 제거한 요소를 의미한다.

const arr = [1,2,3,4,5]

haed => 1
tail => [2,3,4,5]

 

배열의 요소를 모두 합산하는 문제를 풀어보자.

문제 :

배열을 매개변수로 입력받아서 모든 요소들의 합을 리턴한다. 반복문은 사용하지 않고 배열의 모든 요소는 정수라고 가정한다. 비어있는 배열의 경우 0을 반환한다.

풀이 : 

먼저 재귀의 탈출조건( base case)를 설정한다. 배열의 인자를 줄여나가면서 재귀 프로세스가 진행되기 때문에 배열의 길이가 0인 경우 0을 반환하고 탈출한다.

재귀 로직에서는 head와 tail을 사용한다. head는 arr[0]으로, tail은 arr.slice(1)을 사용해서 두 부분으로 나누고, 재귀함수에 tail을 매개변수로 전달한다. 

function arrSum(arr) {

  if(arr.length === 0) return 0;

  return arr[0] + arrSum(arr.slice(1));
}

console.log(arrSum([1,2,3,4,5]));
15

 

 

Drop 문제

문제 : 

임의의 수와 배열을 입력받아 N개의 요소가 제거된 새로운 배열을 반환한다.

풀이 : 

배열의 head와 tail로 구분한다. 입력받은 자연수 N 만큼 재귀 로직이 반복되기 되고 tail의 길이는 N만큼 삭제되게 된다. 

탈출 조건인 입력값이 0보다 같아지는 경우 줄어든 tail을 반환하게 된다. 

function drop(num, arr) {
  // TODO: 여기에 코드를 작성합니다.

  // base case : 
  if( num > arr.length) return [];
  else if(num <= 0) return arr;

  // recursion case:
  return drop(num-1, arr.slice(1));
}

 

Take 문제

문제 : 

임의의 자연수 N과 배열을 입력받아 N개의 요소만 포함된 새로운 배열을 반환한다.

풀이

재귀 알고리즘의 탈출 조건(Base Case)를 설정한다. 이 경우 임의의 자연수를 1씩 줄여나가면서 재귀 로직을 구성하기 때문에, 자연수 N이 0과 같아지는 경우나 배열의 첫번째 요소가 undefined 인 경우 빈 배열을 반환한다. 

재귀 로직에서는 head를 배열로 만들어서 concat() 함수를 사용해서 새로운 배열을 구성한다. concat()에 전달되는 매개변수는 입력받은 배열의 tail을 전달한다.

 

소스코드 :

function take(num, arr) {
  
  
  // base case
  if(num === 0 || (arr[0]===undefined)) return [];
    
  // reculsive logic
  return [arr[0]].concat(take(num-1, arr.slice(1)));
}

 

Reverse 배열 문제

문제 : 

임의의 배열을 입력받아 순서가 뒤바뀐 새로운 배열을 리턴한다.

풀이 : 

배열을 입력받고 먼저 head와 tail을 분리한다. 기존 순서가 head+tail 이었다면 반환할 배열은 tail+head로 변경되어야 한다. 

탈출조건으로는 생성되는 tail 의 길이가 0이 되는 경우다. 재귀 로직에서 tail을 생성하는 로직이 반복되기 때문에 입력받은 arr의 길이 만큼 재귀가 반복되면 tail의 길이는 0으로 수렴한다.

head와 tail로 분리된 arr을 tail + head로 합쳐주는 concat() 함수를 사용해 새로운 배열을 리턴하면 순서가 역으로 변경된 배열이 반환된다.

function reverseArr(arr) {
  
  if(arr.length === 0 ) return [];
    
  return reverseArr(arr.slice(1)).concat([arr[0]]);
}

 

 

 

[Blockchain] DApp(분산형 어플리케이션) 이란?