TIL Day-26

코드스테이츠 26일차

재귀함수와 관련된 문제들을 다시한번 풀어보면서 복습했다.
복습을 하다보면 내가 개념을 이해하고 풀고있는건지
그냥 문제 자체를 외워서 풀고있는건지 의문이 들기도한다.
이건 내가 제대로 공부하고있는걸까?

새로 배운 것들

재귀적으로 생각하기

재귀함수를 사용하기 위해 함수를 어떻게 재사용 할 수 있을지
또는 어떻게 써야될지에 대해 많은 고민을 하게된다.

재귀적으로 생각하기위해 문제를 쪼게고 쪼게
가장 간단한 문제부터 해결해나갈 수 있도록 생각하는게
쉽게 감이 잡히지 않는 경우가 있다.

특히 코플릿 문제 중 마트료시카 문제가 그랬었다.

해당 문제를 풀기위한 수도코드를 먼저 작성해보면 이렇게 볼 수 있다.

• size에 맞는 matryoshka가 있는 경우 true를 출력
  -- 빈 객체를 입력받은 경우 false를 리턴
• true가 아닐 경우 다음matryoshka에서 size와 동일한 matryoshka 찾기
  -- matryoshka속 matryoshka가 있을 경우에만 재귀함수 호출
  -- 입력받은 수보다 큰 수의 matryoshka 열기
• 이 외의 경우는 모두 false

// 러시아 전통인형 마트료시카에 대한 정보를 담은 객체와 수를 입력받아
// 조건에 맞는 인형이 있는지 여부를 리턴해야 합니다.

const matryoshka = {
  size: 10,
  matryoshka: {
    size: 9,
    matryoshka: null,
  },
};

let output = findMatryoshka(matryoshka, 10);
console.log(output); // --> true

output = findMatryoshka(matryoshka, 8);
console.log(output); // --> false

// 주의 사항
/**
 * 함수 findMatryoshka는 재귀함수의 형태로 작성합니다.
 * 반복문(for, while) 사용은 금지됩니다.
 * 입력받은 객체는 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
 * 빈 객체를 입력받은 경우, false를 리턴해야 합니다.
 */

이 문제를 재귀적으로 생각해보자

문제를 쪼개고 쪼개 가장 간단한 문제부터 해결하면
아마 이부분이 될 것이다.

// size에 맞는 matryoshka가 있는 경우 true를 출력

if (matryoshka.size === size) {
  return true
}

그리고 이부분도 쉽게 해결할 수 있을 것이다.

// 빈 객체를 입력받은 경우, false를 리턴해야 합니다.
if (matryoshka.size === size) {
  return true
} else {
  return false
}

그렇다면 true가 아니고 빈 객체가 아닐때에는 어떻게 해야될까?
이때에 마트료시카를 다시 열어볼 수 있도록
재귀함수를 사용할 수 있을 것이다.

// true값이 아닐 경우 다음 matryoshka에서 size와 동일한 matryoshka 찾기
if (matryoshka.size === size) {
  return true
} else {
  return findMatryoshka(matryoshka.matryoshka, size)
}

재귀함수를 불러올때의 인자는 마트료시카속 마트료시카일 것이고
우리가 비교할 size는 똑같은 값을 가지고 와야 될 것이다.
다만 여기엔 한가지 조건이 붙어야하는데
마트료시카 속 마트료시가가 있을때에만 열 수 있을 것이다.

// matryoshka 속 matryoshka 있을 경우에만 다음 재귀함수 호출
if (matryoshka.size === size) {
  return true
} else if (matryoshka.matryoshka) {
  return findMatryoshka(matryoshka.matryoshka, size)
}

여기서 또한가지 조건이 필요한데 마트료시카의 사이즈가
입력받은 수보다 커야한다는 것이다.
입력받은 수보다 작은 경우는 열 필요가 없기 때문이다.

// 입력받은 수보다 큰 수의 matryoshka 열기
if (matryoshka.size === size) {
  return true
} else if (matryoshka.matryoshka && matryoshka.size > size) {
  return findMatryoshka(matryoshka.matryoshka, size)
}

이렇게 작성하면 입력받은 수와 같은 크기의
마트료시카를 찾을 수 있을 것이다.
이제 여기에 이 조건에 맞지 않는 경우를 추가한다.

// 이외의 경우는 모두 false
if (matryoshka.size === size) {
  return true
} else if (matryoshka.matryoshka && matryoshka.size > size) {
  return findMatryoshka(matryoshka.matryoshka, size)
}
return false

이런식으로 문제를 쪼개어 간단한부분부터 해결하는 연습을 많이해야겠다.
이 글을 봐도 도통 무슨소리인지 모르겠을 수 있다.
핵심은 문제를 쪼개고 문제를 구체화하여 생각해야 한다는것이
이 글의 핵심이라고 할 수 있겠다.