Unit1 - [자료구조/알고리즘] 재귀 - 2

강성일·2023년 6월 12일
TIL코드스테이츠
0

[코드스테이츠] SEB FE 45 Students

목록 보기
48/82
post-thumbnail

✅ TIL

오늘은 실제로 재귀가 사용하는 코드를 직접 구현하고 Tree UI까지 구현해 볼 에정이다.

재귀의 실사용 예시도 알아보고 재귀로 문제를 해결하는 방법을 좀 더 익혀보는 시간이다.

오늘 과제를 하면서 느낀점이 있다면, 재귀 함수를 직접 재연하다보니 반복문의 case를 자주 만나게 되었다.
따라서 자연스럽게 과제를 진행하면서 재귀가 반복의 수행을 한다는 것이 자명했다.



JSON.stringify

JSON의 탄생 배경

JSON은 JavaScript Object Notation의 줄임말로, 데이터 교환을 위해 만들어진 객체 형태의 포맷이다.
그리고 JSON 포맷은 JavaScript를 포함한 많은 언어에서 범용적으로 사용하는 유명한 포맷이다.

네트워크를 통해, 어떤 객체 내용을 다른 프로그램에 전송한다고 가정하겠다.

이 객체 내용을 일종의 메신저 혹은 채팅 프로그램에서 쓰는 하나의 메시지라 한다면, 다음 객체를 어떻게 전송할 수 있을까?

const message = {
  sender: "김코딩",
  receiver: "박해커",
  message: "해커야 오늘 저녁 같이 먹을래?",
  createdAt: "2021-01-12 10:10:10"
}

메시지 객체가 전송할 수 있게 하려면, 메시지를 보내는 발신자와 메시지를 받는 수신자가
같은 프로그램을 사용하거나, 문자열처럼 범용적으로 읽을 수 있는 형태여야 한다.

객체는 타입 변환을 이용해 String으로 변환할 경우 객체 내용을 포함하지 않는다.

JavaScript에서 객체를 문자열로 변환하기 위해 메서드(message.toString())나
형 변환(String(message))을 시도하면, [object Object]라는 결과를 리턴한다.

이 문제를 해결하는 방법은 객체를 JSON의 형태로 변환하거나 JSON을 객체의 형태로 변환하는 방법이다.

이를 위한 메서드는 다음과 같다.

  • JSON.stringify : 객체를 JSON으로 변환합니다.
  • JSON.parse : JSON을 객체로 변환합니다.

let transferableMessage = JSON.stringify(message)
// stringify하는 이 과정을 직렬화(serialize)한다고 한다.

console.log(transferableMessage) 
// `{"sender":"김코딩","receiver":"박해커","message":"해커야 오늘 저녁 같이 먹을래?","createdAt":"2021-01-12 10:10:10"}`

console.log(typeof(transferableMessage))
// `string`

JSON으로 변환된 객체의 타입은 문자열이다. 발신자는 객체를 직렬화한 문자열을 누군가에게 객체의 내용을 보낼 수 있다.
그렇다면 수신자는 이 문자열 메시지를 어떻게 다시 객체의 형태로 만들 수 있을까?

JSON.stringify와 정반대의 작업을 수행하는 메서드 JSON.parse를 사용할 수 있다.

let packet = `{"sender":"김코딩","receiver":"박해커","message":"해커야 오늘 저녁 같이 먹을래?","createdAt":"2021-01-12 10:10:10"}`
let obj = JSON.parse(packet)
// JSON.parse를 적용하는 이 과정을 역직렬화(deserialize)한다고 한다.

console.log(obj)
/*
 * {
 * sender: "김코딩",
 * receiver: "박해커",
 * message: "해커야 오늘 저녁 같이 먹을래?",
 * createdAt: "2021-01-12 10:10:10"
 * }
 */

 console.log(typeof(obj))
 // `object`


JSON의 기본 규칙



💬 Sprint Review 


