[1주차 - Day04] 파이썬을 무기로, 코딩테스트 광탈을 면하자! (2)

Step 3. 힙(heap)

---

• 성질 : 최대/최소 원소를 빠르게 찾을 수 있음
• 연산
  • 힙의 구성(heapify)    O(NlogN)
  • 삽입(insert)             O(lonN)
  • 삭제(remove)           O(logN)

완전 이진 트리(complete binary tree) 성질을 가지고 있다.

-> 배열을 이용해서 구현 가능

 

힙의 응용

• 정렬(heapsort)
• 우선 순위 큐(priority queue)

 

Step 4. 동적계획법(Dynamic Programming)

---

주어진 최적화 문제를 재귀적인 방식으로 보다 작은 부분 문제로 나누어

부분 문제를 풀어, 이 해를 조합하여 전체 문제의 해답에 이르는 방식

알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써

탐색 범위를 한정할 수 있음

 

 

적용 예

Ex) 피보나치 수열

 

• 재귀함수로 구현한다면?

f(4) = f(3)                    + f(2)

     = f(2) + f(1)            + f(1) + f(0)  
     = f(1) + f(0)  + f(1)   + f(1) + f(0) 

 

 

• 동적계획법을 적용한다면?

f(0) = 0,      f(1) = 1

f(2) = f(1) + f(0) = 1

f(3) = f(2) + f(1) = 2

f(4) = f(3) + f(2) = 3

복잡도 : 선형함수의 형태 

 

 

Step 5. 깊이/너비 우선 탐색(DFS, BFS)

---

배경지식

• 그래프(graph)
  • 정점(vertex, node) 과 간선(edge, link)
  • 유향(directed, 방향) 그래프와 무향(undirected, 무방향) 그래프
• 스택
• 큐

 

깊이 우선 탐색(DFS; Depth-First Search)

한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 반문하되,

각 인점 정점을 기눚으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행

 

스택을 이용하여 어느 정점에서 DFS 를 하고 있는지를 기억하고 돌아감

 

너비 우선 탐색(BFS; Breadth-First Search)

한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하고,

방문한 각 인접 정점을 기준으로 (방문한 순서에 따라) 또다시 너비 우선 탐색을 행함

 

큐를 이용하여 어느 정점에서 BFS 를 해야 하는지를 기록하고 진행함