마이 자료구조/알고리즘 다이어리

💡 자료구조와 알고리즘에 대해 고민해보고 깨달은 것들을 내 언어로 정리해두는 공간

✍️ 혼자 공부하면서 고민한 결과를 그때 그때 기록해두기 위해 씁니다. 정확하지 않은 정보일 수 있습니다.

📝 시간 복잡도 따질 때 $n=2^k$ 해도 되는 이유

점근적 관점에서 수행 시간 분석할 때는 $2^{k}$ 나 $n$이나 $2n$이나 같기 때문. 샌드위치 정리.

👩‍👩‍👧‍👦 정렬 알고리즘 족보

• 비교 정렬
  • $O(n^2)$
    • 선택 정렬 (Selection Sort)
    • 버블 정렬 (Bubble Sort)
    • 삽입 정렬 (Insertion Sort)
    • 퀵 정렬 (Quick Sort) 👉 그러나 평균적으로 $\Theta(n\log{n})$
  • $O(n\log{n})$
    • 병합 정렬 (Merge Sort)
    • 힙 정렬 (Heap Sort)
• 특수 정렬
  • 기수 정렬 (Radix Sort)
  • 계수 정렬 (Counting Sort)

🆚 선택 정렬 vs. 버블 정렬

두 알고리즘의 차이는 배열 내부 원소 위치를 바꾸는 작업의 횟수에 있다.

대소 비교 횟수를 기준으로 보면 두 알고리즘은 같다. 다만,

• 선택 정렬
  : 비교 다 해서 확실히 한 뒤 마지막에 원소 교환을 하냐
• 버블 정렬
  : 비교할 때마다 중간중간 원소 교환 하면서 가냐

의 차이.

그래서 선택 정렬은 아묻따 모든 케이스 같은 시간이 들고

버블 정렬은 중간중간 원소 교환이 먹히는 케이스가 들어오면 시간이 덜 들 수도 있는 것.
(👉 정렬이 얼추 되어있으면 + 알고리즘을 개량해 중간에 정렬을 완료할 수 있으면)

하지만 최악의 경우엔 당연히 중간중간 다 교환하면서 가는 게 비효율적이 되고.
(👉 정반대 순서로 정렬이 되어있으면)

어쨌든 원소 교환을 다르게 한다고 해도,
그건 어차피 해야 하는 대소 비교 하면서 추가 작업이 있거나 없거나의 관점이기 때문에,
수행 시간의 관점에선 최대 두 배일 뿐. 그래서 결국 시간 복잡도는 둘 다 $\Theta(n^2)$

하지만 표현식 자체는 다를 것이기 때문에 점근적 관점이 아닌 미시적인 레벨의 현실에서는 상술한 것처럼 차이가 생긴다.

⚖️ 정렬의 기본은 양자 비교

비교 정렬이 아닌 특수한 케이스를 제외하면,
일반적인 비교 정렬의 경우에는 두 값의 사이의 대소 비교 연산이 정렬 알고리즘에 있어 모든 작업의 토대가 되는 원소 작업이다.

비교 정렬 알고리즘이란 러프하게 말해서,
전체 배열 안에서 서로 다른 두 값끼리의 대소 비교를 여러 번 하되 알잘딱깔센 하는 것이니까.

문제에서 요구하는 정렬 방식을 모든 케이스에 대해 깔끔히 구현하는 게 쉽지 않다면,

정렬 알고리즘은 언어에 내장된 정렬 함수에 맡기고,
(👉 $\Theta(n\log{n})$의 수행 시간은 이 쪽에서 알아서 책임져 줄 것.)

배열 내부 객체들끼리의 대소 비교를 구현하는 방향으로 접근했을 때 오히려 간단하게 문제가 해결될 때가 있다.
(👉 현 상태로는 문제에서 요구하는 기준으로 양자 비교가 바로 안 되니까)

프로그래머스에 있는 정렬 파트 가장 큰 수 문제가 그 예시

def solution(numbers):
    return "".join(
        map(
            str, 
            sorted(
                map(
                    lambda n: Digit(n),
                    numbers
                ),
                reverse=True
            )
        )
    ).lstrip("0") or "0"

class Digit:
    def __init__(self, number: int):
        self.digit = str(number)
    def __lt__(self, another: "Digit") -> bool:
        return self.digit + another.digit < another.digit + self.digit
    def __gt__(self, another: "Digit") -> bool:
        return self.digit + another.digit > another.digit + self.digit
    def __str__(self) -> str:
        return self.digit

🆚 Heap: Sift Down vs. Sift Up

두 전략의 가장 큰 차이는 전체 작업의 빌딩 블록이 되는 원소 작업의 시간 복잡도가 다르다는 데 있다.

• Sift Down: 현재 노드에서 leaf까지의 거리(=level 차이)
• Sift Up: 현재 노드에서 root까지의 거리

