넌 과감해질 필요가 있어

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/aOhhNFTIeFI?si=H13MEVg0QIqqpAvE

서로소 집합 자료구조 Union-Find

서로소 집합 정의

서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.

서로소 집합 자료구조

서로소 부분 집합들로 나누어진 원소를 처리하기 위한 자료구조.

두 종류의 연산을 지원한다.

• 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
• 찾기(Find): 특정한 원소가 속한 집합(루트 노드)을 찾는 연산

이것을 `Union-Find 자료구조`라고도 부른다.

동작 과정

1. `Union 연산`으로, 노드 A와 노드 B를 연결한다.
   1. A와 B의 루트 노드 A'과 B'을 각각 찾는다. `Find 연산`
   2. A'를 B'의 부모 노드로 설정한다. (노드 번호가 작은 것이 부모가 되도록)
2. 입력된 모든 Union 연산을 처리할 때까지 1번의 과정을 반복한다.

연결성

1. 서로소 집합 자료구조에서는 손쉽게 집합의 형태로 연결 여부를 확인할 수 있다.
2. 기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없다.
   1. 오른쪽 그림의 예시에서는, 노드 3의 루트를 찾기 위해서 노드 2 -> 노드 1 순서로 접근해야 한다.

구현: 기본적인 형태

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
    if parent != x:
        return find_parent(parent, parent[x]) # 루트 찾을 때까지 재귀 호출
    return x
    
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
# 일반적인 문제 형태 ...
# 노드 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1)

# 부모 테이블을 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# Union 연산
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소가 속한 집합(루트 노드) 출력하기
for i in range(1, v + 1):
    print(find_parent(parent, i))

기본적인 구현 방법의 문제점

Union 연산이 편향되게 이루어 지는 경우 Find 연산이 비효율적으로 동작한다.

최악의 경우 Find 연산이 모든 노드를 다 확인해야 하므로 시간 복잡도가 O(V)이다.

이것을 개선하기 위해 `경로 압축`이 필요하다.

구현: 경로 압축

Find 연산을 최적화하기 위한 방법으로 경로 압축(Path Compression)을 이용할 수 있다.

Find 함수를 재귀적으로 호출한 뒤에, 부모 테이블 값을 바로 갱신한다.

def find_parent(parent, x):
    if parent != x:
        parent[x] = find_parent(parent, parent[x]) # 부모 테이블을 즉시 갱신
    return parent[x]

경로 압축의 과정에서, 각 Find 연산이 수행될 떄마다 경로 상의 모든 노드를 루트로 직접 연결하면서 트리의 높이를 평탄화한다.

(이때 부모 노드는 곧 루트 노드이다.)

경로 압축을 적용했을 때 Union-Find 연산의 시간 복잡도는 `O(α(N))`이다.

`α(x)`는 애커만 함수의 역함수이다.

애커만 함수는 재귀 함수의 일종으로 입력 값이 작더라도 매우 빠르게 증가한다.

반대로 역 애커만 함수는 x가 2^65536 일때 그 값이 4 ~ 5 정도이다. 거의 상수 시간이라고 할 수 있다.

아래 링크에 Union-Find 알고리즘의 형태별 시간 복잡도가 자세히 소개되어 있다.

https://velog.io/@nmrhtn7898/Union-Find

서로소 집합을 활용한 사이클 판별

트리 VS 그래프

정의

서로소 집합은 무방향 그래프(DAG) 내에서 사이클을 판별할 때 사용할 수 있다.

(방향 그래프에서의 사이클 여부는 DFS로 판별 가능)

동작 과정

1. 각 간선을 확인하면서 두 노드의 루트 노드를 확인.
   1. 루트 노드가 서로 다르다면 두 노드 Union 연산 수행.
   2. 루트 노드가 서로 같다면 Cycle 발생. 탐색 종료.
2. 그래프에 포함된 모든 간선에 대하여 1번 과정 반복

구현

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
    if parent != x:
        return find_parent(parent, parent[x]) # 루트 찾을 때까지 재귀 호출
    return x
    
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
# 일반적인 문제 형태 ...
# 노드 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1)

# 부모 테이블을 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

cycle = False # 사이클 발생 여부

for i in range(e):
    a, b = map(int, input().split())
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    else:
        union_parent(parent, a, b)

if cycle:
    print("사이클 발생")
else:
    print("사이클 발생하지 않음")

신장 트리 Spanning Tree

정의

모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

최소 신장 트리 MST, Minimum Spanning Tree

최소한의 비용으로 구성되는 신장 트리

크루스칼 알고리즘 Kruskal Algorithm

정의

최소한의 비용으로 만들 수 있는 최소 신장 트리를 찾는 알고리즘.

대표적인 최소 신장 트리 알고리즘.

그리디 알고리즘으로 분류.

동작 과정

1. 간선 데이터를 비용에 따라 오름차순으로 정렬
2. 간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 확인
   1. 사이클이 발생하지 않는 경우, 최소 신장 트리에 포함
   2. 사이클이 발생하는 경우, 최소 신장 트리에 포함하지 않음
3. 모든 간선에 대하여 2번의 과정을 반복

구현

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())
parent = [0] * (v + 1)

edges = [] # 모든 간선을 담을 리스트
result = 0 # 최종 비용

for i in range(1, v + 1):
    parent[i] = i

for _ in range(e):
    a, b, cost = map(int, input().split())
    edges,append((cost, a, b))

edges.sort() # 간선을 비용 순으로 정렬

for edge in edges:
    cost, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b): # 사이클이 발생하지 않는 경우 집합에 포함
        union_parent(parent, a, b)
        result += cost # 비용 더하기
        
print(result)

특징

간선의 개수가 E개일 때 `O(ElogE)`의 시간 복잡도를 갖는다.

가장 많은 시간을 요구하는 곳은 간선을 정렬하는 부분이다.

위상 정렬 Topological Sorting

정의

사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열.

순서가 정해져 있는 작업을 차례대로 수행해야 할 때, 그 순서를 결정하는 알고리즘이다.

예컨대, 라면을 끓이려면 물이 먼저 끓어야 한다. 특정 과목을 수강하려면 선수 과목을 수강해야 한다.

진입차수와 진출차수

진입차수: 특정한 노드로 들어오는 간선의 개수

진출차수: 특정한 노드에서 나가는 간선의 개수

동작 과정: 큐 (진입 차수)

1. 진입차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 텅 빌 때까지 다음의 과정을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
   2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
3. 결과적으로 각 노드가 큐에 들어온 순서가, 위상 정렬을 수행한 결과와 같다.

구현: 큐

from collections import deque

