[alice] 자료구조의 끝판왕

알고리즘을 위한 자료구조

[4장 자료구조의 끝판왕]

프로그램의 핵심: 되풀이

비슷한 일을 여러번 되풀이해서 풀어내기

1. 반복(Iteration): for, while
2. 재귀(Recursion)

재귀(Recursion)

• 스스로를 호출하는 방식의 반복법
• 식의 종료 조건 필요(=Base 조건)
• ex) factorial(n) = n * factorial(n-1)

 

[실습- 팩토리얼]

 

동적 프로그래밍(Dynamic Programming)

• 재귀 + 정보 저장 (메모이제이션)
• 저장 값을 다른 자료 구조에 저장

[실습- 피보나치]

 

 

트리

• 나무 형태의 자료구조
• 부모노드 -> 자식노드 방향으로 연결이 존재
• 루트(root): 부모x 노드
• 리프(leaf): 자식x 노드
• 트리의 깊이(Depth): 루프-리프까지의 경로의 길이
• 루트는 1개
• 방향성 존재
• 순환 구조x

 

이진 트리

모든 노드가 최대 2개의 자식노드를 가지는 트리 (2개이하)

 

1) 완전 이진 트리(Complete Binary Tree)

• 마지막 레벨 제외 노든노드가 채워져 있는가?
• 마지막 레벨 노드가 왼쪽부터 채워져 있는가?

2) 포화 이진 트리(Full Binary Tree)

• 전부 채워진 구조

이진 탐색 트리(Binary Search Tree)

모든 부모 노드의 값이 왼쪽 자식 트리에 있는 값보다는 크고

오른쪽 자식 트리에 있는 값보다는 작은 형태의 트리

 

※ 트리 관련 문제의 핵심 = 탐색

• 루트 노드가 주어졌을 때 트리를 구석구석 훑어가며 원하는 목적을 달성하는 것
• 반복 or 재귀 사용!

 

[실습- 이진 트리 출력]

이건 좀 이해하기 헷갈린다

 

 

너비 우선 탐색(BFS)

Breadth First Search: 반복 기반의 탐색

• 큐에 노드를 순서대로 넣고 빼는 방식으로 탐색
• 횡적으로 한 층씩 탐색하는 방식

 

깊이 우선 탐색(DFS)

Depth First Search: 재귀 기반의 탐색

• 가장 깊은 곳까지 내려갔다가 오는 방식의 탐색

 

 

[수료]