11/23 (자료 구조와 탐색, 수) TIL

(어제에 이은) 자료 구조:

• 트리 : 완전 이진 트리의 경우 잎 노드에서 뿌리 노드까지 도달하는 데 $O(logN)$ 단계가 필요함.

• 힙 : 최대힙과 최소힙이 있음. 완전 이진 트리의 일종이므로 원소 추가와 삭제시 시간 복잡도는 최대 $O(logN)$이 된다.

• 그래프 : 노드와 노드 사이의 연결 관계를 강조하여 나타낸 자료 구조. 인접 행렬과 인접 리스트로 표현할 수 있음.

트리와 그래프를 탐색하기:

DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색) 모두 인접 리스트를 데이터 삼아 구현을 연습했다. 인접 행렬로 표현한 버전이 연결 관계를 찾을 때 O(1)의 시간만으로 빠르게 찾는다던데, 정작 탐색을 할 때는 어떻게 활용해야 할지 모르겠다.

다이나믹 프로그래밍과 메모이제이션:

내가 이해하기로는 보통의 재귀 함수에 그 때까지의 계산 값을 저장해 둔 메모를 덧붙여서 사용하는 방식을 다이나믹 프로그래밍이라고 하는 것 같다. 그 때까지의 계산 값을 메모해 놓는다고 해서 메모이제이션을 활용한다고 하고.

피보나치 수열처럼 ‘반복되는 형태로 작은 문제가 계속해서 파생된다면’ 다이나믹 프로그래밍으로 풀어야겠다고 생각하면 된다.

하지만 어째서 ‘다이나믹’ 프로그래밍인가? 이 전까지의 프로그래밍은 그럼 정적인 프로그래밍이었다는 말인가? 재귀에 메모이제이션을 덧붙인 어느 부분이 그렇게 다이나믹하다는 걸까..?

강의에 덧붙여 나오는 숙제 문제들이 기하급수적으로 어려워졌다. 세 문제 중 하나를 붙잡고 저녁 전부터 잠자기 직전까지 고민 중이다. 아니 이렇게 논리가 복잡해지는 게 맞는 거야..? 내가 쓴 코드 내일 다시 보면 나도 이해 못할 것 같은데.

Uploaded by N2T