[TIL - 5일 차] 데이터 엔지니어링 : 자료구조/알고리즘 풀기 (5)

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

문제

문제

힙(Heap)

• 최대/최소 원소를 O(1) 시간으로 빠르게 찾을 수 있음
• 종류 : 최대 힙(max heap), 최소 힙(min heap)
• 연산 : 힙 구성(heapify, O(n log n)), 삽입(insert, O(log n)), 삭제(remove, O(log n))

힙의 구현과 응용

• 최대 힙을 기준으로 root node에 최댓값이 위치
• 완전 이진트리로 구성돼 있으며, 배열을 이용해서 구현 가능
• 응용 : 정렬(Heapsort), 우선순위 큐 (priority queue)

Python에서의 힙 적용

• 연산 : heapify(list), heappop(list), heappush(list, value)

import heapq

# 리스트 L로부터 min heap 구성
heapq.heapify(L)

# min heap L에서 최솟값 삭제/반환
m = heapq.heappop(L)

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

풀이 (1)

지속적인 정렬을 통해 가장 작은 값이 k보다 클 때까지 스코빌 지수를 계산

알고리즘의 복잡도

• 수가 하나 남을 때까지 섞어야 하는 경우, n - 1회
• 각 단계에서 정렬된 리스트에 원소 삽입, O(n)
• 최종 시간 복잡도 : O(n^2)

풀이 (2)

최소 힙을 활용하여 힙의 가장 작은 값이 k보다 클 때까지 스코빌 지수를 계산

코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)

    # O(n) * O(log n) => O(n log n)
    while True:
        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

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

문제

문제

동적계획법(Dynamic Programming)

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

동적계획법 적용 예 - 피보나치 수열, Knapsack Problem

• 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), f(1), f(2) = f(1) + f(0), f(3) = f(2) + f(1)...
• Knapsack 문제 : 가장 높은 값을 가지도록 물건들을 골라 배낭에 담음

풀이

동적계획법을 활용하여 N을 1, 2, 3,... 번 사용해서 만들 수 있는 수를 찾음

• N = 5
• 1번 : 5
• 2번 : 55, 1번 +-*/ 1번
• 3번 : 555, 2번 +-*/ 1번, 1번 +-*/ 2번
• ...
• 일반화, N = x : "x" * n, 1번 +-*/ n-1번, 2번 +-*/ n-2번,..., n-1번 +-*/ 1번

알고리즘의 복잡도

• 숫자를 1번 사용하면 결과는 총 1개
• 숫자를 2번 사용하면 결과는 총 5개
• ... 숫자를 8번 사용하면 결과는 총 11,853,949개
• 이처럼 결과의 개수가 엄청난 속도로 증가함
• 그러나 실제로 만들어지는 결과의 개수는 숫자를 8번 사용했을 때, 겹치는 수를 제외하면 10000개도 안됨

코드

def solution(N, number):
    s = [set() for x in range(8)] # [set()] * 8 (X)
    
    for i, x in enumerate(s, start=1)
        x.add(int(str(N) * i))
    
    for i in range(8):
        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를 활용

코드

• 최종 시간 복잡도 : O(n log n)

def solution(tickets):
    routes = {}
    
    # O(n)
    for t in tickets:
        routes[t[0]] = routes.get(t[0], []) + [t[1]]
        
    # O(n log n)
    for r in routes:
        routes[r].sort(reverse = True)
    
    stack = ["ICN"]
    path = []
    
    # O(n)
    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]

결론

느낀 점

• 코딩테스트 준비를 위해 다양한 알고리즘과 자료구조를 사용하는 방법들을 익혀야 함
• 힙, DP, DFS, BFS와 같은 필수적인 알고리즘을 적용하여 문제를 해결하는 노하우를 익혀야 함

어려웠던 점

• 개념 자체는 이해했다고 생각하지만, 코드로 구현하는 부분이 미숙하다고 생각함
• 특히 DP 문제의 풀이법을 떠올리기 어려웠고, 다양한 문제를 해결해 보는 과정이 필요하다고 생각

참고링크

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

https://velog.io/@chayezo/%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS-Depth-First-Search