자료구조/알고리즘 - 재귀1

재귀

✅ 문제를 작은 단위로 쪼개며 진행하면서 가장 작은 단위로 쪼개었을 때 문제를 해결하고 다시 큰 단위로 돌아가면서 전체의 문제를 해결하는 방식

1. 재귀 함수의 입력값과 출력값 정의하기
2. 문제를 쪼개고 경우의 수를 나누기
   recursive case = 작은 단위로 쪼개는 과정
3. 단순한 문제 해결하기 -> 더 이상 문제를 쪼갤 수 없을 때 base case 탈출조건 구성
   base case =재귀의 기초 = 문제를 가장 작은 단위로 쪼갰을 때 해결하는 방식 = 재귀의 탈출 조건
4. 복잡한 문제 해결하기
5. 코드 구현하기

코플릿 회고

14.unpackGiftbox

선물 상자에 대한 정보를 담은 배열 giftBox 과 문자열 wish 을 입력받아 조건에 맞는 선물이 있는지에 대한 여부를 리턴

const giftBox = ['macbook', 'mugcup', ['eyephone', 'postcard'], 'money'];
let output = unpackGiftbox(giftBox, 'iphone');
console.log(output); // --> false
output = unpackGiftbox(giftBox, 'postcard');
console.log(output); // --> true

My code

function unpackGiftbox(giftBox, wish) {
  // TODO: 여기에 코드를 작성합니다.
  if(giftBox.length === 0 || wish === '') return false;

  let head = giftBox[0];
  let tail = giftBox.length === 1 ? [] : giftBox.slice(1);


  if(Array.isArray(head)){
    //배열이라면 새로운 배열을 만들어 재귀
    return unpackGiftbox([...head, ...tail], wish);
  }
  
  //base case
  //배열이 아니라면 head와 wish 비교
  if(head === wish) return true;
  //다르면 tail을 재귀
  else return unpackGiftbox(tail, wish);
}

head와 tail로 나누어준 후, head의 배열 유무에 따라서 재귀 시켜주었다.
처음시도할 때는 배열일 경우에 tail 은 순회하지 않아서 그냥 spread syntax로 새로운 배열을 만들어 재귀 시켜주어 해결하였다.

뭔가 이상한 구석이 있지만 test case 통과는 되었는데,
재귀부분에 있어서 함수 unpackGiftbox의 재귀 호출 횟수는 giftBox가 중첩된 정도와 비슷해야 합니다 라는 이유로 통과되지 못했다.
왜일까,,,?

Reference

1. 재귀 함수의 입력값과 출력값 정의하기
   [str], str => boolean
2. 문제를 쪼개고 경우의 수를 나누기

• 쪼갤 수 없는 경우 : 빈 배열이나 빈 문자열을 입력받은 경우
• 쪼갤 수 있는 경우 : unpackGiftbox(giftBox, wish)

3. 단순한 문제 해결하기

• unpackGfitbox([], '') => false
• giftBox !== wish => false

4. 복잡한 문제 해결하기

• [[2, [[3]]], 4, [[[5]]]]

5. 코드 구현하기

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

다차원 배열을 입력받아 1차원 배열로 변환하여 리턴

let output = flattenArr([[1], 2, [3, 4], 5]);
console.log(output); // --> [1, 2, 3, 4, 5]
output = flattenArr([[2, [[3]]], 4, [[[5]]]]);
console.log(output); // --> [2, 3, 4, 5]

• head, tail 로 분리
  • head 가 배열일 경우 (head : [1] , tail : [2, [3,4], 5])
    head에 tail을 덧붙여 새로운 배열을 만들어 재귀 => [...head , ... tail] (=[1,2,[3,4],5)
  • head 가 배열이지 않을 경우
    tail을 재귀시켜 head에 덧붙여줌 => [head].concat(flattenArr(tail))

function flattenArr(arr) {
	if(arr.length === 0) return false;
  	
  	let head = arr[0];
  	let tail = arr.length === 1 ? [] : arr.slice(1);
  
  	if(Array.isArray(head)){
		return flattenArr([...head, ...tail]);
    }
  	return [head].concat(flattenArr(tail));
}