21.12.10 TIL

알고리즘 문제 풀기 with Python

해쉬

해쉬 테이블 : 키값 매핑 구조, 해쉬 함수를 이용하여 데이터의 검색과 저장이 아주 빠르다 (O(1)), 파이썬의 딕셔너리
해쉬 함수 : 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬 값을 출력하는 함수

해쉬 테이블은 내부적으로 해쉬 함수를 통해 키를 임의의 해쉬 값으로 변환하여 인덱스로 사용한다. 그렇기 때문에 즉각적으로 데이터를 찾고 추가할 수 있는 것이다.

딕셔너리 구현하기

class Dict:
    def __init__(self):
        self.items = [None] * 8

    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index] = value

    def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index]


my_dict = Dict()

my_dict.put("A", 1)
my_dict.put("B", 2)
my_dict.put("C", 3)
my_dict.put("D", 4)
print(my_dict.get("C"))
print(my_dict.get("A"))

하지만 이 경우 동일한 나머지 값을 가지는 hash값에서 충돌이 발생한다.

Linked List로 충돌 해결하기 (chaining)

class LinkedTuple:
    def __init__(self):
        self.items = list()

    def add(self, key, value):
        self.items.append((key, value))

    def get(self, key):
        for k, v in self.items:
            if k == key:
                return v

class LinkedDict:
    def __init__(self):
        self.items = []
        for _ in range(8):
            self.items.append(LinkedTuple())

    def put(self, key, value):
        index = hash(key) % len(self.items)
        item = self.items[index]
        item.add(key, value)

    def get(self, key):
        index = hash(key) % len(self.items)
        item = self.items[index]
        return item.get(key)


my_dict = LinkedDict()

my_dict.put("A", 1)
my_dict.put("B", 2)
my_dict.put("C", 3)
my_dict.put("D", 4)
print(my_dict.get("C"))
print(my_dict.get("A"))

그 외에 그냥 남는 자리에 값을 집어넣는 개방주소법(Open Addressing)이 있다.

출석 체크

def get_absent_student(all_array, present_array):
    for student in all_array:
        if student not in present_array:
            return student

O(N)처럼 보일 수 있지만 not in에서 O(N)이므로 총 O(N^2) 시간 복잡도를 가진다.

all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]


def get_absent_student(all_array, present_array):
    my_dict = {}
    for student in all_array:
        my_dict[student] = True
    for student in present_array:
        del my_dict[student]
    for student in my_dict.keys():
        return student


print(get_absent_student(all_students, present_students))

해시 테이블을 사용하면 O(N)으로 효율적인 방법으로 해결할 수 있다.

---

연습문제

def get_melon_best_album(genre_array, play_array):
    genre_table = {}
    genre_index_table = {}
    for i in range(len(genre_array)):
        if genre_array[i] not in genre_table:
            genre_table[genre_array[i]] = play_array[i]
            genre_index_table[genre_array[i]] = [[i, play_array[i]]]
        else:
            genre_table[genre_array[i]] += play_array[i]
            genre_index_table[genre_array[i]].append([i, play_array[i]])

    result = []
    for genre, total_count in list(sorted(genre_table.items(), key=lambda item: item[1], reverse=True)):
        count = 0
        for index, cnt in sorted(genre_index_table[genre], key=lambda item: item[1], reverse=True):
           if count < 2:
               result.append(index)
               count += 1
           else:
               break

    return result


print("정답 = [4, 1, 3, 0] / 현재 풀이 값 = ",   get_melon_best_album(["classic", "pop", "classic", "classic", "pop"], [500, 600, 150, 800, 2500]))
print("정답 = [0, 6, 5, 2, 4, 1] / 현재 풀이 값 = ", get_melon_best_album(["hiphop", "classic", "pop", "classic", "classic", "pop", "hiphop"], [2000, 500, 600, 150, 800, 2500, 2000]))

그래프

연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조.

노드(Node): 연결 관계를 가진 각 데이터. 정점(Vertex)이라고도 한다.
간선(Edge): 노드 간의 관계를 표시한 선.
인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

그래프 표현 방법 두 가지

1. 인접 리스트
   시간 복잡도O(간선), 공간 복잡도 O(노드+간선)
2. 인접 행렬
   시간 복잡도O(1), 공간 복잡도 O(노드^2)

DFS & BFS

자료를 검색하거나 트리나 그래프를 탐색하는 방법

"끝까지 탐색하면" DFS
"모든 정점들을 우선 방문" BFS

이분 탐색 같이 정렬된 데이터에서 하나의 값을 찾는 효율적인 방법이 있는 것 처럼
모든 경우의 수를 탐색할 때의 효적인 방법이 있을 것이다.

DFS 와 BFS 는 그 탐색하는 순서에 차이가 있다.
DFS 는 끝까지 파고드는 것이고, BFS 는 갈라진 모든 경우의 수를 탐색해보고 오는 것.

