Level 4-3. 알고리즘과 복잡도

soheey·2021년 5월 25일
PRE
0

재귀의 이해 - 다르게 생각하기

문제. 자연수의 리스트를 입력으로 받아 리스트의 합을 리턴하는 함수 `arrSum을` 작성하세요.

  • (자연수) 리스트의 합을 구하는 알고리즘

    1. 보조 변수 sum을 0으로 초기화한다.
    2. 순차적으로 리스트의 구성요소에 접근하면서 sum에 더한다.

  • 코드

function arrSum(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

이제 이 문제를 다른 각도에서 생각해 보겠습니다.
자연수의 리스트 [10, 3, 6, 2]의 합을 구한다고 가정합시다.

  1. [10, 3, 6, 2]의 합을 구하는 건 신경쓰지 않고, 대신에 [3, 6, 2]의 합을 구하는 방법을 생각해 봅니다.

    • [10, 3, 6, 2]보다는 [3, 6, 2]가 더 작으니 왠지 더 쉽게 풀릴 것 같기도 합니다. [3, 6, 2]의 합을 구하는 방법을 알아낸다면, 이 값에 10을 더하면 원래의 목적인[10, 3, 6, 2]의 합을 구할 수 있습니다.

  2. [3, 6, 2]의 합을 구하는 것도 조금 버겁게 느껴져서, 대신에 [6, 2]의 합을 구하는 방법을 생각해 봅니다.

    • 똑같은 이유로 [3, 6, 2]보다는 [6, 2]가 더 작아서 쉽게 풀 수 있을 것 같습니다. [6, 2]의 합을 구하는 방법을 알아낸다면, 이 값에 3을 더하면 [3, 6, 2]의 합을 구할 수 있습니다.
    • arrSum([3, 6, 2]) = 3 + arrSum([6, 2])

  3. 똑같은 이유로 [6, 2] 대신 [2]의 합을 구하는 방법을 생각해 봅니다. [2]의 합에 6을 더해 [6, 2]의 합을 구할 수 있습니다.

  4. [2]의 합을 구하는 건 매우 간단합니다. 2입니다.

이 과정을 아래의 간단한 코드로 표현할 수 있습니다.

arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]);
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]);
arrSum([6, 2]) = 6 + arrSum([2]);
arrSum([2]) = 2 + arrSum([]);
arrSum([]) = 0;

쪼개서 생각하는 방법

이처럼 어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀(recursion)라고 합니다. 재귀의 과정을 arrSum에 적용해보면 아래와 같습니다.

  1. 원래의 문제에서 출발하여 더 작은 경우를 생각합니다.
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]);
  1. 계속해서 문제가 더는 작아지지 않을 때까지 더 작은 경우를 생각합니다.
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]);
arrSum([6, 2]) = 6 + arrSum([2]);
arrSum([2]) = 2 + arrSum([]);
  1. 이렇게 문제 풀기를 미루다가, 문제가 간단해져서 바로 풀 수 있게 되는 순간에 미뤄왔던 문제들을 차근차근 해결합니다.
arrSum([]) = 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용한다.
arrSum([2]) = 2 + arrSum([]) = 2;
arrSum([6, 2]) = 6 + arrSum([2]) = 6 + 2 = 8;
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]) = 3 + 8 = 11;
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]) = 10 + 11 = 21;

arrSum을 아래와 같이 보다 엄밀하게(formally) 정의할 수 있습니다.

arrSum(arr)
1. arr이 빈 배열인 경우 = 0
2. 그 외의 경우 = arr[0] + arrSum(arr2)
   (arr2는 arr의 첫 요소를 제외한 나머지 배열)

만약에 arrSum 함수를 javascript 코드로 구현할 경우 (코플릿 과제 중 하나입니다), arrSum은 (인자가 빈 배열이 아닌 경우) 실행과정 중에 자기 자신을 호출하기도 합니다. 이러한 호출 방식을 재귀 호출이라고 합니다.

재귀는 언제 사용하는게 좋을까?

재귀는 특히 아래와 같은 상황에서 매우 적합합니다.

  1. 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나눠 질 수 있는 경우
  2. 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우
for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

사실 모든 재귀 함수는 재귀 호출 없이 while / for loop으로 표현이 가능합니다. 하지만 재귀를 사용 가능한 경우, 재귀를 사용한 코드가 대부분의 경우 더욱 간결하고, 일부의 경우에는 이해하기도 쉽습니다. 이 장이 끝나고 검색 과제로 주어지는 하노이의 탑과 조합(combination) 문제를 재귀와 그렇지 않은 경우로 비교해 보세요.

이 밖에도 재귀는 알고리즘 문제의 많은 부분을 차지합니다.

재귀적 사고 연습하기

Guide : 재귀적으로 사고하기

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

재귀 함수를 통해 어떤 문제를 풀고자 하는 지, 즉 우리의 목표를 정리하는 데 도움이 됩니다. 문제를 가장 추상적으로 또는 가장 단순하게 정리하는 것입니다. arrSum의 경우 number 타입을 요소로 갖는 배열을 입력으로 받아서 number를 리턴합니다. 이를 좀더 간편하게 아래와 같이 표기한다고 가정합시다.

• arrSum: [number] => number

2. 문제를 쪼개고 경우의 수를 나누기