그리고 임의의 데이터셋을 힙으로 만드는 전체 작업은,

• Sift Down 시,
  1. 순서 신경 쓰지 않고(들어온 순서대로) complete binary tree 만들고
  2. leaf를 제외한 내부 노드들에 대해, 아래에서 root까지 Sift Down 작업 실행
• Sift Up 시,
  1. 들어온 순서대로 힙의 leaf로 삽입하면서 트리를 키워나간다.
  2. 새로 들어온 leaf 노드마다 Sift Up 적용

여기서 결정적으로 힙은 complete binary tree이기 때문에 leaf가 많다.
(👉 $\frac{n}{2}$ or $\frac{n+1}{2}$: 대략 전체의 1/2 )

그러니 당연히 Sift Down이 유리한 것.
(👉 먼저 트리 구성 이후 Sift Down 할 때 leaf 노드에는 적용하지 않는다.)
(👉 원소 작업이 일어나는 전체 횟수가 훨씬 적다(절반 이하).)

• Heapify w/ Sift Down: $\Theta(n)$
• Heapify w/ Sift Up: $\Theta(n\log{n})$

*이미 한 번 힙이 된 다음에 순차적으로 값이 추가(삽입)되는 경우에는 두 방법 다 같다.
(👉 leaf로 넣든 root로 넣든 어차피 끝에서 끝까지의 거리는 같으니까)

Ref: https://leeminju531.tistory.com/33

🌈 태스크별 시간 복잡도 (간단)정리

📏 정렬: $\Theta(n\log{n})$

• 비교 정렬이 아닌 특이 케이스에선 $\Theta(n)$ 가능
  • 기수 정렬, 계수 정렬 등
• 퀵 정렬은 $\Theta(n^2)$ 이지만 대부분 케이스에서 $\Theta(n\log{n})$의 성능 보장

🫵 선택: $\Theta(n)$

• n개 중 i번째 작은/큰 원소 고르기
• Heapify하거나 퀵 정렬의 원소 분할 로직 응용
• 이미 구성된 힙으로부터는 상수 시간: $\Theta(i)$

🔍 검색: $\Theta(1)$ ~ $\Theta(\log{n})$

• BST
  • 삽입/검색/삭제 모두, $\Theta(d) \approx \Theta(\log{n})$
  • 트리의 균형이 중요! 👉 레드 블랙 트리, B-트리
• 해시 테이블
  • 저장과 검색 모두 상수 시간
  • 대신 Space Overhead에서 손해를 모두 본다
  • 적재율이 그리 높지 않을 때는 Open Addressing이 더 매력적
  • 어쨌든 적재율을 낮게 (Space Overhead 고려해서) 유지하는 게 핵심

🌐 그래프 - 모든 노드 방문: $\Theta(V+E)$

• DFS & BFS

🌐 그래프 - 최소 신장 트리: $O(E\log{V})$

• 프림 알고리즘 & 크루스칼 알고리즘
• 프림 알고리즘에서 힙 사용 안 하면 $O(V^2)$

🌐 그래프 - 위상 정렬: $\Theta(V+E)$

• DFS 응용

🌐 그래프 - 최단 경로: $O(E\log{V})$

• 다익스트라 알고리즘: $O(E\log{V})$
  • 음의 가중치 허용 X
  • 프림 알고리즘과 유사 👉 힙으로 최소 비용 관리
• 벨만-포드 알고리즘: $O(VE)$
  • 음의 가중치 허용
• 플로이드-워샬 알고리즘: $O(V^3)$
• DAG에서 최단 경로: $\Theta(V+E)$
  • 위상 정렬 응용

🌐 그래프 - 강연결 요소 찾기: $\Theta(V+E)$

• DFS 응용

🌎 이론적 시간 복잡도 vs. 실제로 걸리는 시간

개발하는 모든 프로그램은 어찌 됐든 프로그래밍 언어를 통해 작성되고 실행된다.

그래서 프로그램의 이론적인 시간 복잡도 외에도
언어 레벨의 구현에 따른 다양한 기본 작업들의 실제 수행 시간이 언제나 변수가 되어
전체 프로그램의 실제 수행 시간을 결정한다.

from itertools import combinations
from math import sqrt

def is_prime(n):
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def solution(nums):
    return len(list(filter(lambda comb: is_prime(sum(comb)), combinations(nums, 3))))

예시로 위와 같은 프로그래머스의 소수 만들기 문제 풀이의 경우,
filter 제너레이터의 길이를 구하는 문제로 귀결하는데

파이썬 빌트인 len()이 CPython 구현이기 때문에
제너레이터를 순회하면서 변수에 +1씩 해서 길이를 구하는 것보다,
후에 len()을 사용하기 위해 한 번 순회하면서 리스트 안에 먼저 담고 전체 길이를 한 번에 구하는 방식이 속도 면에선 장점이 있다.