DFS는 최대 깊이만의 공간만 요구하기 때문에 비교적 공간은 적게 사용하지만 최단 경로를 찾기 어렵다.
BFS는 모든 경로를 다 보기 때문에 최단 경로를 쉽게 찾을 수 있지만 공간을 많이 사용하고 시간이 오래걸린다.

DFS 구현하기 - 재귀함수

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = []


def dfs_recursion(adjacent_graph, cur_node, visited_array):
    visited_array.append(cur_node)
    for node in adjacent_graph[cur_node]:
        if node in visited_array:
            continue
        else:
            dfs_recursion(adjacent_graph, node, visited_array)
    return


dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

재귀함수는 노드의 깊이가 크다면 에러가 발생할 수 있다.

DFS 구현하기 - 스택

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}


def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]
    visited = []

    while stack:
        cur_node = stack.pop()
        visited.append(cur_node)
        for node in adjacent_graph[cur_node]:
            if node not in visited:
                stack.append(node)
    return visited


print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!

현재 인접한 노드 중에서 방문하지 않은 노드들을 저장하고 마지막에 넣은 노드만 꺼내서 탐색하는 방식이 필요하기 때문에 스택이 적절했다.

반대로 BFS같은 경우는 현재 인접한 노드 중에서 방문하지 않은 노드들을 저장하고 처음에 넣은 노드를 꺼내서 탐색해야 하므로 큐가 적절할 것이다.

BFS 구현하기 - 큐

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
from collections import deque

graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}


def bfs_queue(adj_graph, start_node):
    queue = deque()
    queue.append(start_node)
    visited = []

    while queue:
        cur_node = queue.popleft()
        visited.append(cur_node)

        for node in adj_graph[cur_node]:
            if node not in visited:
                queue.append(node)

    return visited


print(bfs_queue(graph, 1))  # 1 이 시작노드입니다!
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

동적 계획법 (Dynamic Programming)

피보나치 수열
1 1 2 3 5 8 13 21 34 ...
Fibo(n) = Fibo(n-1) + Fibo(n-2)

재귀함수로 구현하기

input = 20


def fibo_recursion(n):
    if n == 1 or n == 2:
        return 1
    return fibo_recursion(n-1) + fibo_recursion(n-2)


print(fibo_recursion(input))  # 6765

별다른 문제 없어보이지만 입력값이 높아질수록 굉장히 오래걸린다.
위의 로직은 결과가 동일한 연산을 여러번 호출하고 계산하는 비효율적인 과정이 있다.

Fibo(N-1) : 1번 수행
Fibo(N-2) : 2번 수행
Fibo(N-3) : 3번 수행
Fibo(N-4) : 3번 수행
...

이 부분을 줄이기 위해 동적 계획법을 사용할 수 있다.

동적 계획법(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
동적 계획법은 여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘.

재귀 알고리즘과 유사하지만 그 결과를 기록하고 이용한다는 점이 다르다.
결과를 기록하는 것을 메모이제이션(Memoization) 이라고 하고,
문제를 쪼갤 수 있는 구조를 겹치는 부분 문제(Overlapping Subproblem)라고 한다.

겹치는 부분 문제일 경우 동적 계획법을 사용하면 되는데, 이 때 사용하는 방법이 메모이제이션인 것.

동적계획법으로 피보나치 수열 구현

Top Down

input = 50

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
    1: 1,
    2: 1
}


def fibo_dynamic_programming(n, fibo_memo):
    for index in range(3, n+1):
        fibo_memo[index] = fibo_memo[index-1] + fibo_memo[index-2]
    return fibo_memo[n]


print(fibo_dynamic_programming(input, memo))

Bottom Up

input = 100

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
    1: 1,
    2: 1
}


def fibo_dynamic_programming(n, fibo_memo):
    if n in fibo_memo.keys():
        return fibo_memo[n]
    else:
        fibo_memo_n = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
        fibo_memo[n] = fibo_memo_n
        return fibo_memo_n



print(fibo_dynamic_programming(input, memo))

---

*힙 연습문제 *

import heapq

def get_minimum_count_of_overseas_supply(stock, dates, supplies, k):
    max_heap = []

    index = 0
    count = 0
    while stock < k:
        while index < len(dates) and dates[index] <= stock:
            heapq.heappush(max_heap, supplies[index] * -1)
            index += 1

        stock += heapq.heappop(max_heap) * -1
        count += 1
    return count

print("정답 = 2 / 현재 풀이 값 = ", get_minimum_count_of_overseas_supply(4, [4, 10, 15], [20, 5, 10], 30))
print("정답 = 4 / 현재 풀이 값 = ", get_minimum_count_of_overseas_supply(4, [4, 10, 15, 20], [20, 5, 10, 5], 40))
print("정답 = 1 / 현재 풀이 값 = ", get_minimum_count_of_overseas_supply(2, [1, 10], [10, 100], 11))
print("정답 = 3 / 현재 풀이 값 = ", get_minimum_count_of_overseas_supply(2, [1, 7, 28], [5, 22, 2], 30))