자료구조 & 알고리즘(문제 풀이 포함) - 5

힙(Heap)

- 힙(heap)은 데이터를 저장하고 조작하는 데 사용되는 트리 기반 자료구조

- 일반적으로 힙은 완전 이진트리(complete binary tree)를 기반으로 하며, 부모 노드와 자식 노드 간의 대소 관계가 있다.

- 최소 힙(min heap)은 부모 노드가 항상 자식 노드보다 작거나 같은 값을 가지는 힙을 말하며,

- 최대 힙(max heap)은 부모 노드가 항상 자식 노드보다 크거나 같은 값을 가지는 힙을 말한다.

 

문제 1) 프로그래머스 - 더 맵게

# heapq는 파이썬의 내장 라이브러리 중 하나로, 힙(heap) 자료구조를 제공하는 모듈
# heapq 모듈은 리스트(list)를 힙 자료구조로 변환하고, 힙의 원소를 삽입하고 삭제하는 함수들을 제공한다.
# heappush 함수는 힙에 원소를 삽입하고, heappop 함수는 힙에서 원소를 삭제하며,
# heappushpop 함수는 원소를 삽입하고, 동시에 최소 원소를 삭제한다.

import heapq

def solution(scoville, K):
    answer = 0
    # 주어진 리스트 scoville을 최소 힙으로 변환
    heapq.heapify(scoville)
    
    while True:
        # 최소값(min1)을 힙에서 삭제
        min1 = heapq.heappop(scoville)
        if min1 >= K:
            # 최소값이 K 이상인 경우, 반복문을 종료
            break
        elif len(scoville) == 0:
            # 스코빌 지수를 만들 수 없는 경우, answer 값을 -1로 설정하고 반복문을 종료
            answer = -1
            break
        # 두 번째로 작은 값을 힙에서 삭제
        min2 = heapq.heappop(scoville)
        # 새로운 스코빌 지수를 계산하여 힙에 추가
        new_min = min1 + (min2 * 2)
        heapq.heappush(scoville, new_min)
        answer += 1
        
    # 최소 횟수(answer)를 반환
    return answer

이 알고리즘의 시간복잡도는 O(nlogn)
heapq.heapify 함수는 리스트를 최소 힙으로 변환하는 데 O(n)의 시간이 소요
heappop 함수와 heappush 함수는 각각 O(logn)
while 반복문의 시간복잡도는 O(klogn)
최종적으로, 이 알고리즘의 시간복잡도는 O(nlogn + klogn) = O((n+k) logn)

---

깊이/너비 우선 탐색(DFS/BFS)

- 그래프(Graph): 노드(Node)와 노드 간의 연결(Edge)을 사용하여 데이터를 표현하는 자료구조
- 스택(Stack): 가장 마지막에 추가된 데이터를 가장 먼저 꺼내게 되는 후입선출(LIFO, Last In First Out)의 원리를 따르는 자료구조
- 큐(Queue): 가장 먼저 추가된 데이터를 가장 먼저 꺼내게 되는 선입선출(FIFO, First In First Out)의 원리를 따르는 자료구조

- 깊이 우선 탐색(Depth First Search): 그래프의 모든 노드를 한 번씩 방문하는 알고리즘 중 하나, 깊은 부분을 우선적으로 탐색

* 스택(Stack) 자료구조를 활용하여 구현 가능

- 넓이 우선 탐색(Breadth First Search): 그래프의 모든 노드를 한 번씩 방문하는 알고리즘 중 하나, 넓은 부분을 우선적으로 탐색

* 큐(Queue) 자료구조를 활용하여 구현 가능

출처 - https://hudi.blog/dfs-bfs/

 

문제 2) 프로그래머스 - 여행경로

def solution(tickets):
    # 딕셔너리 routes를 초기화
    routes = {}
    # 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 딕셔너리에서 제거
            routes[top] = routes[top][:-1]

    # 경로 리스트를 역순으로 정렬하여 최종 경로를 반환
    return path[::-1]

시간 복잡도는 주어진 항공권 수를 n이라고 할 때, O(n log n)
티켓 정보를 딕셔너리 routes에 추가하는 부분은 티켓 수만큼 수행되므로 O(n)
routes 딕셔너리의 값(리스트)을 정렬하는 부분은 출발점 수만큼 수행되므로 O(n log n)
스택을 이용한 경로 탐색은 티켓 수 n과 경로 길이 m에 따라 O(n+m)

---

동적계획법(Dynamic Programming)

- 큰 문제를 작은 문제로 쪼개어 푸는 알고리즘 기법

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

 

1) 알고리즘 적용 예시

- 피보나치수열: 0과 1로 시작하여, 이전의 두 수를 더해 다음 수를 만들어가는 수열

ex)  0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,... 와 같은 형태

출처 - https://hongjw1938.tistory.com/47

 

문제 3) 프로그래머스 - N으로 표현

def solution(N, number):
    # 각 연산 횟수에 해당하는 집합을 담은 리스트를 생성 최대 연산 횟수는 8
    s = [set() for _ in range(8)]

    # N을 여러 번 반복한 값을 각 집합에 추가
    for idx, x in enumerate(s, start=1):
        x.add(int(str(N) * idx))

    # 각 집합에 대해 가능한 모든 조합의 연산을 수행
    for i in range(len(s)):
        # i번째 집합에 대해 가능한 모든 조합을 계산
        for j in range(i):
            # j번째 집합과 i-j-1번째 집합에 있는 모든 원소의 조합을 계산
            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
    # for-else 구문: for 문이 완전히 실행된 후 else 문이 실행
    # 즉, 목표 숫자를 찾지 못한 경우 -1을 반환
    else:
        answer = -1

    return answer

---

어려웠던 점

- 알고리즘을 응용해서 적용하는 부분

- 동적계획법의 개념과 응용되는 피보나치 수열 이론