우주의 IT 소행성

다이나믹 프로그래밍 (DP)

- 메모리 공간을 더 사용하여 연산속도를 비약적으로 증가시키는 방법

- 동적 계획법이라고도 함

- 탑다운과 보텀업 방식으로 나뉨

다이나믹 프로그래밍의 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

메모이제이션 (캐싱)

- DP구현 방법중 하나, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식이 호출될 때 메모한 결과만을 그대로 가져오는 기법

탑다운 (Top-Down, 하향식)

- 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법

- 큰 문제를 해결 하기 위해 작은 문제를 호출한다고 해서 Top-Down 방식이라 함

- 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.

보텀업 (Bottom-Up, 상향식)

- 반복문을 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법

- 작은 문제부터 차근차근 답을 도출한다고 해서 보텀업 방식이라 한다.

- 다이나믹 프로그래밍의 전형적인 형태

- 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP테이블'이라 부른다

다이나믹 프로그래밍과 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전 계산 결과를 일시적으로 기록해 놓은 것이므로 다이나믹 프로그래밍과는 별도의 개념이다.

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

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

그래프란?

- 노드와 간선(정점)으로 표현된 자료구조

- 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 그래프 탐색이라고 한다.

- 두 노드가 간선으로 이어져 있으면 '두 노드는 인접(Adjacent) 하다'라고 표현한다.

그래프의 표현 방식

- 그래프를 프로그래밍에서 표현하는 방식은 크게 2가지이다

1. 인접 행렬 방식 (Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현

표로 표현했을 때

INF = 999999999 # 무한

# 2차원 리스트의 인접 행렬 표현
graph = [
	[0, 3, 5],
    [3, 0, INF],
    [5, INF, 0]
}

print(graph)

파이썬 코드로 표현했을 때

- 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리의 낭비가 심함

- 인접 행렬 방식이 인접 리스트 방식보다 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠름

2. 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현

graph = [[] for _ in range(3)]

graph[0].append((1, 5))
graph[0].append((2, 3))

graph[1].append((0, 5))

graph[2].append((0, 3))

print(graph)

- 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용함

- 인접 리스트 방식은 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림 (데이터를 하나씩 확인)

# DFS
def dfs(graph, v, visited):
	visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
dfs(graph, 1, visited)

BFS (Breadth First Search, 너비 우선 탐색)

- 가까운 노드부터 탐색하는 알고리즘

- DFS와 반대(가장 가까운 노드부터 / 가장 먼 노드부터)

- 선입선출의 큐 자료구조를 사용

- 재귀로 DFS를 구현하면 수행 시간이 느려질 수 있음

- 스택을 사용하여 DFS구현을 빠르게 동작시킬 수 있음

- 일반적인 경우 DFS보다 BFS의 동작이 빠름

# BFS
from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
    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

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
bfs(graph, 1, visited)

탐색(Search)

- 다수의 데이터 속 원하는 데이터를 찾는 과정

- 그래프 트리 등의 자료구조 안에서 사용하는 대표적인 탐색 알고리즘으로 BFS/DFS가 있다.

- BFS/DFS 탐색를 이해하려면 기본 자료구조에 대한 사전 지식이 수반되어야 한다.

자료구조(Data Structure)

- 데이터를 표현/관리/처리 하기 위한 구조

- 스택 / 큐 / 덱 / 그래프 / 트리 등이 있다

오버플로(Overflow)

- 특정 자료구조의 수용 범위를 넘어섰을 때, 추가로 데이터를 삽입할 때 나타나는 연산 오류

- Over(넘쳐) + flow(흐르다) ->> 데이터가 너무 많아서 넘쳐 흘러 버린다.

언더플로(Underflow)

- 오버플로의 반대로, 데이터가 전혀 없는데 데이터를 삭제할 때 나타나는 연산 오류

스택(Stack)

- 박스 쌓기와 같은 구조

- 박스는 아래서부터 위로 차곡차곡 쌓고, 아래의 박스를 꺼내려면 위의 박스를 치워야만 한다.

- 선입후출(First in Last Out / FILO) -> 먼저 들어온게(선입), 나중에 나간다(후출)

- 파이썬 리스트의 append()와 pop() 함수를 사용하면 stack과 동일하게 사용할 수 있다.

큐(Queue)

- 마트의 대기 줄이나 도로의 터널을 생각해보자.

- 먼저 들어온 (대기한) 사람이 먼저 나가는(우선권을 가지는) 자료구조로 선입선출(First In First Out / FIFO)이다.

- 파이썬 collections 모듈의 deque 자료 구조를 사용하자 (스택과 큐의 장점 둘 다를 가짐)

재귀 함수(Recursive Function)

- 자기 자신을 다시 호출하는 함수

# 예시
def recursive_function():
	print("나 불렀어?")
    recursive_function()

recursive_function()

이 경우에는 "나 불렀어?"가 무한히 출력된다.

파이썬에서는 재귀함수의 무한 출력을 방지하기 위해 횟수 제한을 두고있다. (기본 1000회)

따라서 코드 시작에

import sys
sys.setrecursionlimit(횟수)

를 삽입하여 필요에 따라 재귀함수의 출력 최대 횟수를 지정해주자.

하지만 애초에 재귀 함수를 사용할 때는 무한 출력이 발생하지 않도록, 종료 조건을 명시해주어야 한다.

컴퓨터 내부에서 재귀함수는 스택 자료구조를 이용한다.

따라서 가장 마지막에 호출된 재귀함수가 끝나야 순차적으로 앞선 호출이 완료되는 것이다.

그리디 알고리즘이란?

- 현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘 설계 기법

- 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음.

- 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형

- 주로 정렬과 짝을 이뤄 출제

- '가장 큰 순서대로', '가장 작은 순서대로'등의 기준을 알게 모르게 제시한다.

- 부분의 최적해들의 집합이 곧 전체문제의 해답일 경우 사용

대표적인 예시

- 거스름돈, 최소 신장 트리, 다익스트라, 허프만, 크리스컬....

거스름돈 문제

말 그대로, 돈을 거슬러 주는 문제인데, 가지고 있는 잔돈의 종류를 탐욕적으로 이용하여 가장 적은 잔돈의 종류를 내 주어야 한다.

거스름돈으로 사용할 동전의 종류

- 500원, 100원, 50원, 10원 (동전의 양은 무한하다고 가정)

1) 2340원을 받았다고 가정했을 때