v, e = map(int, input().split())
indegree = [0] * (v + 1) # 모든 노드에 대한 진입차수는 0으로 초기화
graph = [[] for i in range(v + 1)] # 간선 정보를 담을 리스트

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b) # 노드 A에서 B로 이동 가능
    indegree[b] += 1

def queue_topological_sort():
    result = []
    q = deque()
    
    for i in range(1, v + 1):
        if indegree[i] == 0: # 진입차수가 0인 노드를 큐에 삽입
            q.append(i)

    while q:
        now = q.popleft()
        result.append(now)
        
        for i in graph[now]:
            indegree[i] -= 1 # 현재 노드와 연결된 노드의 진입 차수 1 빼기
            if indegree[i] == 0: # 새롭게 진입 차수 0이 된 노드 큐에 삽입
                q.append(i)

    for i in result:
        print(i, end=" ")

topological_sort()

동작 과정: 스택 (진출 차수)

1. 방문하지 않은 임의의 노드에서 출발한다.
2. DFS를 수행하며 방문하는 노드를 스택에 담는다.
3. 모든 정점을 방문할 때까지 1번을 반복한다.
4. 모든 정점을 방문했다면 스택에 담긴 정점을 출력한다.

DFS는 깊이 우선 탐색이라는 사실을 떠올려보자.

하나의 노드에서 DFS를 수행하면 결국 리프 노드까지 내려갈 것이다.

리프 노드는 진출 차수가 0이다.

즉, 가장 마지막에 수행되어야 하는 작업이다.

가장 깊은 리프 노드가 스택에 먼저 담기고,

루트 노드가 가장 나중에 스택 최상단에 담길 것이다.

LIFO 형태의 스택을 차례대로 출력하면 위상 정렬의 결과와 같다.

임의의 노드를 선택해도 상관이 없는 이유는,

DFS는 선택한 노드보다 늦게 수행되어야 할 노드(더 깊은 노드)만 방문하는 원리이다.

탐색 중인 그래프가 DAG인지 확인하기 위해 사이클 유무를 판단할 수 있어야 한다.

방문 처리된 노드를 DFS 호출 과정에서 만나면 사이클이 존재한다는 뜻이다.

구현: 스택

v, e = map(int, input().split())
graph = [[] for i in range(v + 1)] # 간선 정보를 담을 리스트
visited = [False] * (v + 1) # 방문 처리
stack = []

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b) # 노드 A에서 B로 이동 가능

def dfs(v):
	visited[v] = True
    
    for next in graph[v]:
    if not visited[next]:
        dfs(next)
    
    stack.append(v)

def stack_topological_sort():
    for i in range(1, v + 1):
        if not visited[i]:
            dfs(i)

    while stack:
        print(stack.pop(), end=" ")
        
stack_topological_sort()

위상 정렬 특징

시간 복잡도는 `O(V + E)`이다.

차례대로 모든 노드를 확인하며, 각 노드에서 나가는 간선을 차례대로 제거해야 한다.

위상 정렬은 DAG(Direct Acyclic Grpah, 방향이 있는 비순환 그래프)에 대해서만 수행 가능하다.

여러 가지 답이 존재할 수 있다.

같은 단계에 큐에 삽입되는 노드가 여러 개 있다면, 그들의 순서는 상관 없다.

모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.

사이클에 포함된 원소 중 어떤 원소도 큐에 삽입될 수 없다.

스택을 활용한 DFS로 위상 정렬을 수행할 수 있다.

참고

https://bigsong.tistory.com/33

https://velog.io/@nmrhtn7898/Union-Find

https://sorjfkrh5078.tistory.com/36

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/acqm9mM1P6o?si=paoazc7Qx2lqr39R

최단 경로 알고리즘

가장 짧은 경로를 찾는 알고리즘.

다양한 문제 상황이 있다.

1. 한 지점에서 다른 한 지점까지의 최단 경로
2. 한 지점에서 다른 모든 지점까지의 최단 경로
3. 모든 지점에서 다른 모든 지점까지의 최단 경로

각 지점은 그래프에서 노드로 표현한다.

지점 간 연결 도로는 그래프에서 간선으로 표현한다.

다익스트라 Dijkstra

요약

특정 노드에서 다른 모든 노드로 가는 최단 경로를 계산.

음의 간선이 없는, 현실 세계의 도로에서 정상적으로 동작.

그리디 알고리즘으로 분류.

매 상황에서 가장 비용이 적은 노드를 선택하여 과정을 반복하기 때문.

동작 과정

1. 출발 노드를 설정
2. 최단 거리 테이블을 최댓값(예컨대 INF)으로 초기화 (각 노드에 대한 현재까지의 최단 거리 정보를 갖고 있음)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 3번에서 선택한 노드를 거쳐, 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 모든 노드를 방문할 때까지 3번과 4번을 반복

구현1. 기본적인 다익스트라

INF = int(1e9) # 무한의 거리를 나타내기 위해 10억을 설정

n, m = map(int, input().split())
start = int(input()) # 시작 노드
graph = [[] for _ in range(n+1)] # 연결 정보 담는 리스트
visited = [False] * (n+1) # 방문 체크 리스트
distance = [INF] * (n+1) # 시작 노드부터 특정 노드까지의 최단 거리 테이블. INF로 초기화.

for _ in range(m): # 모든 간선 정보 입력
    a, b, c = map(int, input().split()) # a번 노드 -> b번 노드 (비용 c)
    graph[a].append((b, c))
    
def get_smallest_node(): # 방문하지 않은 노드 중, 최단 거리가 최소인 노드 반환
    min_value = INF
    index = 0 # 최단 거리가 최소인 노드의 인덱스
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]: # 현재 노드의 최단 거리보다 짧고 && 방문하지 않음
            min_value = distance[i]
            index = i
    
    return index
    
def dijkstra(start):
    distance[start] = 0 # 시작 노드부터 시작 노드까지의 최단 거리는 0으로 갱신
    visited[start] = True # 방문 처리
    
    for adjacent_node_of_start in graph[start]: # 시작 노드와 인접한 노드의 최단 거리 갱신
        distance[adjacent_node_of_start[0]] = adjacent_node_of_start[1]
        
    for i in range(n-1): # n-1인 이유. 시작 노드X. 마지막 노드X
        now = get_smallest_node() # 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드
        visited[now] = True # 방문 처리
        
        for adjacent_node in graph[now]: # 선택한 노드와 인접한 노드 확인
            cost = distance[now] + adjacent_node[1] # 시작~선택 + 선택~인접
            if cost < distance[adjacent_node[0]]: # cost가 시작~인접보다 작을 경우 갱신
                distance[adjacent_node[0]] = cost
                
dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("도달할 수 없는 신기루")
    else:
        print(distance[i])

1번 방법의 특징

O(V)번에 걸쳐서 get_smallest_node()를 호출하여, 매번 선형 탐색을 해야 한다.