즉,

• 순회하면서 변수에 +1
• 순회하면서 리스트에 담고 한번에 len()

의 두 가지 선택지가 이론적인 시간 복잡도 측면에선 같지만,
두 번째 옵션이 수행할 기본 작업의 선택 측면에서 현실의 수행 시간에는 이점이 있다는 것.

하지만 제너레이터를 리스트로 변환하는 방식은 대신 공간 복잡도에 부하를 주는 방식이고 일반적으로 추천되는 방식은 아니다.
그리고 len()이 가져다 주는 속도적 이점도 크리티컬한 수준은 아님.

list comprehension이 for문에 비해 속도적 이점을 갖는 것도 비슷한 맥락이겠고

어찌 됐든 이런 점을 숙지하고 사용하는 언어의 내부 구현을 많이 파악해 놓는다면
프로그래밍하는 데 있어 제어할 수 없는 요소를 최대한 배제할 수 있겠다.

Ref: https://frhyme.github.io/python/python_length_of_generator/

👨‍👧‍👦 BFS와 프림 & 다익스트라 알고리즘

프림 알고리즘과 다익스트라 알고리즘은 둘 다 본질적으론 BFS 알고리즘이라고 볼 수 있다.

다만,

• BFS에선 기본적으로 모든 노드가 동등해 Breadth-first한 순서로 차근차근 진행되지만,
• 두 알고리즘은 매 방문마다 최소 비용인 노드를 따져 그 순서대로 진행이 되어야한다는 점이 다르다.

이처럼 다른 상황에 다른 태스크를 수행하긴 하지만 결국 두 알고리즘은 다음과 같은 뼈대를 BFS와 공유한다.

한 노드씩 거치면서 인접 노드들을 순회한다

• BFS
  : 한 노드씩 순회하면서 인접 노드들 순회해 방문 처리
• 프림 & 다익스트라
  : 한 노드씩 방문하면서 인접 노드들 순회해 비용 업데이트

정리하자면 위와 같이

• 한 노드씩 거쳐갈 때 처리하는 작업
  • BFS: 단순 순회
  • 프림 & 다익스트라: 방문 처리
• 인접 노드들을 순회하며 처리하는 작업
  • BFS: 방문 처리
  • 프림 & 다익스트라: 비용 업데이트

에서 서로 다르다.

그리고 한 노드씩 거칠 때 다음 노드를 선택하는 순서가 다른데,

• BFS의 기준은 Breadth-first, 같은 breadth 레벨에선 단순히 큐에 들어온 순서대로
• 프림 & 다익스트라는 다음 노드를 선택할 때마다 그 당시 최소 비용인 순서대로 모든 노드를 한 번씩 거쳐간다.

💲 프림 & 다익스트라 알고리즘에서 힙으로 비용 관리하기

두 알고리즘 모두 최적의 시간 복잡도를 달성하려면 최소 힙을 사용해 비용을 관리해야 한다는 조건이 있다.

하지만 의사 코드 수준에서 두 알고리즘의 비용을 관리하는 방식은 보통 다음과 같이 표현된다.

1. 모든 노드에 대해 비용 $\infin$으로 초기화
2. 시작 노드는 비용 0으로 변경 후 모든 노드 순회 시작
3. 순회 시 방문하게 되는 노드마다,
   인접 노드들 순회하면서 조건 만족하면 간선 가중치 적용해서 해당 노드 비용 업데이트
4. 아직 방문하지 않은 노드 중 현재 최소 비용인 노드를 다음 방문 노드로 선택

그리고 위와 같이 모든 노드들에 대해 비용을 수정하면서 동시에 힙도 사용해야 한다고 생각하면 문제가 발생한다.

• 비용을 수정하기 위해 매번 힙 내부에서 해당 노드를 탐색해야 한다.
  : 해당 노드 비용이 최소 비용이란 보장이 당연히 없기 때문
• 중간 노드일 수 있는 노들들의 비용을 수정하면 다음 최소 비용 반환을 위해 다시 heapify 해줘야 한다.

결국 루트가 아닌 중간 노드에 계속 접근해서 수정 작업을 해줘야 하는 상황으로 인해 힙의 장점은 사라지게 되고,
오히려 딕셔너리로 관리하면서 매번 최솟값을 구하는 방식보다 시간 복잡도에서 손해가 된다.

이제 여기서 문제의 발단을 살펴보면,
이미 알고 있는 노드의 비용을 힙 내부에서 수정해야 하는 상황인데,

비용 업데이트가 일어날 때,

• 힙에는 새로운 비용을 삽입 (기존 비용이 있다면 내부에 그대로 존재)
• 현재 노드별 비용을 기록하는 딕셔너리를 따로 두고 거기서 최신 비용 수정

