Data Structure & Algorithm
3주차 - 재귀로 짜는 이진 트리 순회, 그리고 BST가 성능을 보장하는 이유
전위/중위/후위 순회를 재귀로 구현하며 결과 배열을 함수 밖에 두는 대신 중첩 함수로 감싸는 방법부터, 이진 트리 구조 자체는 탐색 성능을 보장하지 않는다는 것, 균형이 무너지면 O(log n)이 O(n)이 되는 이유, 캐시 지역성 때문에 DB가 이진 트리 대신 B+트리를 쓰는 이유까지.
Data Structure & Algorithm
하나의 주제로 이어지는 배움의 기록.
8개의 기록 최신순
Data Structure & Algorithm
3주차 - DP는 재귀가 반복하는 일을 기억해두는 것, 피보나치와 계단 오르기로 확인
재귀가 같은 하위 문제를 계속 반복 계산할 때 memo로 기억해두는 하향식(탑다운) DP와, 밑바닥 값부터 채워 올라가는 상향식(바텀업) DP를 피보나치 수열과 계단 오르기 문제로 각각 구현.
Data Structure & Algorithm
3주차 - 그래프 탐색, BFS와 DFS를 직접 구현하며 비교
인접 리스트로 무방향/방향 그래프를 만드는 것부터, Queue로 너비 우선 탐색하는 BFS와 재귀로 깊이 우선 탐색하는 DFS를 각각 구현하고 장단점을 비교. 시간 복잡도는 둘 다 O(V+E).
Data Structure & Algorithm
3주차 - Greedy는 매 순간의 최선이 전체 최선이 되는 상황, 거스름돈과 회의실 배정으로 확인
매번 가장 큰 동전을 고르는 거스름돈 문제와, 종료 시간이 가장 빠른 회의부터 고르는 회의실 배정 문제로 그리디 알고리즘이 '순간의 최선'을 반복하는 원리를 확인.
Data Structure & Algorithm
3주차 - LCS(최장 공통 부분수열)를 DP 테이블로 구하기
두 문자열을 각각 행과 열에 두고, 같으면 대각선 위에 1을 더하고 다르면 위/왼쪽 중 최댓값을 가져오는 방식으로 LCS 길이를 채워나가는 DP 테이블 구현.
Data Structure & Algorithm
3주차 - 트리가 한쪽으로 쏠리는 것을 막는 균형 이진 트리, RB트리
BST가 데이터 쏠림으로 O(n)까지 느려질 수 있다는 문제에서 출발해서, RB트리의 색 규칙과 Black Height, 그리고 Rotation·Recoloring으로 Double Red를 복구하는 과정을 정리.
Data Structure & Algorithm
3주차 - 위상 정렬, 순서 관계와 위상이 같은 개념인 이유
위상 수학의 '위상'이 순서 관계와 일대일 대응한다는 것에서 출발해서, DAG의 모든 간선 (u,v)에서 u가 v보다 앞에 오도록 정렬하는 위상 정렬을 구현하고 장단점을 정리.
Data Structure & Algorithm
2주차 - Mark & Sweep, GC는 도달 가능성을 어떻게 판단할까
Mark & Sweep 알고리즘이 루트에서 시작해 도달 가능한 객체를 표시하고 나머지를 회수하는 원리와, 루트가 될 수 있는 세 부류를 정리.