// 💬 주어진 코드
/*
 * 1. Browser에 존재하는 JSON.stringfy 함수를 직접 구현해 봅니다.
 * JSON.stringfy 함수는 input 값을 JSON 형식으로 변환합니다.
 * 단, undefined와 function은 JSON으로 생략되거나 null로 변환됩니다.
 *
 * 2. stringfyJSON은 아래와 같이 작동합니다.
 * - Boolean이 input으로 주어졌을 경우
 * stringifyJSON(true);                // 'true'
 * - String이 input으로 주어졌을 경우
 * stringifyJSON('foo');               // '"foo"'
 * - Array가 input으로 주어졌을 경우
 * stringifyJSON([1, 'false', false]); // '[1,"false",false]'
 * - Object가 input으로 주어졌을 경우
 * stringifyJSON({ x: 5 });            // '{"x":5}'
 * - undefined, function이 주어졌을 경우
 * stringifyJSON(undefined)            // undefined
 * stringifyJSON(function(){})         // undefined
 * stringifyJSON({ x: undefined, y: function(){} })   // '{}'
 *
 * 3. spec/stringifyJSONSpec.js의 stringifiableObjects 배열을 참고해서 테스트에서 어떤 input 값들이
 * 주어지고, 어떻게 stringify해 주어야 할지 생각해 보세요.
 *
 * 4. 그냥 테스트 통과를 하고 싶으시다면, 다음과 같이 구현하면 될 거예요.
 *  const stringifyJSON = JSON.stringify;
 *
 * 하지만 이 과제의 목적은 재귀를 공부하는 것이니, 처음부터 구현해봐야겠지요?:
 */
function stringifyJSON(obj) {
  // your code goes here
};

// 다음 코드는 결과 제출을 위한 코드입니다. 신경 쓰지 않아도 좋습니다.
if (typeof window === "undefined") {
  module.exports = stringifyJSON;
}

// ✅ 구현한 코드
 
function stringifyJSON(obj) {
  if (typeof obj === "number") return String(obj);
  else if (obj === null) return "null";
  else if (typeof obj === "boolean") return String(obj);
  else if (typeof obj === "string") return `"${obj}"`;
  else if (Array.isArray(obj)) return `[${obj.map(stringifyJSON).join(",")}]`;
  else if (typeof obj === "object") {
    for (let key in obj) {
      if (typeof obj[key] === "function" || undefined) {
        return "{}";
      }
    }
    return `{${Object.keys(obj)
      .map((key) => `"${key}":${stringifyJSON(obj[key])}`)
      .join(",")}}`;
  }
}
if (typeof window === "undefined") {
  module.exports = stringifyJSON;
}


Tree UI 

// 💬 주어진 코드 (fix_me.js)

// 여러분들이 tree-UI를 만드셔야 할 메뉴판입니다.
// menu는 수정하지 않고, createTreeView 함수만 수정하세요.

