Data Structure & Algorithm
3주차 - 재귀로 짜는 이진 트리 순회, 그리고 BST가 성능을 보장하는 이유
전위/중위/후위 순회를 재귀로 구현하며 결과 배열을 함수 밖에 두는 대신 중첩 함수로 감싸는 방법부터, 이진 트리 구조 자체는 탐색 성능을 보장하지 않는다는 것, 균형이 무너지면 O(log n)이 O(n)이 되는 이유, 캐시 지역성 때문에 DB가 이진 트리 대신 B+트리를 쓰는 이유까지.
재귀
하나의 주제로 이어지는 배움의 기록.
2개의 기록 최신순
Data Structure & Algorithm
3주차 - DP는 재귀가 반복하는 일을 기억해두는 것, 피보나치와 계단 오르기로 확인
재귀가 같은 하위 문제를 계속 반복 계산할 때 memo로 기억해두는 하향식(탑다운) DP와, 밑바닥 값부터 채워 올라가는 상향식(바텀업) DP를 피보나치 수열과 계단 오르기 문제로 각각 구현.