따라서 전체 시간 복잡도는 O(V^2)이다.

python은 대략 1초에 20,000,000 연산이 가능하므로 노드 개수가 5,000 개면 간당간당하다.

우선순위 큐를 이용하여 개선이 필요하다.

잠시 자료 구조의 바다에 빠져보자.

풍덩 ~

우선순위 큐 Priority Queue

우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료 구조.

python은 표준 라이브러리 형태로 지원한다.

나의 이데아 swift는 지원하지 않는다. 함부로 다가갈 수 없는 매력이 있다.

힙 Heap

우선순위 큐를 구현하기 위해 필요한 자료 구조이다.

최소 힙(Min Heap)과 최대 힙(Max Heap)이 있다.

완전 이진 트리(complete binary tree)의 일종.

힙은 느슨한 정렬 상태를 유지한다.

부모 노드의 key(노드가 저장하는 값)가 자식 노드의 key보다 항상 작은-최소 힙(큰-최대 힙) 상태의 이진 트리.

이진 트리 binary tree

모든 노드가 둘 이하(0, 1, 2)의 자식을 가진 트리이다.

위 그림과 같이 다양한 종류가 있다.

많은 자료 구조를 만나고 왔다.

이진 트리 -> 완전 이진 트리 -> 힙 -> 우선 순위 큐 -> 개선된 다익스트라 알고리즘.

이렇듯 여러 단계를 거쳐 다익스트라를 개선시킬 수 있다.

핵심은 단계마다 방문하지 않은 노드 중에서, 시작 노드로부터 최단 거리가 가장 짧은 노드를 선택하기 위해 힙을 사용하는 것이다.

구현2. 개선된 다익스트라

import heapq

INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)
# 방문 처리 배열을 만들지 않는다. 단계마다 순차 탐색하는 것이 아니라 우선순위 큐에서 pop()하므로.

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) # 시작 노드 -> 시작 노드의 최단 거리는 0으로 갱신. 큐에 삽입.
    distance[start] = 0
    
    while q: # 큐가 텅텅 빌 때까지 반복
        dist, now = heapq.heappop() # 최단 거리(dist)를 기준으로 우선순위 큐에서 bubble pop

        if distance[now] < dist: # distance[now] == 현재까지 확정된 최소 거리, dist == 현재 탐색에서 최소 거리
            continue # 확정된 최소 거리가 더 짧으면, 이미 방문한 셈 치고 continue
        
        for adjacent_node in graph[now]:
            cost = dist + adjacent_node[1] # 현재 탐색에서, 탐색 중인 노드의 최소 거리 + 인접 노드의 최소 거리
            if cost < distance[adjacent_node[0]]: # cost가 인접 노드의 확정된 최소 거리보다 짧다면 갱신
                distance[adjacent_node[0]] = cost
                heapq.heappush(q, (cost, adjacent_node[0]])

dijkstra(start)

for i in ragne(1, n+1):
    if distance[i] == INF:
        print("영영 닿을 수 없음")
    else:
        print(distance[i])

개선된 방법의 특징

시간 복잡도는 O(ElogV)이다.

E는 Edge(간선), V는 Vertex(정점, 노드).

모든 노드를 검사하는 while문은 간선의 개수 E에 따라 실행 횟수가 결정된다.

왜 why? 간선의 개수만큼 큐에 넣으니까.

전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산(O(logN))과 유사하다.

E개의 원소에 대하여 O(logE)의 연산을 수행한다.

즉, 시간 복잡도는 O(ElogE)이다.

동시에 이것은 O(ElogV)와 같다.

왜 why? 실제 그래프에서 모든 노드가 서로 연결되어 있다면, 최대 간선 수는 V*(V-1)/2이다.

따라서 다음의 식이 성립한다.

O(ElogE) -> O(ElogV^2) -> O(2ElogV) -> O(ElogV)

플로이드-워셜 Floyd-Warshall

요약

모든 노드에서 다른 모든 노드로 가는 최단 경로를 모두 계산.

다익스트라와 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행.

단, 단계마다 방문하지 않는 노드 중 최단 거리 노드를 찾는 과정은 필요X (다익스트라에서 get_smallest_noe()로 수행했던 그것)

2차원 테이블에 최단 거리 정보를 저장.

다이나믹 프로그래밍 유형에 속함.

동작 과정

1. 2차원 최단 거리 테이블을 최댓값(예컨대 INF)으로 초기화
2. 각 단계마다 특정한 노드 k를 거쳐가는 경우를 확인
   1.  a -> b 최단 거리보다, a -> k  + k -> b가 더 짧은지 검사
   2. 점화식(D는 거리): Dab = min(Dab, Dak + Dkb)
3. 모든 노드를 방문할 때까지 2번을 반복

구현: 플로이드 워셜

INF = int(1e9)

n, m = map(int, input().split()) # n은 노드의 개수, m은 간선의 개수
graph = [[INF] * (n + 1) for _ in range(n + 1)] # 최단 거리 정보를 저장할 2차원 리스트 INF로 초기화

for a in range(1, n+1): # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0
            
for _ in range(m): # 각 간선에 대한 정보를 입력 받아, 최단 거리 테이블 갱신
    a, b, c = map(int, input().split())
    graph[a][b] = c # a에서 b로 가는 비용을 c라고 설정
    
for k in range(1, n+1): # 점화식에 따라 플-워 수행
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print("INFINITY", end = " ")
        else:
            print(graph[a][b], end = " ")
    print()

플로이드 워셜의 특징

노드의 개수가 N개일 때 알고리즘을 N번 수행한다.

각 단계마다 O(N^2)의 연산을 통해, 현재 선택된 노드를 거쳐 가는 모든 경로를 고려한다.

따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)이다.

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/5Lu34WIx2Us?si=OJpwTfcdclJ1HMaq

다이나믹 프로그래밍 Dynamic Programming

요약

다이나믹 프로그래밍(DP)은 동적 계획법이라고도 부른다.

메모리를 사용하여, 처리 시간을 단축하는 방법이다. 이를 메모이제이션(Memoization)이라고 한다.

조건

1. 최적 부분 구조 (Optimal Substructure)
   - 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제 (Overlapping Subproblem)
   - 동일한 작은 문제를 반복적으로 사용하여 해결해야 한다.

접근 방식

• 하향식(Top-Down): 큰 문제로 시작하여, 풀리지 않는 작은 문제를 만나면 재귀적으로 해결.
• 상향식(Bottom-Up ): 작은 문제를 모아서 큰 문제를 해결하는 방식.

Top-Down 접근 방식을 메모이제이션(Memoization)이라고도 부른다.

계산 결과를 메모리에 저장하여 중복 계산을 방지한다.