주어진 문제를 어떻게 쪼갤 것인지 고민합니다. 어떤 기준을 정하고 그 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는 지 검토해봅니다. 일반적으로 입력값이 이 기준을 정하는 대상이 됩니다. 이 때 중요한 관점은 순서와 크기입니다. 주어진 입력값 또는 문제 상황을 크기를 기준으로 구분할 수 있거나, 순서를 명확하게 정할 수 있는지를 살펴보는 것이 도움이 됩니다. 그리고 구분된 문제들을 푸는 방식이 같다면, 문제를 제대로 구분한 것입니다.

  • arrSum의 경우 입력값인 배열을 크기에 따라 구분할 수 있습니다. 그리고 arrSum([1, 2, 3, 4])를 구하는 방법과 arrSum([2, 3, 4])을 구하는 방법은 동일할 것이므로 이 구분은 적절하다고 판단할 수 있습니다.
    이제 문제의 입력값에 따라 경우의 수를 나눕니다. 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눕니다.

  • arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있습니다. 각각의 경우는 다르게 처리되어야 합니다.

  • arrSum: [number] => number
    arrSum([ ])
    arrSum([e1, e2, ... , en])

3. 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음에는 쉬운 문제부터 해결합니다. 이를 재귀의 기초(base case)이라고 부릅니다. 재귀의 기초는 나중에 재귀 함수 구현 시 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성하게 됩니다.

  • arrSum를 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이 때 arrSum은 0입니다.
  • arrSum: [number] => number
    arrSum([ ]) = 0
    arrSum([e1, e2, ... , en])

4. 복잡한 문제 해결하기

남아있는 복잡한 경우를 해결합니다.

  • arrSum이 길이가 1 이상인 배열을 입력으로 받을 경우, 맨 앞의 요소를 따로 구하고(head), 나머지 요소(tail)를 새로운 입력값으로 갖는 문제를 해결하여 얻은 결과를 head에 더합니다.
  • arrSum: [number] => number
    arrSum([ ]) = 0
    arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])
  • 배열이 있을 때 head와 tail을 구분하는 방법만 안다면, arrSum을 해결할 수 있습니다.

5. 코드 구현하기

function arrSum(arr) {
// 재귀의 기초 (base case)
// 문제를 더 이상 쪼갤 수 없을 경우
if (arr의 길이가 0인 경우) {
    return 0;
}
// recursive Case
// 그렇지 않은 경우
// head: 배열의 첫 요소
// tail: 배열의 첫 요소만 제거된 배열
return head + arrSum(tail);
}

아래는 일반적인 재귀 함수의 템플릿입니다. 재귀 함수 연습에 활용하시기 바랍니다.

function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

더 쪼개지지 않는 문제 = 기초(base) = head = 탈출 조건

factorial

더 생각해 볼 주제 - Advanced

  • 재귀 함수와 메모리 사용량 간의 관계 (javascript recursion memory leak)
  • 꼬리 재귀 (tail recursion in js)
  • 하노이의 탑 재귀 (js tower of hanoi in recursion)
  • 조합 재귀함수 (js combination in recursion)
  • 최적화 기법(memoization)

JSON

1. JSON 탄생 배경

JSON(JavaScript Object Notation)은 데이터 교환을 위해 만들어진 포맷입니다. 여러분이 만일 어떤 객체 내용을 네트워크를 통해 다른 프로그램에게 전송한다고 생각해 보세요. 여기서는 일종의 메신저 혹은 채팅 프로그램에서 쓰는 하나의 메시지라고 간주해봅시다. 다음 객체를 어떻게 보낼 수 있을까요?

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

객체라는 것이 전송 가능(transferable)하려면 애초에 수신자(reciever), 발신자(sender) 모두가 같은 프로그램을 쓰거나, 아니면 문자열과 같이 범용적으로 읽을 수 있는 형태여야만 할 것입니다.

혹시나 싶어 엔지니어는 message.toString() 메소드나, String(message)를 시도해보았지만, 리턴되는 것은 그저 [object Object]라는 메시지 뿐이었습니다.

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

이 문제를 인지한 엔지니어는, 다른 방법을 찾기 시작했고, 객체를 문자열로 멋지게 변환하는 JSON.stringify 함수를 mdn을 통해 알아낼 수 있었습니다.

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

stringify하는 이 과정을 직렬화(serialize)한다고 합니다.

이제는 문자열 그 자체로 누군가에게 객체 내용을 보낼 수 있게 되었습니다. 자 이제 수신자는 이 메시지를 어떻게 다시 객체로 만들 수 있을까요? 정확히 JSON.stringify와 반대의 일을 하는 JSON.parse가 여기 있습니다.

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

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

parse하는 이 과정을 역직렬화(deserialize)한다고 합니다.

이처럼, JSON은 서로 다른 프로그램 사이에서 데이터를 교환하기 위한 포맷이며, 단순히 자바스크립트에서만 쓰이는 것이 아닌, 여타 다른 언어에서도 범용적으로 쓰이는 아주 유명한 포맷입니다.

2. JSON 규칙

JSON을 얼핏 보기에 자바스크립트의 객체와 별반 다를 바가 없어 보이지만, 자바스크립트의 객체와는 미묘하게 다른 규칙이 있습니다.

또한 JSON은 키와 값 사이, 그리고 키-값 쌍 사이에는 공백이 있어서는 안됩니다.

profile
soheey
이전 포스트

Level 4-2. JavaScript 심화 개념

다음 포스트

10

0개의 댓글