하는 식으로 나눠서 접근하면 힙의 장점을 활용하는 비용 관리가 가능하다.

import heapq
from math import inf

def dijkstra(
    start: int, graph: list[list[int, float]]
) -> tuple[dict[int, float], dict[int, int]]:
    # init
    visited = []
    costs_book = {node: inf for node in range(len(graph))}
    costs_book[start] = 0
    costs_heap = [(0, start)]
    back_tracks = {}

    while costs_heap:  # until all nodes are visited
        # pop next node
        curr_cost, curr_node = heapq.heappop(costs_heap)  # greedy
        if curr_node in visited:  # only nodes not visited
            continue

        # update neighbors
        visited.append(curr_node)
        for nghbr_node, weight in filter(None, enumerate(graph[curr_node])):
            if (
                nghbr_node not in visited
                and curr_cost + weight < costs_book[nghbr_node]
            ):
                # cost update
                updated_cost = curr_cost + weight
                costs_book[start] = updated_cost
                heapq.heappush(costs_heap, updated_cost)

                # back track update
                back_tracks[nghbr_node] = curr_node

    return costs_book, back_tracks

프림과 다익스트라 알고리즘의 다음과 같은 세 가지 성질 때문에 위와 같은 구현이 가능하다.

1. 모든 노드는 비용 업데이트가 최소 한 번 보장된다.

1. 비용 업데이트가 일어나지 않을 노드는 어떤 노드에도 인접하지 않은 노드인데,
2. 그런 노드는 Spanning Tree에 포함될 수 없는 동시에 거기에 이르는 경로도 없기 때문에 두 알고리즘의 고려 대상이 아니다.
3. 따라서, 빈 상태로 시작해도 최소 비용 힙(costs_heap) 안에 모든 노드가 최소 한 번 들어간다.
4. 최소 비용 힙이 소진될 때까지 순회하면 모든 노드에 대한 방문이 보장된다.

2. 노드의 비용은 업데이트되면서 커질 일은 없다.

1. 노드의 비용을 업데이트하는 조건 자체가 기존의 비용보다 더 작아야 하기 때문
2. 따라서, 힙에 이미 존재하는 노드의 비용을 수정하는 대신 계속 삽입하며 쌓는다고 해도 최솟값 반환을 수행해 나온 노드의 비용은 그 노드의 최신 비용임이 보장된다.

3. 이미 방문한 노드는 다시 방문하지 않는다.

1. 힙에 같은 노드가 계속 쌓이는 문제는 최솟값 반환을 통해 알고리즘에서 원하는 올바른 방문 순서만 보장할 수 있다면 문제가 없다.
2. 만약 최솟값 반환해서 나온 노드가 아직 방문하지 않은 노드면, 앞서 언급했듯이 그 비용이 해당 노드의 최신 비용이기 때문에 문제가 없다.
3. 하지만 아직 방문하지 않은 노드들의 최소 비용보다 이미 방문했던 노드의 최소가 아닌 비용이 더 작아 이미 방문한 노드가 최솟값 반환 시 튀어나올 수가 있다.
4. 그럴 때 이미 방문한 노드라면 다시 최솟값 반환을 수행하도록 처리만 해주면 아직 방문하지 않은 노드들만 고려하는 올바른 방문 순서가 보장된다.

♻️ DFS와 파이썬의 재귀 깊이 제한

최근 코딩 테스트를 보던 중 DFS를 사용한 풀이가 로직에는 전혀 문제가 없는데 테스트 상황에서 런타임 에러가 나는 상황을 겪었다.

문제의 조건에 맞게 최대 크기의 테스트 케이스를 만들어 돌려보니 그제야 RecursionError가 발생하는 것을 확인할 수 있었다.

파이썬은 과도한 재귀 호출로 인한 스택 오버플로우를 방지하기 위해 최대 재귀 깊이를 정해두고 이를 초과할 시 RecursionError를 발생시킨다.

DFS는 재귀 호출을 이용하는 대표적인 알고리즘이고 그래서 큰 케이스를 만났을 때 최대 재귀 깊이를 넘는 호출이 일어났던 것이다.

이런 경우에는,

1. sys 모듈을 활용해 최대 재귀 깊이를 늘리거나

   >>> import sys
   >>> sys.setrecursionlimit(1e6)

2. 재귀 호출을 이터레이션으로 대체한다.

하지만 성능과 안정성에 따른 이유로 과도한 재귀 호출은 최대한 피하는 게 좋고 따라서 두 번째 방법으로 문제를 해결할 수 있으면 베스트.

👉 Ref: https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it

그리고 DFS의 경우,
특수한 용법이 아니라 단순히 모든 노드 방문이 목적이라면
간단히 같은 역할을 하지만 재귀 호출이 없는 BFS로 대체하면 쉽게 해결이 가능하다.