코드스테이츠_S3U1_1W_목,금

윤뿔소·2022년 10월 20일
0

CodeStates

목록 보기
28/47
post-thumbnail

알고리즘의 필수 재귀에 대해서 알아보자!

재귀

원래의 자리로 되돌아가거나 되돌아옴.
알고리즘의 재귀는 '자기 자신의 함수'를 '자기'가 호출하는 방식임
액자식 구성 알제? 그런 느낌의 반복이 되는 함수 호출임

재귀 사용법

재귀는 2가지가 필요하다.이 2가지를 충족해야 원하는 결과물을 얻을 수 있다.

  1. 자기 자신을 자신이 호출(반복)
  2. 반복이 끝날 수 있는 종료 코드

재귀를 사용하는 최적의 상태도 있다. 반복문의 일종이라고 보면 된다.

  1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
  2. 중첩된 반복문이 많거나(3개 이상) 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우(2차원 이상 참조 데이터들)
  3. 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

예시

배열이 주어지면 전체 합을 구하는 arrSum()함수를 만든다고 가정해보자. 물론 reduce나 for, while로도 구할 수 있지만 재귀를 써보자

function arrSum (arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if (arr.length === 0) {
    return 0
  }
  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  //   --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr.shift() + arrSum(arr)
}

위 코드는 맨 앞의 배열 요소를 제거하고 그 반환값을 더하고, arrSum(arr)을 또 더해줘 반복이 되게 만들었다. 또 추가로 종료조건을 써줘 배열이 0이 되면 끝나게 만들었다.즉 과정을 보면 먼저 쪼개지고, 위 GIF처럼 합쳐지는 구조로 된다!

재귀적으로 사고하기

  1. 재귀 함수의 입력값과 출력값 정의하기

    • 함수 입력, 출력을 정하여 풀려는 문제를 더 쉽게 정의하기
    • arrSum: [number] => number ← 입출력값 정의
  2. 문제를 쪼개고 경우의 수를 나누기

    • 위에서 했던 것처럼 쪼개야함
      • 어떤 것이 입력되는지
      • 어떻게 순서를 이어나가 문제를 해결할지
    • arrSum([ ]) ← 입력값이 빈 배열인 경우
    • arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우
  3. 단순한 문제 해결하기 (base case)

    • 재귀에서 단순한 문제는 종료 조건을 세우는 것이다. 그리고 이 단순한 것을 먼저 해결하고 재귀 공식을 써주는 것이 좋다!
    • arrSum: [number] => number
    • arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우 : 해결!
    • arrSum([요소1, 요소2, ... , 요소n])
  4. 복잡한 문제 해결하기 (recursive case)

    • 남아있는 복잡한 거 처리
    • arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) ← 그렇지 않은 경우 : 해결!
    • 배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, 함수 arrSum 을 재귀적으로 구현할 수 있다.
  5. 코드 구현

    • 예시

    • 기본적인 코드 템플릿

      function recursive(input1, input2, ...) {
      // base case : 문제를 더 이상 쪼갤 수 없는 경우
      if (문제를 더 이상 쪼갤 수 없을 경우) {
       return 단순한 문제의 해답;
      }
      
      // recursive case : 그렇지 않은 경우
      return 더 작은 문제로 새롭게 정의된 문제
      }

예제

문제 : 자연수를 입력받고, 입력받은 수부터 1까지의 자연수를 모두 곱한 값을 리턴하는 재귀 함수 fac 을 작성하세요.

  1. 입력값: 자연수 하나, 출력값 : 자연수부터 1까지 곱해진

  2. fac(자연수요소)

  3. base case: 1은 곱해도 안변하기에 종료 조건이 요소 === 1이면 종료하게끔

  4. fac(n) = n * fac(n-1) 이런 식으로 처리

  5. function fac(n) {
      // base case
      if (arr.length === 1) {
        return 1;
      }
    
      // recursive case
      return n * fac(n - 1);
    }

해설: n이 4라면 fac(4) = 4 * fac(3)을 리턴해 fac(3)을 호출하고 n이 3이니까 fac(3) = 3 *fac(2)를 호출, 이런 식으로 반복해 결국 1일때 fac(1)이 끝난다. 다 놓고 보자면 4 3 2 * 1이 되어 팩토리얼이 완성된다!

코플릿 문제

알고리즘 태그에 써놨다 꼭 보자!

JSON

재귀 중 갑자기 JSON?! 통신 중 JSON.stringfy 함수가 재귀를 이용하기 때문에 보면서 JSON도 다시 보자
JSON의 기본적인 개념을 짚고 넘어가보자

  • JavaScript Object Notation, 데이터 교환을 위해 만들어진 객체 형태의 포맷
  • 한마디로 JS에서 데이터를 주고 받을 때 약속된 문자 형식, 문자열임

http인 프로토콜같이 데이터 전송에 필요한 조건을 충족하기 위한 범용적인 형태가 필요했기에 생겨났다. XML 등의 사촌.
기본적으로 JSON 형태의 데이터라 JS에선 문자열처럼 쓸 순 없다. String(JSON)을 한다면 [object Object]라는 결과를 리턴한다.

