TIL_221018 재귀, 자료구조 알고리즘

핵심단어

검색, 재귀, 트리

학습목표

• 검색과 재귀에 대해 익히기
• 트리의 기본을 익히기

WARM UP

https://youtu.be/LnxEBW29DOw

• TREE
  • 부모 자식간의 관계를 가지는 구조
  • LEAF - 더 이상 자식을 가지지 있는 노드
  • Binary tree - 자식 노드가 2개까지만
  • Ternary tree - 세 개 이상
  • Balance - 밸런스
  • 완전 이진트리

참고용

https://pythontutor.com/visualize.html#mode=edit
https://visualgo.net/en
https://geonlee.tistory.com/m/72

코드링크

자료구조와 활용

검색

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

재귀

재귀 정말 정말 중요한 개념!

• https://youtu.be/rJALa9MW7M4 링크 참고
• 재귀 호출은 스택의 개념이 적용되고, 함수 내부는 스택처럼 관리됨(후입후출)
  • 단점 : 함수를 반복적으로 사용하기 때문에 메모리 사용과다
  • 단, 수학적으로 개념이 복잡한 경우 효율이 안 좋더라도 재귀 사용

재귀로 문제를 해결 하는 법

• 하위 문제를 쉽게 해결할 수 있을 때까지 문제를 더 작은 하위 문제로 나누기
• 문제를 분할하고 해결해서, 해결 한 문제를 다시 합치는 분할정복법이 대표적