const menu = [
  {
    type: 'group',
    name: '음료',
    children: [
      {
        type: 'group',
        name: '콜드 브루',
        children: [
          { type: 'item', name: '나이트로 콜드 브루' },
          { type: 'item', name: '돌체 콜드 브루' },
          { type: 'item', name: '제주 비자림 콜드 브루' },
          { type: 'item', name: '콜드 브루' },
        ],
      },
      {
        type: 'group',
        name: '프라푸치노',
        children: [
          { type: 'item', name: '애플 쿠키 크림 프라푸치노' },
          { type: 'item', name: '더블 에스프레소 칩 프라푸치노' },
          { type: 'item', name: '모카 프라푸치노' },
          { type: 'item', name: '피스타치오 크림 프라푸치노' },
        ],
      },
      {
        type: 'group',
        name: '블렌디드',
        children: [
          { type: 'item', name: '망고 바나나 블렌디드' },
          { type: 'item', name: '딸기 요거트 블렌디드' },
          { type: 'item', name: '자몽 셔벗 블렌디드' },
          { type: 'item', name: '피치 & 레몬 블렌디드' },
        ],
      },
      {
        type: 'group',
        name: '티',
        children: [
          { type: 'item', name: '라임 패션 티' },
          { type: 'item', name: '민트 블렌드 티' },
          { type: 'item', name: '아이스 유스베리 티' },
          { type: 'item', name: '아이스 캐모마일 블렌드 티' },
        ],
      },
      {
        type: 'group',
        name: '주스',
        children: [
          { type: 'item', name: '한방에 쭉 감당' },
          { type: 'item', name: '파이팅 청귤' },
          { type: 'item', name: '딸기주스' },
          { type: 'item', name: '도와주 흑흑' },
        ],
      },
    ],
  },
  {
    type: 'group',
    name: '음식',
    children: [
      {
        type: 'group',
        name: '빵',
        children: [
          { type: 'item', name: '트러플 미니 스콘' },
          { type: 'item', name: '보늬밤 몽블랑 데니쉬' },
          { type: 'item', name: '고소한 치즈 베이글' },
          { type: 'item', name: '미니 클래식 스콘' },
        ],
      },
      {
        type: 'group',
        name: '케이크',
        children: [
          { type: 'item', name: '밀당 에그 타르트' },
          { type: 'item', name: '마스카포네 티라미수 케이크' },
          { type: 'item', name: '블루베리 쿠키 치즈 케이크' },
          { type: 'item', name: '부드러운 생크림 카스텔라' },
        ],
      },
      {
        type: 'group',
        name: '샌드위치',
        children: [
          { type: 'item', name: '애플 까망베르 샌드위치' },
          { type: 'item', name: '트리플 머쉬룸 치즈 샌드위치' },
          { type: 'item', name: '로스트 치킨 샐러드 밀 박스' },
          { type: 'item', name: 'B.E.L.T 샌드위치' },
        ],
      },
      {
        type: 'group',
        name: '과일',
        children: [
          { type: 'item', name: '하루 한 컵 RED' },
          { type: 'item', name: '한라봉 가득 핸디 젤리' },
        ],
      },
      {
        type: 'group',
        name: '스낵',
        children: [
          { type: 'item', name: '리저브 초콜릿 세트' },
          { type: 'item', name: '로스티드 아몬드 앤 초콜릿' },
          { type: 'item', name: '마카롱' },
          { type: 'item', name: '자일리톨 캔디 크리스탈 민트' },
        ],
      },
      {
        type: 'group',
        name: '아이스크림',
        children: [
          { type: 'item', name: '자바 칩 유기농 바닐라 아이스크림' },
          { type: 'item', name: '넛츠 초콜릿 아포가토' },
          { type: 'item', name: '바닐라 아포가토' },
        ],
      },
    ],
  },
  {
    type: 'group',
    name: '굿즈',
    children: [
      {
        type: 'group',
        name: '머그',
        children: [
          { type: 'item', name: '우리 한글 블랙 머그 473ml' },
          { type: 'item', name: '서울 투어 머그 355ml' },
          { type: 'item', name: '스타벅스 1호점 머그 400ml' },
          { type: 'item', name: '서울 제주 데이머그 세트' },
        ],
      },
      {
        type: 'group',
        name: '텀블러',
        children: [
          { type: 'item', name: 'SS 부산 투어 텀블러 355ml' },
          { type: 'item', name: 'SS 블랙 헤리티지 오드리 텀블러 355ml' },
          { type: 'item', name: 'SS 에치드 실버 텀블러 473ml' },
        ],
      },
      {
        type: 'group',
        name: '악세사리',
        children: [
          { type: 'item', name: '리저브 오렌지 카드 홀더' },
          { type: 'item', name: '스타벅스 1호점 에코백' },
          { type: 'item', name: '스타벅스 1호점 랩탑 파우치' },
        ],
      },
    ],
  },
  {
    type: 'group',
    name: '카드',
    children: [
      { type: 'item', name: '10000원권' },
      { type: 'item', name: '30000원권' },
      { type: 'item', name: '50000원권' },
      { type: 'item', name: '100000원권' },
    ],
  },
];

// TODO: createTreeView 함수를 재귀(자기 자신을 계속 부르게 함)호출하여 테스트케이스를 통과하세요.
// GOAL: 최종 결과가 resut.html와 같은 모습으로 나와야 합니다.

const root = document.getElementById('root');
function createTreeView(menu, currentNode) {
  // TODO: createTreeView 함수를 작성하세요.
}

