[TIL] 2주차_Day5: 자료구조/알고리즘 풀기(5)

💡Today I Learned

• 자료구조/알고리즘에 대한 다섯 번째 이론 및 실습 강의를 진행했습니다.
• 코딩테스트 연습 _ 프로그래머스 코딩테스트 연습 문제 풀이
• 해시, 그리디, 정렬 알고리즘을 사용하는 대표 문제 풀이

 

---

 

1. 힙(Heap) 대표 문제: #더 맵게

- 최악의 경우: 수가 하나 남을 때까지 섞어야하는 경우 → n-1 회

- 각 단계(=섞는 일)에서 요구되는 계산량: 섞은 아이템을 정렬된 리스트 내에 삽입 → O(N)

→ 전체 문제의 복잡도: O(N^2) 느림

→ 최대/최소 원소를 빠르게 꺼내기를 원함 = max/min heap 자료구조 사용

 

- 연산별 복잡도

• heapify → O(NlogN) _ 빈 힙에 N개의 원소를 하나씩 넣어가며 heap을 유지
• insert → O(logN)
• remove → O(logN)

- 힙의 구현: 완전 이진 트리(Complete Binary Tree), 배열을 이용해 구현 가능

- 힙의 응용: 1) 정렬(heap sort, O(NlogN))  2) 우선순위 큐(priority queue)

 

*)파이썬에서의 힙 사용

import heapq

L = [2, 5, 4, 8, 6, 9, 1]
heapq.heapify(L)  # 리스트 L로부터 min heap 구성
m = heqpq.heappop(L)  # min heap L에서 최솟값 삭제&리턴

x = 7
heapq.heappush(L, x)  # min heap L에 원소 x 삽입

 

2. 동적계획법(Dynamic Programming) 대표 문제: #N으로 표현

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

- ex) 피보나치 수열: Fib[n] = Fib[n-2] + Fib[n-1] (n ≥ 2)

- ex) Knapsack Problem _ 가장 높은 값을 가지도록 물건을 골라 배낭에 담기 (배낭에 담을 수 있는 무게Kg는 한정적)

 

- N을 k회 사용해 'number'을 만들 수 있는 경우들 중 k의 최솟값을 리턴

- 1) N을 k회 늘어놓기  2) N을 k번 사용해 사칙연산으로 계산

- k = 1, 2, 3, ... 일때가 계산돼 배열(dp[k])에 저장

- ex) dp[2] → dp[1]일때의 값 끼리 사칙연산(+ - / *) 해 결과값들을 dp[2]에 저장

 

3. 깊이/너비 우선 탐색(DFS/BFS) 대표 문제 풀이: #여행 경로

- DFS: 한 정점에 인접한 모든 정점 방문하되, 1) 각 인접 정점을 기준으로 DFS를 끝낸 후  2) 다음 정점으로 진행 / stack 이용

- BFS: 1) 한 정점에서 인접한 모든 정점을 방문하고, 2) 방문한 각 인접 정점을 기준으로 또다시 BFS 행함 / queue 이용

 

 

---

 

📒 Furthermore

• Knapsac Problem → 다이나믹 프로그래밍으로 풀이한 알고리즘 확인하기
• 코딩테스트 연습 문제 풀이