주로 재귀 함수를 반복적으로 호출하여 문제를 해결한다.

Bottom-Up 접근 방식은 타뷸레이션(Tabulation)이라고 한다.

테이블에 기록한다는 느낌.

주로 반복문으로 구현한다.

따라서 재귀 호출에 따른 오버헤드 혹은 스택 오버플로우 위험이 없다.

기본적으로 Bottom-Up으로 접근하는 것이 더 직관적이다.

일단 그렇게 하고, 막히면 Top-Down으로 풀이하자.

DP인지 어떻게 판단?

가장 중요한 문제이다.

1. 주어진 입력값의 범위가 너무 크면 의심해본다.
2. 완탐, 그리디로 풀리지 않으면 의심해본다.
3. 상술된 조건을 이용한다. (quick sort가 왜 DP가 아닌지 떠올리면 더 좋다. 최적 부분 구조는 맞지만, 중복되는 부분 문제는 없다.)

피보나치 수열을 DP로 구현

피보나치 수열이 뭔지는 생략하지 않지 않지 않겠다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

An = An-1 + An-2의 규칙을 반복하는 수열이다.

그림과 같은 방식으로 풀이하면, 중복 계산이 발생하여 지수 시간복잡도를 갖는다.

그래서 DP로 풀이하기 딱 좋은 유형이다.

f(6)을 구하기 위해, 작은 문제로 나눌 수 있다. 작은 문제를 합치면 f(6)을 구할 수 있다. (최적 부분 구조)

f(2)와 같이 작은 문제가 중복 계산되고 있다. (중복되는 부분 문제)

햐향식 Top-Down 접근

dp = [0] * 100 # 계산된 결과를 메모이제이션 하기 위한 리스트

def fibo(x):
    if x == 1 or x == 2:
        return 1
        
    if dp[x] != 0: # 이미 계산된 결과는 즉시 return. 중복 계산 방지. 상수 시간 소요.
        return dp[x]

    dp[x] = fibo(x - 1) + fibo(x - 2) # 새로운 문제는 재귀적으로 구함.
    return dp[x]

print(fibo(10)) # 55

상향식 Bottom-Up 접근

# 엥 이것도 메모이제이션 아니에요? 
# 동의하는 부분.. 다만 탑다운에서 이미 계산된 결과는 즉시 반환하는 등 명시적으로 다루고 있어서 구분 짓나 보다.
dp = [0] * 100

d[1] = 1
d[2] = 1

for i in range(3, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[10]) # 55

예제 1. 개미 전사

# DP인지 판단
# 최적 부분 구조가 가능한가?
    # 특정 구간의 최대 조합이 있을 것이다. 그것은 구간을 확장해도 조합이 바뀌지 않을 것이다.
# 중복되는 부분 문제가 있는가?
    # 특정 구간의 조합이 다음 구간에 영향을 주므로 (1칸 이상 떨어져야 함) 중복되는 문제가 있다고 보아야 한다.

# 메모이제이션 - 탑 다운으로 풀이해보자
# 배열의 크기가 1일 때는? a1
# 2일 때는? max(S1, a2)
# 3일 때는? max(S2, S1 + a3)
# 4일 때는? max(S3, S2 + a4)
# 5일 때는? max(S4, S3 + a5)
# 6일 때는? max(S5, S4 + a6)
# n일 때는? max(Sn-1, Sn-2 + an)
# S1 = arr[0]
# S2 = max(arr[1], arr[0])
# Sn = max(Sn-1, Sn-2 + an)

n = int(input())
arr = list(map(int, input().split()))
dp = [0] * 10
dp[0] = arr[0]
dp[1] = max(arr[0], arr[1])

def get_food(n):

    if dp[n] != 0:
        return dp[n]
    
    dp[n] = max(dp[n - 1], dp[n - 2] + arr[n])

    return dp[n]

print(get_food(n - 1))
print(dp)

예제 2. 1로 만들기

# 최적 부분 구조
    # 맞다. 특정 수를 만드는 최소 연산 회수는 정해져 있다.
# 중복되는 부분 문제
    # 맞다. 특정 수까지의 최소 연산 회수가 정해져 있으므로, 계산 과정에서 반복적으로 사용한다.

# 조건
# 5로 나눈다.
# 3으로 나눈다.
# 2로 나눈다.
# 1로 뺸다.

# 풀이
# 항상 큰 수로 나누는 것이 유리한가?
# 그렇지만, 순서의 차이는 있다. 16의 경우 16 -> 15 -> 3 -> 1 (3번) / 16 -> 8 -> 4 -> 2 -> 1 (4번)). 그리디처럼 풀이하는 것은 아니다.
# 반대로 1부터 dp 테이블 해당 인덱스를 구하기 위한 최소 연산 회수로 채워가는 것은 어떤가?
# [0, 1, 2, 3, 4, 5, 6, 7, ...]
# [0, 0, 1, 1, 2, 1, 2, 3, ...]

# 7을 살펴보자. 다음과 같은 방법으로 만들 수 있다.
# 6 + 1
# 6을 살펴보자.
# 5 + 1, 3 * 2, 2 * 3
# 10을 살펴보자.
# 9 + 1, 5 * 2, 2 * 5
# Sn = min(Sn-1 + 1, Sn//5 + 1, Sn//3 + 1, Sn//2 + 1)이다.
# if n이 어떤 수로 나누어 떨어지느냐에 따라 if 조건문으로 나누면 풀이할 수 있을 것이다.

# n = 1 return 1
# n = 2 return 1
# n = 3 return 1
# n = 5 return 1

# if n % 5 == 0
    # min(Sn-1 + 1, Sn//5 + 1)
# elif n % 3 == 0
    # min(Sn-1 + 1, Sn//3 + 1)
# elif n % 2 == 0
    # min(Sn-1 + 1, Sn//2 + 1)
# else
    # Sn-1 + 1

n = int(input())

dp = [0] * 30001
dp[0] = 0
dp[1] = 0
dp[2] = 1
dp[3] = 1
dp[5] = 1

