[자료구조/ 알고리즘] JSON (+재귀)

JSON(Javascript Object Notation)

: 서로 다른 프로그램에서 데이터를 교환하기 위해 만들어진 객체 형태의 포맷

많은 언어에서 범용적으로 사용하는 유명한 포맷임

 

네트워크를 통해 객체 내용을 전송하려면

- 수신자와 발신자가 같은 프로그램을 사용하며

- 문자열처럼 범용적으로 읽을 수 있어야 하는데

 

객체 타입을 문자열로 변환하기 위해 메서드나 형변환을 시도하면 아래처럼 [object Object] 반환

obj.toString()
String(obj)
// [object Object]

 

이를 해결하기 위해 JSON 형태를 사용

JSON.stringify()

객체를 JSON으로 변환

= 직렬화(serialize)

(문자열 타입)

 

JSON.parse()

JSON을 객체로 변환

= 역직렬화(deserialize)

 

 

JSON과 자바스크립트 객체는 비슷해보이지만 조금 다른 규칙을 가지고 있음

	JSON	JS object
키	반드시 쌍따옴표를 붙여야함 '{"key":"property"}'	따옴표 없이도 쓸 수 있음 { key : "property" }
문자열 값	반드시 쌍따옴표를 붙여야함 '{"key":"property"}'	큰/ 작은 따옴표 사용 가능 { "key" : 'property' }
키-값, 키값쌍 사이 공백	사용 불가 '{"key":"property","num":1}'	사용 가능 { "key" : 'property', num: 1 }

 

 

 

 

 

(+ 추가학습)

재귀 함수와 메모리 사용량 간의 관계 (javascript recursion memory leak)

- 스택(Stack)

자료의 입출력이 언제나 목록의 한 쪽 끝에서만 일어남

후입선출(LIFO. Last In First Out)

 

재귀 함수를 사용하면 함수의 호출이 스택에 차곡차곡 쌓이게 되고, 

위에서부터 순서대로 값을 반환하기 전에는 메모리 공간을 계속 차지하고 있게됨

-> 호출 스택이 너무 커져 메모리 사용량이 많아질 수 있음

따라서 재귀보다 반복문을 사용했을 때 성능이 좋은 경우가 많다

 

 

꼬리 재귀 (tail recursion in js)

재귀 함수 호출로 인해 발생할 수 있는 위험을 방지

- 스택 오버 플로우: 스택의 최대 크기 이상의 메모리가 쌓이게 될 경우 발생

- 잦은 점프의 반복으로 인한 성능 저하

 

꼬리 재귀 최적화를 위한 조건 2가지

- 재귀 함수를 꼬리 재귀 방식으로 구현할 것

- 컴파일러가 꼬리 재귀 최적화를 지원할 것

int FactorialTail(int n, int acc) // acc : accumulator의 약자
{
	if (n == 1) return acc;
	return FactorialTail(n - 1, acc * n);    
    // 일반 재귀에서의 n * Factorial(n-1)와 달리 반환값에서 추가 연산을 필요로 하지 않음
}


int Factorial(int n)
{
	return FactorialTail(n, 1);
}

 

 

하노이의 탑 재귀 (js tower of hanoi in recursion)

막대 A에 쌓여있는 원반을 순서대로 막대C로 옮기기(막대 B 이용)

 

조건

- 한 번에 움직일 수 있는 원반은 기둥 맨위의 원반 하나

- 작은 원반 위에 큰 원반을 쌓을 수 없음

 

풀이 과정

1. 막대 A의 작은 원반 n-1개를 막대 B로 옮기기

2. n번째 원반을 막대 C로 옮기기

3. 막대 B의 작은 원반 n-1개를 막대 C로 옮기기

function hanoiTower(num, start, end, by) {
  if (num === 1) {
    console.log(`${num}번째 원반을 ${start}에서 ${end}로 이동`)
  } else {
    hanoiTower(num-1, start, by, end)
    console.log(`${num}번째 원반을 ${start}에서 ${end}로 이동`)
    hanoiTower(num-1, by, end, start)
  }
}

// num: 원반 개수
// start: 기본 막대(출발)
// end: 옮길 막대(도착)
// by: 거칠 막대(경유)

 

 

조합 재귀 함수 (js combination in recursion)

순열(permutation)
: n개 중에 r개를 뽑아 줄 세우는 경우의 수(nPr, nCr*r!, n!/(n-r)!)

조합(combination)
: n개 중에 r개를 뽑는 경우의 수(nCr, nPr/r!, n!/(r!(n-r)!))

조합

 

 

 

 

참고

재귀 함수와 메모리 사용량 간의 관계

꼬리 재귀

하노이의 탑

하노이의 탑2

순열과 조합

 

 

 

 

 

22.12.16

코스 S3U1