200820_TIL

Today I learned

• 재귀함수 & Recursion 과제
• 시간 복잡도

[재귀]

• 어떤 함수가 스스로를 호출하는 함수

  • 실행과정 중에 자기 자신을 호출

• 잘게 쪼개어 더 작은 문제로 나뉘어 질 수 있는 경우 사용

• 중첩 루프가 많아서 중첩의 정도를 미리 알 수 없는 경우 사용

• 모든 재귀함수는 재귀 호출 없이 while / for loop로 표현이 가능하다

• 팩토리얼 함수

• 재귀적 사고

  • 문제를 여러 경우로 구분
    • 쉬운 문제부터 해결

• 활용

  • 트리 구조에 재귀 함수 활용
  • JSON 구조에 함수를 활용
  • DOM 구조에 재귀함수를 활용

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

  • 메모리 누수
  • 더 이상 필요하지 않는 메모리
  • garbage collected languages
  • 필요한 메모리의 질문과 접근 가능한 메모리에 대한 고민으로의 전환
  • cause for leaks = unwanted references.
  • garbage collector 는 윈도우 객체에 도달되는 모든 객체들에 대해서 활성화 표시를 하고, 이는 garbage로 간주되지 않는다.
    - 전역변수 남발, 타이머 또는 콜백 함수 관리, DOM 참조를 유지할 때, 클로저를 사용할 때 주의하면 메모리 누수를 방지 할 수 있다.
    

  참고글: 자바 스크립트에서 발생하는 4가지 메모리 누수 유형 및 이를 방지하는 방법
  

• 하노이의 탑과 조합(combination) 문제

• 꼬리 재귀 (tail recursion in js)

  • 함수는 호출 시 콜 스택에 쌓인다.
  • 수많은 재귀가 쌓이면 스택 버퍼 오버플로우가 발생
  • 이를 방지하기 위해 꼬리 재귀 함수가 존재
  • 스택을 위한 메모리를 더 적게 사용 가능

• 조합 재귀함수 (js combinaton in recursion)

• 시간 복잡도

  • 빠른 알고리즘, 느린 알고리즘 와 같이 알고리즘에 대한 분석.

  • 모바일 디바이스에 대한 제약.

  • 머신러닝과 같은 많은 컴퓨터 자원을 필요로 하는 작업을 할 때 시간 복잡도를 고려하면 자원 활용도를 높일 수 있다.

  • 문제 n개가 늘어날 수록 소요 시간의 증가율.

  • 효율적 알고리즘에 대한 접근방법

    • 숫자들을 비교하여 숫자 차이에 대한 최대값을 구하려고 할 때
      1. 모든 숫자에 대해 비교해본다. n*n
      2. 가장 작은 숫자와 가장 작은 숫자를 찾아본다. 그 차를 구한다. (2n)
      3. 처음과 마지막 숫자만 비교한다 (1)

  • 복잡도 타입

    • 정확한 값이 아닌 근사치를 표현한다. (앞에 계수를 무시한다) ex) 2n - > n
    • 낮은 차수의 숫자는 무시한다 ex) n+2 , n + 3 → n, n

[Comment]

@@ 오늘은 underbar에 이어서 recursion 과제를 진행했다. underbar 여파인지, 뇌정지(?)가 자주 와서 버벅 버벅, 너무 어렵게 느껴졌다. 재귀함수가 낯설기도 하고 항상 독학 할때도 고차함수, 재귀 이 파트 전에 멈췄어서 그런지 더 무겁게 다가왔다.

페어 프로그래밍 하며 페어분 도움 받아 어찌저찌 1문제 클리어 하고, 저녁 개인시간 때 다시 봤다. AMA 덕에 힌트를 많이 얻어서 초기화 하고 다시 접근하니, 어려워서 콘솔만 몇 십번 찍었던 문제가 홀연히 통과됐다. (어안이 벙벙...)

기분 좋긴 한데, 오늘 DOM 파트부터 연습 부족, 개념 숙지 부족이라는 경고등이 떴다. 내일이면 pre 과정 마지막 날인데, 긴장 늦추지 말고 복습 또 복습에 매진해야겠다.