for i in range(4, n + 1):
    dp[i] = dp[i-1] + 1
    if i % 5 == 0:
        dp[i] = min(dp[i], dp[i//5] + 1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)

print(dp[n])

예제 3. 효율적인 화폐 구성

# 최적 부분 구조
    # 맞다. 특정 값을 구성하기 위한 최소 화폐 개수는 정해져 있다.
# 중복되는 부분 문제
    # 해당 구조가 여러 번 반복된다.


# 풀이
# 무조건 고액 화폐를 많이 사용하는 것이 옳은가?
# 그렇지 않다. 700을 고려해보자. 300 + 300 + ...? / 300 + 200 + 200
# 1로 만들기 문제처럼, 100부터 목표 값까지 최소 화폐 개수를 채워나가보자.
# coins = [200, 300]
# [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
# [  0,   1,   1,   2,   2,   2,   3,   3,   3,    4]
# 쉬운 듯?
# min(Sn-300 + 1, Sn-200 + 1)

# if 조건문으로 모든 케이스를 검증하며 풀이해보자. 아니다. 조건문조차 필요가 없다.
# dp = [0] * 10001

# for coin in coins:
# dp[coin] = 1

# for i in range(min(coins), m + 1)
    # for coin in coins:
        # if i > coin:
            # dp[i] = min(dp[i], dp[i - coin] + 1)

# -1 if dp[m] == 1 else dp[m]


n, m = map(int, input().split())
coins = [int(input()) for _ in range(n)]

dp = [10001] * (m + 1)
dp[0] = 0

for i in range(n): # 화폐 단위
    for j in range(coins[i], m+1): # 목표 금액
        if dp[j - coins[i]] != 10001:
            dp[j] = min(dp[j], dp[j-coins[i]] + 1)

if dp[m] == 10001:
    print(-1)
else:
    print(dp[m])

예제 4. 금광

# 최적 부분 구조
    # 맞다. 전체의 문제를 한 열씩 나눠서 판단할 수 있다. 
    # 특정 구간 최적 경로는 전체 구간에서 봐도 그렇다.
# 중복되는 부분 문제
    # 하나의 최적 경로를 구하는 문제이므로, 같은 구간이 중복되어 계산된다.

# 풀이
# 무작정 3방향 중 최대값을 선택하면 되는가?
# 안 된다. 그건 그리디이다. 이동 범위 밖에 있는 최적 경로가 존재할 수 있다.

# 전체 행에서 최대값을 선택하는 것도 불가능하다. 이동이 불가능할 수도 있으므로.

# 2차원 배열을 탐색하며 이전 3방향의 최대값을 더해주는 방식으로 배열을 갱신해야겠다.
# 현재 인덱스의 값은, 이전 3방향 값 중 최대값을 더한 값이다.
# 즉, 다음과 같다.
# dp[i][j] = dp[i - 1][j] +  matrix[i][j-1]
# if i > 0:
# dp[i][j] = max(dp[i][j], dp[i-1][j-1] + matrix[i][j])
# if i + 1 < n 
# dp[i][j] = max(dp[i][j], dp[i+1][j-1] + matrix[i][j])


tc = int(input())

for k in range(tc):
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))

    matrix = []
    for i in range(0, len(arr), m):
        matrix.append(arr[i : i + m])

    dp = [[0] * m for _ in range(n)]
    for i in range(n):
        dp[i][0] = matrix[i][0]

    for j in range(1, m):
        for i in range(n):
            if i == 0:
                left_up = 0
            else:
                left_up = dp[i - 1][j - 1]
            
            if i == n - 1:
                left_down = 0
            else:
                left_down = dp[i + 1][j - 1]
            
            left = dp[i][j - 1]
            dp[i][j] = matrix[i][j] + max(left_up, left, left_down) # 2차원 탐색 문제는 이렇게

    result = 0
    for i in range(n):
        result = max(result, dp[i][m-1])
    
    print(result)

예제 5. 병사 배치하기

# 최적 부분 구조
    # 나눠서 풀 수 있는가?
    # 연속되는 구간 별로 나눠서 특정 병사를 제외했을 때, 그것이 최선이 되는가?
    # 직관적으로 생각나지는 않지만, 딱히 반례가 떠오르는 것도 아니다.

# 중복되는 부분 문제
    # 하나의 최적 배열을 구하는 것이므로, 부분 문제가 중복된다고 할 수 있다.

# 풀이
# 최장 연속 부분 수열? 그런 유형인 듯하다.
# 내림차순이 성립하지 않는 모든 수만 제거하면 되는가? 그럼 문제가 발생한다.
# [15 11 2 10 9] 이런 배열이 있다면 내림차순이 성립함에도 불구하고, 2를 제거하는 것이 옳다.
# [9 8 7 6 5 4 3 2 10 5 9 8 7] 이런 경우에는 4 3 2 5를 제거해야 한다.


n = int(input())
arr = list(map(int, input().split()))
arr.reverse()

dp = [1] * n

for i in range(1, n):
    for j in range(0, i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(n - max(dp))

위 문제는 가장 긴 연속하는 부분 수열(Longest Increasing Subsequence, LIS) 유형이다.

LIS의 점화식은 다음과 같다.

# D[i] = array[i]를 마지막 원소로 포함하는, 부분 수열의 최대 길이
모든 0 ≤ j < i에 대하여, D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

모든 i에 대하여 0 ~ i 범위를 탐색하면서 비교하므로 시간복잡도는 O(N^2)이다.

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/94RC-DsGMLo?si=iDSiDtzOFIj_b1Ym

이진 탐색 binary search

요약

순차 탐색: 리스트 내 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인

이진 탐색: 정렬된 리스트 내에서, 탐색 범위를 절반씩 좁혀가며 데이터를 탐색

순서

• 리스트를 정렬한다.
• while start <= end인 동안 다음을 반복한다.
• start와 end의 중간점을 mid로 설정한다.
• mid와 구하고자 하는 값인 target을 비교한다.
• mid < target이면, 검색 범위를 높여야 한다. start = mid + 1로 설정해서 재귀적으로 이진 탐색한다.
• mid > target이면, 검색 범위를 낮춰야 한다. end = mid - 1로 설정해서 재귀적으로 이진 탐색한다.
• mid == target인 경우 mid 값을 반환한다.

파라메트릭 서치

파라메트릭 서치란 최적화 문제(특정한 조건을 만족하는 가장 알맞은 값을 찾는)를 결정 문제(예 혹은 아니오)로 바꾸어 해결하는 기법.

일반적으로 코테에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결 가능.

구현1: 재귀

def binary_search(array, target, start, end):
    if start > end:
        return None
    
    mid = (start + end) // 2
    
    if array[mid] == target:
        return mid
    
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    
    else: # array[mid] < target:
        return binary_search(array, target, mid + 1, end)

구현2: 반복문

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        
        if array[mid] == target:
            return mid
            
        elif array[mid] > target:
            end = mid - 1
        
        else: # array[mid] < target:
            start = mid + 1
    
    return None

구현3: 라이브러리

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x)) # 2
print(bisect_right(a, x)) # 4

시간 복잡도

매 단계에서 탐색 범위를 절반으로 줄여나가므로 탐색 횟수는 로그 스케일로 증가한다.

따라서 평균, 최악의 상황에서 O(logN)의 시간복잡도를 갖는다.

공간 복잡도

반복문 구현: O(1). 추가적인 저장 공간이 필요하지 않다.

