트리

트리의 종류

• 이진트리

  • 최대 두 개의 자식 노드를 가지는 트리 형태의 자료구조

• 이진탐색트리

  • 자식 노드가 최대 2개까지만 붙는 이진트리의 형태를 띄면서

  • 이진탐색트리는 정렬되어서 들어오는 데이터에 약하다.

• 편향이진트리

  • 한 쪽 방향의 자식 노드를 가지는 이진트리 ex) 왼쪽 자식노드만 가진다.

재귀함수

• 재귀함수란

  • 함수가 자기자신을 다시 호출하는것, 종료조건이 정상작동한다.
    • 종료조건이 충족될 때까지 반복적으로 스스로 불러내면서 주어진 작업을 수행하는 것
  • 반복문과 스택 구조가 결합된 함수이다.
  • 파이썬 함수 -> 콜스택 형태

• 재귀적인 문제 해결

  • 한단계 낮은 문제가 해결된다면, 그것을 바탕으로 답을 얻을 수 있다.
  • 재귀함수 작성시
    • 재귀호출할 때 인자를 반드시 규모가 줄어들도록 설정
    • 재귀호출없이 해결할 수 있는 최소문제(base case) 설정하기
      • 이때는 재귀호출 하지 않고, 바로 답을 반환할 수 있도록 하기!