createTreeView(menu, root);
// 💬 주어진 코드 (result.html)

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
    <link rel="stylesheet" href="index.css" />
  </head>

  <body>
    <ul id="root">
      <li>
        <input type="checkbox" checked />
        <span>음료</span>
        <ul>
          <li>
            <input type="checkbox" />
            <span>콜드브루</span>
            <ul>
              <li>나이트로 콜드 브루</li>
              <li>돌체 콜드 브루</li>
              <li>제주 비자림 콜드 브루</li>
              <li>콜드 브루</li>
            </ul>
          </li>
          <li>
            <input type="checkbox" />
            <span>프라푸치노</span>
            <ul>
              <li>애플 쿠키 크림 프라푸치노</li>
              <li>더블 에스프레소 칩 프라푸치노</li>
              <li>모카 프라푸치노</li>
              <li>피스타치오 크림 프라푸치노</li>
            </ul>
          </li>
          <li>
            <input type="checkbox" />
            <span>블렌디드</span>
            <ul>
              <li>망고 바나나 블렌디드</li>
              <li>딸기 요거트 블렌디드</li>
              <li>자몽 셔벗 블렌디드</li>
              <li>피치 & 레몬 블렌디드</li>
            </ul>
          </li>
          <li>
            <input type="checkbox" />
            <span>티</span>
            <ul>
              <li>라임 패션 티</li>
              <li>민트 블렌드 티</li>
              <li>아이스 유스베리 티</li>
              <li>아이스 캐모마일 블렌드 티</li>
            </ul>
          </li>
          <li>
            <input type="checkbox" />
            <span>주스</span>
            <ul>
              <li>한방에 쭉 감당</li>
              <li>파이팅 청귤</li>
              <li>딸기주스</li>
              <li>도와주 흑흑</li>
            </ul>
          </li>
        </ul>
      </li>
      <li>
        <input type="checkbox" />
        <span>음식</span>
        <ul>
          <li>
            <input type="checkbox" />
            <span>빵</span>
            <ul>
              <li>트러플 미니 스콘</li>
              <li>보늬밤 몽블랑 데니쉬</li>
              <li>고소한 치즈 베이글</li>
              <li>미니 클래식 스콘</li>
            </ul>
          </li>
          <li>
            <input type="checkbox" />
            <span>케이크</span>
            <ul>
              <li>밀당 에그 타르트</li>
              <li>마스카포네 티라미수 케이크</li>
              <li>블루베리 쿠키 치즈 케이크</li>
              <li>부드러운 생크림 카스텔라</li>
            </ul>
          </li>
          <li>
            <input type="checkbox" />
            <span>샌드위치</span>
            <ul>
              <li>애플 까망베르 샌드위치</li>
              <li>트리플 머쉬룸 치즈 샌드위치</li>
              <li>로스트 치킨 샐러드 밀 박스</li>
              <li>B.E.L.T 샌드위치</li>
            </ul>
          </li>
          <li>
            <input type="checkbox" />
            <span>과일</span>
            <ul>
              <li>하루 한 컵 RED</li>
              <li>한라봉 가득 핸디 젤리</li>
            </ul>
          </li>
          <li>
            <input type="checkbox" />
            <span>스낵</span>
            <ul>
              <li>리저브 초콜릿 세트</li>
              <li>로스티드 아몬드 앤 초콜릿</li>
              <li>마카롱</li>
              <li>자일리톨 캔디 크리스탈 민트</li>
            </ul>
          </li>
          <li>
            <input type="checkbox" />
            <span>아이스크림</span>
            <ul>
              <li>자바 칩 유기농 바닐라 아이스크림</li>
              <li>넛츠 초콜릿 아포가토</li>
              <li>바닐라 아포가토</li>
            </ul>
          </li>
        </ul>
      </li>
      <li>
        <input type="checkbox" />
        <span>굿즈</span>
        <ul>
          <li>
            <input type="checkbox" />
            <span>머그</span>
            <ul>
              <li>우리 한글 블랙 머그 473ml</li>
              <li>서울 투어 머그 355ml</li>
              <li>스타벅스 1호점 머그 400ml</li>
              <li>서울 제주 데이머그 세트</li>
            </ul>
          </li>
          <li>
            <input type="checkbox" />
            <span>텀블러</span>
            <ul>
              <li>SS 부산 투어 텀블러 355ml</li>
              <li>SS 블랙 헤리티지 오드리 텀블러 355ml</li>
              <li>SS 에치드 실버 텀블러 473ml</li>
            </ul>
          </li>
          <li>
            <input type="checkbox" />
            <span>악세사리</span>
            <ul>
              <li>리저브 오렌지 카드 홀더</li>
              <li>스타벅스 1호점 에코백</li>
              <li>스타벅스 1호점 랩탑 파우치</li>
            </ul>
          </li>
        </ul>
      </li>
      <li>
        <input type="checkbox" />
        <span>카드</span>
        <ul>
          <li>10000원권</li>
          <li>30000원권</li>
          <li>50000원권</li>
          <li>100000원권</li>
        </ul>
      </li>
    </ul>
  </body>
</html>


💬 Sprint Review


