[TIL] #23. JSON 과 TreeUI 에서 재귀 활용해보기

2022.6.24. (금)

1. 오늘의 소감

• 사각형의내부의사각형의내부의사각형의내부의사각형 의내부의사각형…. - 이상, 건축무한육면각체 연작시 中 백화점
  → 이 사각형들 안에 있는 김철수씨를 찾을 때 무엇을 쓰면 좋을까? 바로 재귀다!
• 오늘 과제를 풀고 나니까, 재귀 함수를 어떤 경우에 쓰면 좋을 지 알겠다! 특히 그냥 코딩 테스트 문제에만 쓸 줄 알았던 재귀의 무궁무진한 활용법을 알게 되어서 좋았다.
• 결론부터 말하자면 재귀는 ‘트리 구조'에서 진가를 발휘한다. 트리구조는 부모가 하나이고 자식이 여러개인 구조이다. 대표적인 트리구조로 폴더 구조가 있다. 하나의 폴더 안에 여러 개의 파일과 폴더가 있고, 그 폴더 안에 또 여러 개의 파일과 폴더가 있다. 이 파일과 폴더들은 자식은 여러 개 가질 수 있지만 부모는 오직 하나다. 훌륭한 트리 구조의 예시라고 볼 수 있다. 그 외에 프론트엔드 개발을 하면서 자주 만나게 될 트리 구조는 ‘다차원 배열’, ‘중첩 객체', DOM tree, Tree UI, JSON.stringify() 등이 있다.
• 왜 트리 구조에서 재귀를 활용하면 좋은가? 그건 부모가 자식을 처리할 때 사용한 로직을 (자식을 가진) 자식을 처리할 때 똑같이 활용할 수 있기 때문이다. 즉 트리구조에서 재귀함수는 주로 두 가지 경우로 분기가 된다.
  • (자식이 없는) 자식 처리 : 바로 처리한다.
  • (자식이 있는) 자식 처리 : 재귀함수 호출(= 부모의 로직 그대로 자식 처리하기!)
  ⇒ 이렇게 이미 만들어 둔 로직을 자식에게 재귀로 재활용 해서 간단하게 문제를 해결할 수 있다!
• 오늘치 데일리코딩은 많이 어려웠다. 피보나치 수열을 시간복잡도를 고려해서 O(2^n) ⇒ O(n) 으로 최적화 시켜야 되었는데, 해결방법이 쉽게 떠오르지 않아 1시간을 끙끙 거렸던것 같다. 이번 문제를 풀어보면서 메모이제이션(memoization) 이라는 개념을 알 수 있었다. 메모이제이션은 이미 해결한 문제의 답을 기록해둬서, 다시 해결하지 않는 기법이다. 이 기법을 사용하면 중복 계산을 방지해서 시간복잡도를 크게 줄일 수 있다.

2. 학습한 키워드

• JSON, JSON.stringify(), JSON.parse(), 직렬화 serialize, 역직렬화 deserialize, 메모이제이션(memoization)

3. 키워드를 바탕으로 학습 내용 설명해보기

• JSON 은 데이터 교환을 위해 만들어진 포맷으로, 쉽게 생각하면 객체 같이 복잡한 형태도 전송되기 쉽도록 ‘한줄의 문자열로 변환시킨’ 포맷이다.
• 데이터 전송이 가능하려면 다음 조건을 충족해야한다.
  • 수신자와 발신자가 같은 프로그램을 사용한다.
  • 또는, 문자열처럼 범용적으로 읽을 수 있는 형태여야 한다.
• 객체를 그냥 문자열로 만들고 싶다고 String(obj) 나 obj.toString() 을 하면 [object Object] 가 나온다. 제대로 객체 데이터를 문자열로 만들고 싶다면 JSON.stringify(obj) 를 사용하면 된다. (obj 가 꼭 객체가 아니여도 된다. 자주 쓰는 형태가 객에일 뿐. 숫자나 boolean 등등이 들어가도 JSON 변환 규칙에 맞게 변환된다.)
• JSON.stringify() : 객체 → JSON 문자열, 이 과정을 직렬화(serialize) 라고 한다. 이 과정을 거치면 타입이 string이 된다
• JSON.parse() : JSON 문자열 → 객체, 이 과정을 역직렬화(deserialize) 라고 한다.
• JSON에는 기본 규칙이 있다. 이는 기존 자바스크립트 객체의 규칙과 약간의 차이가 있다.
  • 키는 반드시 쌍따옴표로 감싸져야 한다.
  • 문자열 값도 반드시 쌍따옴표로 감싸져야한다.
  • 키와 값 사이, 키-값 쌍 사이 공백을 넣을 수 없다. JSON 포맷은 각 데이터 사이에 공백같은 낭비 없이 조밀한 형태의 문자열이다.
• 메모이제이션(memoization)은 이미 해결한 문제의 답을 기록해둬서 다시 해결하지 않는 기법이다. 중복 계산을 방지해서 시간복잡도를 줄일 수 있는 스킬! 대표적인 예로 코플릿 문제에 나왔던 피보나치 수열 계산이 있다.
• 피보나치 수열을 원래 풀이대로 풀면 다음과 같다.

function fibonacci(n) {
    if(n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

⇒ 이 경우 시간복잡도는 O(2^n) 이 된다.

• 하지만 메모이제이션을 활용해서 푼다면 시간복잡도를 O(n) 으로 확 줄일 수 있다.

function fibonacci(n) {
    const memo = [0, 1];

    const aux = (n) => {
        //base case
        if(memo[n] !== undefined) return memo[n];

        //recursive case
        memo[n] = aux(n-1) + aux(n-2);
        return memo[n];  //리턴 필수
    }

    return aux(n);
}

⇒ 이 경우 시간복잡도는 O(n) 이 된다!