재귀적 구현: O(logN). 재귀 호출로 인한 스택이 필요하다.

예제 1: 떡볶이 떡 만들기

n, m = map(int, input().split())
heights = list(map(int, input().split()))
result = 0

start = 0
end = max(heights)

while start <= end:
    
    total = 0
    mid = (start + end) // 2

    for hei in heights: # 기준치 보다 자르려는 떡의 긴 경우에만, 차이만큼 total에 더한다.
        if hei > mid:
            total += hei - mid

    if total < m: # 조건을 만족하지 못 하면, 기준치를 줄여, 남는 떡의 길이를 늘린다.
        end = mid - 1
    else: # 조건을 만족한 경우 result를 갱신한다. 기준치를 줄이고, 남는 떡의 길이를 늘려 최적값을 찾는다.
        result = mid
        start = mid + 1

print(result)

예제 2-1: 특정 수 개수: 일반

def count_by_value(array, x): # 정렬된 수열에서 값이 x인 원소의 개수를 세는 메서드
    n = len(array) # 데이터의 개수
    
    first_idx = first(array, x, 0, n-1) # x가 처음 등장한 인덱스
    if first_idx == None: # 수열에 x가 존재하지 않는 경우
        return 0 # 값이 X인 원소의 개수는 0개이므로 0 반환
    
    last_idx = last(array, x, 0, n-1) # x가 마지막으로 등장한 인덱스
    return last_idx - first_idx + 1


def first(array, target, start, end):
    if start > end:
        return None
    
    mid = (start + end) // 2

    # target == mid인 동시에, mid - 1은 target보다 작은 경우
    # 조건을 만족하는 가장 왼쪽에 있는 인덱스인 경우
    if target == array[mid] and (mid == 0 or target > array[mid - 1]):
        return mid
    
    elif target <= array[mid]:
        return first(array, target, start, mid - 1)
    
    else:
        return first(array, target, mid + 1, end)


def last(array, target, start, end):
    if start > end:
        return None
    
    mid = (start + end) // 2

    if array[mid] == target and (mid == 0 or array[mid + 1] > target):
        return mid
    
    elif array[mid] > target:
        return last(array, target, start, mid - 1)
    
    else:
        return last(array, target, mid + 1, end)


n, x = map(int, input().split())
array = list(map(int, input().split()))

count = count_by_value(array, x)
print(count if count > 0 else -1)

예제 2-2: 특정 수 개수: 라이브러리

from bisect import bisect_left, bisect_right

def get_count_by_bisect(array, x):
    left = bisect_left(array, x)
    right = bisect_right(array, x)
    return right - left

n, x = map(int, input().split())
array = list(map(int, input().split()))

count = get_count_by_bisect(array, x)

if count == 0:
    print(-1)
else:
    print(count)

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/KGyK-pNvWos?si=w2ozPGhJxDhH5aNy

레퍼런스: https://gyoogle.dev/blog/

정렬

데이터를 특정한 기준에 따라 순서대로 나열하는 것.

선택 정렬 selection sort

요약

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬 알고리즘.

각 탐색마다 결정될 자리를 먼저 선택하고, 자리에 올 값을 찾는 과정이라고 생각하면 좋다.

구현

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i # 최솟값의 인덱스, 최초에는 이번 탐색에서 결정될 인덱스로 초기화
    
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]: # 현재 인덱스보다 작은 값을 발견하면
            min_index = j # 최솟값의 인덱스를 갱신
    
    array[i], array[min_index] = array[min_index], array[i] # 탐색이 끝나면 스왑

print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 복잡도

N + (N - 1) + (N - 2) + ... + 2 # 마지막 원소는 이미 확정되었으므로 정렬을 하지 않아도 괜찮다.

데이터의 개수가 N개라고 했을 때,

• 첫 번째 탐색에서 비교횟수: 1 ... N-1 => N-1
• 두 번째 탐색에서 비교횟수: 2 ... N-1 => N-2
• ...
• (N-1) + (N-2) + .... + 2 => N(N-1) / 2 - 1

시간복잡도는 O(N^2)이다.

최선, 평균, 최악의 경우 모두 같다.

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해 수행되므로, O(N)이다.

특징

• 제자리 정렬 (in-place sorting)
• 불안정 정렬 (unstable sorting)

삽입 정렬 insertion sort

요약

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 정렬 알고리즘.

선택 정렬에 비해 구현 난도는 높지만, 일반적으로 더 효율적.

구현

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)): # 1번째 원소는 결정된 것으로 간주하고, 2번째 원소부터 정렬
    for j in range(i, 0, -1): # 삽입할 원소를, 역순으로 기존 원소와 비교하며 삽입 위치를 결정
        if array[j] < array[j-1]: # 현재 원소가 이전 원소보다 작은 경우
            array[j], array[j-1] = array[j-1], array[j] # 위치를 바꿈 # 이전 원소의 왼쪽으로
        else:
            break # 작지 않을 경우 해당 자리에서 멈춤

print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 복잡도

N + (N - 1) + (N - 2) + ... + 1 # 마지막 원소까지 정렬해야 함

최악, 평균의 경우: 선택 정렬과 마찬가지로 O(N^2)

최선의 경우: O(N)

이미 정렬이 되어 있을 경우, 한 번씩만 비교한다.

즉, 상수 시간이 소요된다.

전체 배열 탐색 + 탐색마다 한 번씩 비교만 하면 되므로 O(N)

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해 수행되므로, O(1)이다.

추가적인 메모리가 필요하지 않다.

특징

• 대부분의 원소가 정렬되어 있는 경우, 매우 효율적이다.
• 제자리 정렬 (in-place sorting)
• 안정 정렬 (stable sorting)

퀵 정렬 quick sort

요약

기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법.

분할 정복(divide and conquer) 방법을 사용한다.

병합 정렬과 더불어 대부분 언어의 기본 정렬 라이브러리의 근간이다.

구현1: 일반적인 방식

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return

    pivot = start # 첫 번째 원소를 피봇으로
    left = start + 1 # 왼쪽 포인터의 인덱스
    right = end # 오른쪽 포인터의 인덱스

    while left <= right:
        while left <= end and array[left] <= array[pivot]: # 왼쪽 출발. pivot보다 큰 값을 찾을 때까지.
            left += 1
        
        while right > start and array[right] >= array[pivot]: # 오른쪽 출발. pivot보다 작은 값을 찾을 때까지.
            right -= 1
        
        if left > right: # 포인터가 엇갈렸다면, 작은 값과 피봇 값을 교체
            array[right], array[pivot] = array[pivot], array[right]
        
        else: # 엇갈리지 않았다면, 각 포인터의 값을 교체
            array[left], array[right] = array[right], array[left]
    
    quick_sort(array, start, right - 1) # 분할divide 이후 각각 재귀적으로 정렬
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

