검색과 재귀(Searching and Recursion)

검색

• 특정 노드를 추가하거나 삭제를 위해서는 검색이 우선되야한다
• 다양한 알고리즘을 활용하는 경우, 최적 알고리즘 경로를 측정하는데 쓰인다
• 검색하는 컬렉션이 무작위이고 정렬되고 않은 경우, 선형검색이 기본적인 검색방법이다

재귀

• 알고리즘과 방법론을 자주 언급되고, 중요한 개념이므로 반복하며 익숙해져야한다.
• 문제를 해결하는 재호출 로직을 발견해야한다
• 스택의 개념이 적용되며, 함수의 내부는 스택 처럼 관리된다 (LIFO)
  • 단점: 재귀를 사용하면 함수를 반복적으로 호출함으로 메모리를 더 많이 사용한다
  • 수학적 개념이 복잡한 경우에는 메모리나 시간적 효율이 안좋아도 재귀를 사용하는것이 좋다
  • ** 분할정복법에 재귀가 사용된다
    • 재귀는 해결을 위한 특정 기능을 재호출 하는것이고 분할정복은 문제를 분할하고 해결하는 구체적인 방법론이다
• 재귀에서 중요한 부분은 조건에 따른 반복 계산이다:
  1. base case(기본 케이스, 또는 조건)이 있어야 한다
  2. 추가 조건과 기본 케이스의 차이를 확인한다
  3. 반드시 자기 자신(함수)를 호출해야 한다
• 재귀 제한
  • 파이썬은 재귀 깊이의 제한을 1000으로 기본 설정을 잡고 있다
  • 재귀 함수가 1000이 도달하면 RecursionError가 뜬다
  • 해결을 위해서는 깊이를 늘려야한다

Tree

용어:

• 루트(root) : 가장 위쪽에 있는 노드, 트리별 하나만 있다.
  • 루트와 부모는 다르다. 부모노드는 자식노드가 1개 이상 있는 경우에만 존재할 수 있다.
• 서브트리 : 자식노드이면서 부모노드역할을 하는 노드가 있는 트리
• 차수 : 노드가 갖고 있는 최대 자식노드 수
  • 위의 경우 차수는 2개이다
    • 10의 차수, 8의 차수, 9의 차수, 1의 차수
• 리프(leaf) : 레벨별로 가장 마지막에 있는 노드, 단말노드(terminal node), 외부노드(external node)라고도 한다. 리프는 트리별로 여러 개가 있을 수 있다.