- 500원 4개 -> 현재 동전 : 4 / 남은 돈 : 340

- 100원 3개 -> 현재 동전 : 7 / 남은 돈 : 40

- 10원 4개 -> 현재 동전 : 11 / 남은 돈 : 0

이므로 최적의 동전 개수는 11개이다.

2) 1260원을 받았다고 가정했을 때

- 500원 2개 -> 현재 동전 : 2 / 남은 돈 : 260

- 100원 2개 -> 현재 동전 : 4 / 남은 돈 : 60

- 50원 1개 -> 현재 동전 : 5 / 남은 돈 : 10

- 10원 1개 -> 현재 동전 : 6 / 남은 돈 : 0

이므로 최적의 동전 개수는 6개이다.

cost = int(input()
coins = [500, 100, 50, 10]
count = 0

for coin in coins:
	count += n
    n %= coin
 
print(count)

거스름 돈 알고리즘 코드

예시문제 1. 큰 수의 법칙 (2019 국가 교육기관 코딩 테스트 문제)

해당 문제에서 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 4라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다.

(서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.)

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 결과를 출력하시오.

<입력 예시>

5 8 3

2 4 5 4 6

<출력 예시>

46

n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort(reverse = True)
target = 0
result = 0
count = 0

while count < m:

    if target == 0:
        for j in range(k):
            result += data[target]
            count += 1
        target = 1

    else:
        result += data[target]
        target = 0
        count += 1

print(result)

이는 M의 숫자가 커지면 시간 초과가 될 수도 있는 코드이다.

주어진 배열의 1, 2 번째로 큰 수만을 사용하여 일정한 규칙을 나타내기 때문에

이를 일반항으로 도출하여 풀어낼수도 있지만, 시작의 장이기에 넘어가도록 하겠다.

다익스트라 알고리즘 (추가 예정)