구현2: pythonic한 방식

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    if len(array) <= 1: # 리스트 원소가 1개라면 재귀 끝 !
        return array
    
    pivot = array[0] # 첫 번째 원소를 피봇
    tail = array[1:] # 피봇을 제외하고 나머지 배열

    left_side = [x for x in tail if x <= pivot] # filter를 사용하듯, pivot 보다 작은 원소만
    right_side = [x for x in tail if x > pivot] # pivot 보다 큰 원소만

    # 재귀적으로 반복하면, left_side에는 min이, right_side에는 max만 남고 return을 시작한다.
    # 차곡차곡 min + 1, max - 1 -> min + 2, max - 2 ... 쌓이고, 정렬이 완성된다.
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array)

시간 복잡도

데이터의 크기가 N이라면,

각 순환 호출 단계의 비교 연산: O(N)

총 호출의 횟수: O(logN)

따라서 평균, 최선의 시간복잡도는 O(NlogN)이다.

최악의 경우는 O(N^2)이다.

정렬하고자 하는 배열이 이미 오름차순 혹은 내림차순으로 정렬이 되어있는 경우,

각 호출 단계 비교 횟수 O(N), 총 호출 횟수 O(N)이 되어 O(N^2)이다.

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해 수행된다.

재귀 호출 깊이 만큼 추가적인 공간이 필요하므로 O(logN)이다.

최악의 경우 O(N)이다.

특징

• 불안정 정렬
• 불균형 분할 (분할이 항상 절반으로 뚝 나뉘는 것이 아니다. 최악의 경우 시간 복잡도의 비효율을 초래한다.)

계수 정렬 Counting sort

요약

비교하지 않는 정렬이다.

데이터의 값 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.

위 조건에서는 매우 빠르게 동작한다.

구현1: 카운트한 값만큼 반복하는 방식

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
result = []

count = [0] * (max(array) + 1) # 값의 모든 범위를 포함하는 카운터 배열. 0으로 초기화

for i in range(len(array)):
    count[array[i]] += 1 # array 원소의 개수를 센다.

for i in range(len(count)):
    for j in range(count[i]): # 현재 원소가 count된 수만큼 반복해서 추가한다.
        result.append(i)

print(result) # [0, 0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9]

구현2: 누적합을 사용하는 방식 (다소 직관적이지 않다)

def counting_sort(arr):
    # 1단계: 입력 배열에서 최대값 찾기
    max_val = max(arr)
    count = [0] * (max_val + 1)  # 각 숫자의 등장 횟수를 저장할 배열 초기화
    
    # 각 숫자의 등장 횟수 세기
    for num in arr:
        count[num] += 1
    
    # 2단계: 누적합 계산
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # 3단계: 정렬된 배열을 생성하기 위한 임시 배열
    output = [0] * len(arr)
    
    # 원본 배열을 거꾸로 순회하며 정렬된 위치에 숫자 배치
    for num in reversed(arr):
        idx = count[num] - 1  # 정렬된 배열에서의 위치 계산. 누적합에서 1을 빼야 0부터 시작하는 인덱스 반영.
        output[idx] = num
        count[num] -= 1  # 다음 같은 숫자가 올 위치를 위해 누적합 감소
    
    return output

# 예제 배열
arr = [1, 4, 1, 2, 7, 5, 2]
sorted_arr = counting_sort(arr)
print(sorted_arr) # [1, 1, 2, 2, 4, 5, 7]

시간 복잡도

데이터의 개수가 N / 정수의 최대값이 K라면,

카운터 배열의 초기화: O(N)

카운터 배열의 누적합을 만드는 과정: O(K)

O(N + K)의 시간 복잡도를 갖는다.

O(N)이 아닌 이유는 [1, 999999] 배열을 정렬할 경우, N = 2임에도 K의 크기만큼 누적합을 계산해야 하기 때문에.

공간 복잡도

누적합 배열: O(K)

정렬된 배열: O(N)
따라서 추가적으로 필요한 공간은 O(N + K)이다.

비교 기반 알고리즘과 다르게 동작하기 때문에, 정렬된 배열을 위한 공간 O(N)이 필요하다는 것을 기억하자.

특징

• 안정 정렬 (stable sorting)
• 제자리 정렬이 아니다 !!! 비교 기반 알고리즘과는 다르다.

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/7C9RgOcvkvo?si=p-_dsBcTLy0K_6WN

스택 Stack

Last-In First-Out

먼저 들어온 데이터가 나중에 나가는 선입후출 자료구조.

stack = []

stack.append(5) # push
stack.append(3)
stack.append(2)
stack.pop() # pop

print(stack) # [5, 3]

python에서 stack은 리스트로 구현할 수 있다.

• 삽입: append(요소) # O(1)
• 삭제: pop() # O(1)

큐 queue

First-In First-Out

먼저 들어온 데이터가 먼저 나가는 선입선출 자료구조.

from collections import deque

queue = deque()

queue.append(5) # push
queue.append(3)
queue.popleft() # pop
queue.append(2)

print(queue) # [3, 2]

python에서 queue는 deque을 사용해서 구현한다.

삽입: append(요소) # O(1)

삭제: popleft() # O(1)

deque은 내부적으로 연결 리스트로 구현이 되어 있다.

따라서 삽입, 삭제가 O(1)으로 가능하다.

단 random access가 불가능하기에, 요소 접근에는 O(N)이 소요된다.

재귀 함수 Recursive Fuction

재귀 함수란? 자기 자신을 다시 호출하는 함수.

재귀 함수는 반복문으로 동일하게 구현이 가능하다. 역도 그렇다.

코드의 길이는 짧아지지만, 인간에게 직관적이지 않으므로 신중하게 사용해야 한다.

문제 풀이에 활용하려면 종료 조건을 반드시 명시해야 한다.

종료 조건 없이 함수가 무한히 호출되면, stack overflow가 발생하기 때문.

import sys
sys.setrecursionlimit(10 ** 5)

python3는 기본적으로 재귀 깊이를 1,000으로 제한해 놓았다.

그러나 문제를 풀다보면 이 제한을 해제해야 하는 경우가 있다.

sys.setrecursionlimit()으로 이 제한을 늘려주자

직접 해본 결과 재귀 깊이가 29945를 넘어가면, segmentation fault 에러가 발생한다.

프로그램이 메모리를 잘못 액세스 했을 때 발생하는 오류로, stack overflow를 원인으로 발생하는 오류 중 하나이다.

정해진 메모리 공간을 넘어가면, 다른 데이터를 건드릴 수 있기에 이를 방지하기 위한 에러이다.

