자료구조/알고리즘 (5)

힙 (Heap) 대표 문제 풀이: 더 맵게

알고리즘의 복잡도

• 최악의 경우 : 수가 하나 남을 때까지 섞어야 하는 경우 (n-1회)
• 각 단계(섞는 일)에서 요구되는 계산량 : 정렬된 리스트에 순서 맞추어 원소 삽입, O(n)
• 전체 문제 풀이의 복잡도: O(n^2), 지나치게 높다.

보다 나은 방법

• 최소/최대 원소를 빠르게 꺼낼 수 있으면 좋을 듯
• 힙 : max heap, min heap

완전 이진트리 -> 배열을 이용해서 구현 가능

힙의 응용

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

python에서 힙 적용

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

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while True: #while 조건보다 break가 더 편리하다 판단
        min1 = heapq.heappop(scoville)
        if min1 >= K:
            break
        elif len(scoville)==0:
            answer = -1
            break
        min2 = heapq.heappop(scoville)
        new_scoville = min1 + 2 * min2
        heapq.heappush(scoville, new_scoville)
        answer += 1
    return answer

-> O(nlogn)

동적계획법 (Dynamic Programming) 대표 문제 풀이: N으로 표현

동적계획법 (Dynamic Programming)

• 주어진 최적화 문제를 재귀적인 방식으로 보다 작은 부분 문제로 나누어 부분 문제를 풀어 이 해(solution)를 조합하여 전체 문제의 해답에 이르는 방식
• 알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정 할 수 있음

ex) 피보나치 수열, Knapsack Problem

문제의 복잡도

(발생할 수 없는) 최악의 경우

실제로 만들어지는 결과의 개수

요약

문제의 성질에 따라, 동적계획법으로 풀어냄으로써 탐색해야 하는 범위를 효과적으로 줄일 수 있음

#테스트 케이스 8 실패 다시 한번 볼 필요 있음
def solution(N, number):
    s = [set() for x in range(8)]
    for i, x in enumerate(s, start=1):
        x.add(int(str(N) * i))
    for i in range(1, len(s)):
        for j in range(i):
            for op1 in s[j]:
                for op2 in s[i - j - 1]:
                    s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                        s[i].add(op1 // op2)
        if number in s[i]:
            answer = i + 1
            break
    else:
        answer = -1
    return answer

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

배경지식

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

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

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

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

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

문제의 해결 - 깊이 우선 탐색 (DFS) 을 응용

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

알고리즘의 설계

스택을 이용하여 재귀적인 "한 붓 그리기" 문제를 해결 -> DFS 알고리즘의 응용

def solution(tickets):
	routes = {}
    for t in tickets:
    	routes[t[0]] = routes.get(t[0], []) + [t[1]]
    for r in routes:
    	routes[r].sort(reverse=True)
    stack = ["ICN"]
    path = []
    while len(stack) > 0:
    	top = stack[-1]
        if top not in routes or len(routes[top]) == 0:
        	path.append(stack.pop())
        else:
        	stack.append(routes[top][-1])
            routes[top] = routes[top][:-1]            
    return path[::-1]

-> O(nlogn)