[알고리즘] Heap, Dynamic Programming, DFS/BFS

1. 더 맵게 (Heap)

Heap은 이진트리 기반의 자료구조이며, max/min 값을 빠르게 찾기 위해 사용된다. Complete Binary Tree의 형태를 띄며, 부모 자식 노드 간에는 특정한 크기 관계가 성립한다.

문제 설명

• N개의 수와 K값이 주어짐.
• 가장 작은 수 + (두 번째로 작은 수 * 2) → 하나의 수
• 모든 수가 K 이상이 되도록 → 얼마나 + 해야하는가?
• 모든 값을 K 이상으로 만들 수 없는 경우 → -1 리턴 (한 개만 남았는데, 그 값이 K 이상이 아닌 경우)

알고리즘 복잡도

• 최악의 경우
  • 수가 하나 남을 때까지 섞어야 하는 경우 (n-1회)
  • 섞은 값 정렬된 배열 어디 들어가야 하는가 (O(n))
  • → 전체 문제 풀이의 복잡도 : O(n^2) → 지나치게 높다.

난 위와 같이 풀었다.

더 좋은 방법 Heap을 생각해볼 수 있다.

최소/최대 원소를 빠르게 꺼낼 수 있는 자료구조.

Heap → max heap, min heap

연산 종류

• 힙 구성(heapify, O(NlogN))
• 삽입(insert, O(logN))
• 삭제(remove, O(logN))
• 값을 찾는 데에는 N만큼의 시간, 삽입과 삭제를 위해서는 총 logN 시간

아래는 Max heap의 구현

Complete binary tree로 만듦으로써 배열을 이용해서 구현 가능하다.

index를 가지고 child node, parent node를 찾을 수 있다.

힙의 응용

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

최소 힙 (Min heap)이 디폴트다.

import heapq
heapq.heapify(L)  # 리스트 L로부터 min heap 구성
m = heapq.heappop(L)  # min heap L에서 최소값 삭제 (반환)
heapq.heappush(L, x)  # min heap L에 원소 x 삽입

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while True:
        min1 = heapq.heappop(scoville)
        if min1 >= K:
            break
        elif len(scoville) == 0:
            answer = -1
            break
        min2 = heapq.heappop(scoville)
        heapq.heappush(scoville, min1+min2*2)
        answer += 1
    return answer

---

2. N으로 표현 (Dynamic Programming) 다시 봐야겠음

12 = (55+5)/5 → 5를 4개 사용해서 계산식을 만들 수 있다.

이것을 어떻게 찾을 수 있을까?

문제에 답인지 확인해야 하는 부분을 순차적으로 봐야한다. 최적화 문제를 해결할 때 주로 사용한다. 재귀적인 방식으로 보다 작은 부분 문제로 나누어서 풀고, 이 부분 문제에 대한 답을 조합하여 전체 문제의 해답에 이르는 방식이다.

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

피보나치 문제가 그리 적합한 예시는 아닌데, 한 번 봐보면…

Ex) 피보나치 수열 → 재귀 (지수함수 형태의 복잡도)

동적 계획법 적용한다면? → 선형함수 형태의 복잡도 (주어진 수에 비례하는 복잡도)

또 다른 예시로 Knapsack Problem이 있다. = 가장 높은 값을 가지도록 물건을 골라 담는 문제.

---

3. 여행 경로 (DFS/BFS)

이산 수학 - 그래프에 기반한 DFS/BFS를 활용한다.

• 정점과 간선
• 유향, 무향 그래프
• 스택
• 큐

DFS - 깊이 우선 탐색

한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 이동

위와 같은 무향 그래프가 있을 때, 탐색 순서는 아래와 같다.

0 → 1 → 3 → 7 → 4 → 5 → 2 → 6

생각을 해보면, Stack 을 이용하여 어느 정점에서 DFS를 하고 있는지를 기억하고 되돌아가게 된다.

BFS - 너비 우선 탐색

한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하고, 방문한 각 인접 정점을 기준으로 (방문한 순서에 따라) 또다시 너비 우선 탐색을 행함

BFS의 경우 탐색 순서는 아래와 같다.

0 → 1 → 2 → 3 → 4 → 5 → 6 → 7

DFS는 Stack을 사용했다면, BFS는 Queue를 이용하여 어느 정점에서 BFS를 해야 하는지를 기록하고 진행한다.

예를 들어, 0번 노드에 위치해 있을 때 1과 2를 Queue에 집어 넣음. → 1, 2 방문

문제 살펴보자.

주어진 항공권 모두 이용하여 여행경로를 짠다.

• 한 붓 그리기.
  • 이것이 가능함은 문제에서 보장되어 있음.
• 모든 정점 방문이 목적이 아니고, 모든 간선을 거치는 것이 목적이다.
• 언젠가는 한 번 가야 하는데, 그 순서를 결정해야 한다.
• 한 정점에서 택할 수 있는 간선이 두 개 이상인 경우 ?
  • 공항 이름의 알파벳 순서를 따라야 한다.

알고리즘 설계

Stack과 DFS를 응용하여 해결할 수 있다.

간선을 하나씩 지우면 된다. 재귀적인 느낌으로..

• 방문하는 공항을 Stack에 집어 넣는다.
  • 왜냐면, DFS에서 어디를 가면 내가 어디까지 간지를 알아야 하기 때문이다.
• 결과적으로는 Stack에서 꺼낸 것 역순이 정답.