실전에서는 재귀 깊이 제한을 10 ** 5 정도로 설정한 뒤에, 종료 조건을 반드시 작성하자.

예시1. 팩토리얼

def factorial_recursive(n)
    if n <=1 :
        return 1
    return n * factorial_recursive(n - 1)
    
# 0! == 1
# 1! == 1

예시2. 유클리드 호제법

def gcd(a, b)
    if a % b == 0 :
        return b
    else :
        return gcd(b, a % b)
        
# 성질: a와 b의 나머지가 r이라면, a와 b의 최대 공약수 == b와 r의 최대 공약수
# a, b의 대소 관계와 상관없이 동작한다.

DFS (Depth First Search)

정의

깊이 우선 탐색.

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.

뼈대

def dfs(graph, v, visited):
    
    visited[v] = True # 현재 노드 방문 처리
    print(v, end = " ") # 방문한 노드를 순서대로 출력
    
    for i in graph[v]: # 인접한 노드를 모두 확인
        if not visited[v]: # 방문하지 않은 노드가 있다면
            dfs(graph, i, visited) # 재귀적으로 탐색

스택 혹은 재귀 함수를 이용한다.

1. 탐색 시작 노드를 스택에 삽입 / 방문 처리
2. 스택 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리.
   방문하지 않은 인접한 노드가 없으면 스택 최상단 노드 꺼냄.
3. 2번 과정을 수행할 수 없을 때 까지 반복

BFS (Breadth First Search)

정의

너비 우선 탐색.

가까운 노드부터 우선적으로 탐색하는 알고리즘.

뼈대

from collections import deque

def bfs(graph, start, visited):
    
    queue = deque([start]) # deque에 시작 노드를 추가해서 초기화
    visited[start] = True # 현재 노드 방문 처리
    
    while queue: # 큐가 빌 때까지 반복
        v = queue.popleft() # 가장 먼저 들어온 노드를 제거 # 처음에는 시작 노드
        print(v, end = " ") # 순서대로 출력
        
        for i in graph[v]: # 인접한 노드를 모두 확인
            if not visited[i]: # 방문하지 않은 노드가 있다면
                queue.append(i) # 큐에 추가하고
                visited[i] = True # 방문 처리

큐를 이용한다.

1. 탐색 시작 노드를 큐에 삽입 / 방문 처리
2. 큐에서 노드 꺼내고 해당 노드의 인접 노드 중에서, 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번 과정을 수행할 수 없을 때까지 반복

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/2zjoKjt97vQ?si=VgYo4fBNuccHh7P5

그리디

정의

현재 상황에서 지금 당장 좋은 것만 선택하는 알고리즘.

정당성 분석이 선행되어야 한다.
--> 단순하게 가장 좋아보이는 것만 선택하면, 최적의 해를 구할 수 있는지?

실제로 유형을 모른 채로 문제를 만났을 때, 그리디 알고리즘을 사용해야 하는 근거는 다음과 같다.

1. 문제의 구조:

• 최적 부분 구조: 작은 문제의 최적 해결책이, 전체 문제에도 적용될 수 있어야 함.

2. 선택의 기준:

• 탐욕적: 현재 정보에 한해, 제일 좋은 것을 선택.
• 단기적: 각 선택은 현재 정보만을 기반으로 이루어짐. 이전 혹은 미래의 선택을 고려하지 않음.
• 불가역적: 선택이 이루어지고 나면, 이후의 과정에서 그 선택을 되돌릴 수 없음. 모든 선택은 최종 선택임.

1. 거스름 돈

큰 단위가 항상 작은 단위의 배수이므로 최적의 해를 보장한다.
예: [500, 400, 100]이라면, 큰 단위(500)가 작은 단위(400)의 배수가 아니므로, 그리디를 적용할 수 없다.

2. 1이 될 때까지

1빼기 보다, 나누기를 많이 하는 것이 대부분의 상황에서 유리하다.

현재 값이 2이상이면 나누는 것이 1 빼는 것보다 빠르게 조건을 달성할 수 있으니까.

n, k = map(int, input().split())

result = 0

while True:
    target = (n // k) % k # n과 가장 가까우면서 작은 k로 나누어 떨어지는 수
    result += (n - target) # 어차피 1씩 빼면서 target까지 가야한다. 그것을 한 번에.
    
    n = target # 1씩 빼서 target까지 도착했다고 치고
    
    if n < k: # 나누는 수보다 작아지면 탈출
        break
        
    result += 1
    n //= k # while을 한 번 반복할 때마다, k로 한 번씩 나누는 셈

result += (n - 1) # 더 이상 나눌 수 없는 상태이므로, 1씩 빼서 1에 도착할 때까지 횟수
print(result)

3. 곱하기 혹은 더하기

피연산자가 1 또는 0이 아니라면 항상 곱하기가 유리하다.

4. 모험가 길드

배열을 정렬하고, 작은 값부터 임시 그룹에 추가하며, 조건을 만족하는 즉시 마을을 떠나면 최적의 해를 구할 수 있다.

그리디 알고리즘을 적용해야 하는지 헷갈릴 수 있다.

그리디 알고리즘 선택 근거를 다시 생각해보자.

1. 문제의 구조: [1]인 경우와 [1, 2, 3]인 경우, 모두 같은 풀이를 적용할 수 있다.

2. 선택의 기준: [1]인 경우와 [1, 2, 3]인 경우, 탐욕적으로 선택해도 최적의 해가 나온다. 각 선택은 단기적이고 불가역적이다. 

구현

정의

풀이를 떠올리는 것은 쉽지만 소스 코드로 옮기기 어려운 문제

1. 알고리즘은 간단한데 코드가 지나칠 정도로 길어짐
2. 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 함
3. 문자열을 다룸
4. 적절한 라이브러리를 찾아서 사용해야 함

1. 상하좌우

방향 벡터를 사용한 문제.

행렬의 시작 부분인 (0, 0)이 좌상단 임을 기억할 것.

2. 시각

h = int(input())

count = 0

for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            if "3" in str(i) + str(j) + str(k): # 이렇게 하면 쉽다.
                count += 1

print(count)

완전 탐색.

하루는 86,400초이므로 완탐을 하기에 무리 없다.

파이썬은 1초에 2,000만 번 정도 연산을 수행할 수 있다고 생각하기.

3. 왕실의 나이트

8방향 벡터.

4. 문자열 재정렬

data = input()
result = []
value = 0

for x in data:
    if x.isalpha(): # 문자면 True 아니면 False # isNumeric()도 있음
        result.append(x)
    else:
        value += int(x)

result.sort()

if value != 0: # 숫자가 없을 경우 표시하면 안 되니까
    result.append(str(value))

print("".join(result)) # 리스트의 원소를 합쳐서 문자열로 만드는 방법