사용법

그렇다면 JS에선 어떻게 써야할까? fetch같이 JS에서 작성되고 JSON으로 데이터를 전송해야할 일이 있을 때 어떻게 변환할까?
바로 JSON.stringify(obj)(객체를 JSON으로 변환, 직렬화), JSON.parse(JSON, 역직렬화)(JSON을 객체로 변환)을 사용해야한다.

// stringify, 직렬화(serialize)
let transferableMessage = JSON.stringify(message)
console.log(transferableMessage) 
// `{"sender":"김코딩","receiver":"박해커","message":"해커야 오늘 저녁 같이 먹을래?","createdAt":"2021-01-12 10:10:10"}`
console.log(typeof(transferableMessage))
// `string`

// parse, 역직렬화(deserialize)
let obj = JSON.parse(transferableMessage)
console.log(obj)
/*
 * {
 * sender: "김코딩",
 * receiver: "박해커",
 * message: "해커야 오늘 저녁 같이 먹을래?",
 * createdAt: "2021-01-12 10:10:10"
 * }
 */
 console.log(typeof(obj))
 // `object`

JSON 주의점

JSON은 객체 포맷을 가져왔지만 말그대로 객체는 아니다. 다음과 같은 규칙을 지켜야 JSON이라 할 수 있다!

과제

Koans처럼 JSON.stringfy 함수의 구조를 만들어보는 시간이다.

function stringifyJSON(obj) {
  if (typeof obj === "number" || obj === null || typeof obj === "boolean") return `${obj}`;
  // JSON은 문자열을 무조건 "" 붙이기 때문
  if (typeof obj === "string") return `"${obj}"`;
  if (Array.isArray(obj)) {
    let result = "";
    for (let i = 0; i < obj.length; i++) {
      // 재귀로 배열 각 요소를 변환, 대괄호가 얼마나 중첩되있는지 모르니
      result += `${stringifyJSON(obj[i])},`;
    }
    result = result.slice(0, -1);
    return `[${result}]`;
  }
  if (typeof obj === "object") {
    let result = "";
    for (let j in obj) {
      // stringfy는 기본적으로 und나 함수는 포함하지 않고 변환됨
      if (typeof obj[j] === "undefined" || typeof obj[j] === "function") {
        continue;
      }
      // JSON 키, 값 규칙 지키기
      result += `${stringifyJSON(j)}:${stringifyJSON(obj[j])},`;
    }
    result = result.slice(0, -1);
    return `{${result}}`;
  }
}

핵심: 재귀로 얼마나 중첩되는지 모르는 참조 데이터들에게 쓰면 좋다!@@

Tree UI

네이버 블로그에 목차를 누르면 아래 쭉 펼치듯이 나오는 UI가 있다. 하나의 항목에 여러 항목이 겹쳐있는 구조를 Tree 구조라고 하고, 우리가 재귀와 DOM을 이용하여 구현해본다.

풀이

// TODO: createTreeView 함수를 재귀(자기 자신을 계속 부르게 함)호출하여 테스트케이스를 통과하세요.

// 데이터 구조)
// menu[0]은 음료 메뉴판. menu[0].children = [콜드브루, 프라푸치노, 블렌디드, 티, 주스] ;
// menu[1]은 음식. menu[1].children = [빵, 케이크, 샌드위치, 과일, 스낵, 아이스크림] ;
// menu[2]는 굿즈. menu[2].children = [머그, 텀블러, 악세사리]
// menu[3]은 카드. menu[3].children  = [10000원권, 30000원권, 50000원권, 100000원권]

// 요소 구성: menu[i].children = [ {type: "item", name: 음식이름 }, {type: "item", name: 음식이름 } ]
// children이 없으면 li만 렌더링, 있으면 구성요소(input, span 등)렌더링 되고 재귀로 children 렌더링
const root = document.getElementById("root");
function createTreeView(menu, currentNode) {
  for (let i = 0; i < menu.length; i++) {
    let li = document.createElement("li");
    // base
    if (!menu[i].children) {
      // li 안 name 붙여주기
      li.textContent = menu[i].name;
      currentNode.append(li);
    }
    // recursive, 렌더링 후 재귀 호출
    else {
      let input = document.createElement("input");
      input.type = "checkBox";
      let span = document.createElement("span");
      span.textContent = menu[i].name;
      let ul = document.createElement("ul");
      li.append(input, span, ul);
      currentNode.append(li);
      // ul.append(createTreeView(menu[i].children, ul));하면 안됨, 재귀 자체가 넣어줌
      createTreeView(menu[i].children, ul);
    }
  }
}

핵심: 저렇게 트리구조같이 같은 구조가 반복되고, 구조가 얼마나 중첩되있는지 모르기에 재귀가 최고야!

🦏

profile
코뿔소처럼 저돌적으로

0개의 댓글