DataStructure Intermediate

TaeWoo Lee / Kris·2022년 4월 5일
0

트리

트리의 종류

  • 이진트리

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

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

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

  • 편향이진트리

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

재귀함수

  • 재귀함수란

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

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

0개의 댓글