result.html 구조를 보고, tree 구조의 UI를 구현하면 되는 과제이다.

처음에는 이게 재귀와 무슨 관련이 있지..? 라는 생각이 정말 많이 들었는데
과제가 끝나고 나서 재귀의 대한 공포심과 필요성의 대한 의문이 모두 해결되었다.

정말 실상에서 반복을 구현해야 하는 상황이라면, 유용하게 쓸 수 있을 것 같다는 생각이 많이 들었다.

⚙️ Code 

// ✅ 구현한 코드
...
const root = document.getElementById("root");

function createTreeView(menu, currentNode) {
  for (let el of menu) {
    if (el.type === "group") {
      // 자식 노드가 있는 데이터
      const li = document.createElement("li");
      currentNode.append(li);

      const input = document.createElement("input");
      input.type = "checkbox";

      const span = document.createElement("span");
      span.textContent = el.name;

      const ul = document.createElement("ul");

      li.append(input, span, ul);

      createTreeView(el.children, ul);
    } else if (el.type === "item") {
      // 자식 노드가 없는 데이터
      const li = document.createElement("li");
      li.textContent = el.name;
      currentNode.append(li); // 함수 실행을 종료
    }
  }
}

createTreeView(menu, root);


⚙️ Build


💬 Review

처음부터 createTreeView 를 재귀 함수로 어떻게 사용해야 하는지 감이 오지 않아서 그냥 뒀다.

먼저 다른 가장 큰 틀을 구현하기 위해서 구조를 살폈다.

가장 먼저 보이는 것은 음료, 음식, 굿즈, 카드를 리스트 4개를 시작으로, 안쪽으로 퍼져나간다는 것이었다.
리스트 안쪽 구조는 li ➡️ input ➡️ span ➡️ ul ➡️ li 와 같은 반복의 형태였다.

하지만, 그 전에 더 먼저 해야할 것이 있었다.
테스트 조건 중, 자식 노드가 있는 데이터와 없는 데이터가 무엇인지 알아야 했다.

그것은 바로 한 메뉴에서 li ➡️ input ➡️ span ➡️ ul ➡️ li 식으로 타고 들어가다 보면 최종적인 메뉴가 결정이 되는
이것이 바로 더 이상 쪼개질 것이 없는 base case 와 그 쪼개지는 과정이 바로 recursive case 이었다.

쉽게 말하면 음료 ➡️ 콜드 브루 ➡️ 나이트로 콜드 브루 로 쪼개지는 동안
음료와 콜드 브루는 type: 'group' 이지만, 나이트로 콜드 브루는 type: 'item'이다.

음료와 콜드 브루까지는 type: 'group' 으로 골라지는 과정 중에서
음료 ➡️ 프라푸치노 처럼 아예 다른 분야로 선택이 가능했지만, 콜드 브루라는 메뉴를 고르면,
그 안에 또 다른 부류의 선택지인 type: 'group'이 아닌, 같은 부류의 선택지인 type: 'item'밖에 없다.

즉, type: 'item'에 닿으면, 최종인 더 이상 쪼개질 수 없는 상황이 된다.

따라서 코드를 이렇게 나눌 수 있다.

Recursive Case

// 자식 노드가 있는 데이터

if (el.type === "group") {
  const li = document.createElement("li");
  currentNode.append(li);

  const input = document.createElement("input");
  input.type = "checkbox";

  const span = document.createElement("span");
  span.textContent = el.name;

  const ul = document.createElement("ul");

  li.append(input, span, ul);

  createTreeView(el.children, ul); // 재귀 호출
}

Base Case

// 자식 노드가 없는 데이터

else if (el.type === "item") {
  const li = document.createElement("li");
  li.textContent = el.name;
  currentNode.append(li); // 함수 실행을 종료
}

여기까지 구조를 파악하고 나서야, 재귀 함수가 왜 필요한지, 무슨 역할을 하는지 알게 되었다.

createTreeView(el.children, ul) 을 이용하여, 더 이상 쪼개지지 않는 type: 'item'까지
Recursive Case 구역 안을 계속 반복하며 돌고 li, input, span, ul 을 계속 만들어내는 것이다.

profile
강성일
아이디어가 넘치는 프론트엔드를 꿈꿉니다 🔥
이전 포스트

🌟 [SEB FE] Section 2_회고

다음 포스트

Unit2 - [사용자 친화 웹] UI/UX

0개의 댓글