알고리즘 정리

11 Sep 2020 in Algorithm on Basics

1. 개요
2. 주요 라이브러리의 문법과 유의점
3. 복잡도
- 알고리즘 설계시 주의사항
4. 기초 기타 알고리즘
- 에라토스테네스의 체
- 투 포인터
5. 그리디 알고리즘
6. 완전탐색, 시뮬레이션
6. DFS/BFS
7. 정렬
8. 이진 탐색
9. 다이나믹 프로그래밍
10. 최단 경로
11. 그래프 이론
기출 풀면서 고민했던 내용

1. 개요

지금까지 포스팅한 파이썬 알고리즘을 정리하는 포스팅이다. 모든 내용을 정리하진 않고, 복습하면서 기억이 나지 않는 부분과 빠르게 정리하고 싶을 때 참고할 내용 정도만 정리했다. 자세한 내용을 확인하고 싶다면 각 제목을 클릭하도록 하자. 각 제목을 클릭하면 해당 포스팅으로 이동하도록 링크를 걸어두었다.

2. 주요 라이브러리의 문법과 유의점

itertools의 permutations와 combinations는 클래스이므로 사용시 list로 형변환해서 사용한다.
bisect_left, bisect_right을 이용하면 이진 탐색을 쉽게 구현할 수 있다.
collections 라이브러리의 Counter은 인자로 이터레이터가 들어오는데 예시로 리스트가 온 경우 a = Counter(리스트)와 같이 변수로 받아서 사용할 때는 a[‘찾을것’]과 같이 변수 뒤에 [‘찾고자하는 내용’]으로 사용시 개수가 반환된다. 숫자일 경우는 ‘’ 없이 사용

reverse와 reversed의 차이
둘 다 리스트의 요소를 뒤집을 때 사용한다. reverse는 리스트 타입에서 제공하는 함수이다. 따라서 arry.reverse() 이렇게 사용한다. 즉, 값을 반환하지 않고 해당 리스트를 역순으로 만들어준다.
reversed는 내장함수로 리스트에서 제공하는 함수가 아니다. reversed는 tuple과 str을 인자로 받으면 reversed 객체를 반환하지만 list를 인자로 받는 경우 리스트이터레이터를 반환한다. 사용법에는 큰 차이가 없고 사용할 때 list로 형변환 시켜서 사용한다.

3. 복잡도

알고리즘 설계시 주의사항

시간 복잡도

N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘으로 설계하면 풀이 가능
N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘으로 설계하면 풀이 가능
N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘으로 설계하면 풀이 가능
N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘으로 설계하면 풀이 가능

코딩 테스트 환경에서는 1초에 2,000만에서 1억정도의 연산을 처리할 수 있다. 대부분의 시간제한은 1초인 경우가 많기 때문에 복잡도를 신중히 고려해야한다.

공간 복잡도

데이터의 단위가 1,000만 단위가 넘어가지 않도록 알고리즘 설계

알고리즘 소요 시간 체크

import time
start = time.time()
end = time.time()
print(end-start)

4. 기초 기타 알고리즘

에라토스테네스의 체

소수 판별에 사용하는 알고리즘

N+1 크기의 리스트를 True로 초기화
- 인덱스 0과 1은 False로 수정
남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 선택
남은 수 중에서 i를 제외한 i의 모든 배수는 False로 수정
for문을 사용하여 2부터 (n의 제곱근+1)까지 2,3과정을 반복
- 제곱근 이후에는 2 * 8, 8 * 2처럼 중복이 발생하기 때문에 범위가 위와 같이만 해도 걸러낼 수 있음

투 포인터

리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘

특정한 합(M)을 가지는 부분 연속 수열 찾기

시작점과 끝점이 첫 번째 원소의 인덱스 0을 가리키도록 한다.
현재 부분합이 M과 같다면 count+=1
현재 부분합이 M보다 작으면 end를 1 증가(전체 길이 초과하기 전까지)
현재 부분합이 M보다 크거나 같으면 start를 1 증가
start가 리스트 끝까지 갈때까지 위 과정 반복

이미 정렬된 두 리스트 합치기

이미 정렬된 리스트 A와 B를 받는다.
리스트 A, B에서 처리되지 않은 원소 중 가장 작은 원소를 i, j
A를 기준으로 두자면 i<len(a) and a[i]<b[j] 이면 결과리스트에 a[i]를 대입해주고 인덱스+1
이외의 경우(b가 작거나, 결과 인덱스가 len(a)를 넘어가는 경우) b[j]를 결과리스트에 대입하고 인덱스+1
- 이렇게 분류해주면 따로 남은 리스트를 대입해줄 필요가 없다.
리스트 A, B에 더이상 처리할 원소가 없을 때까지 위 과정 반복

여러 쿼리의 구간 합 계산

몇 개 안되는 쿼리만 구한다면 단순히 계산하면 되지만 여러 개의 쿼리가 존재한다면 각 쿼리[left,right]에 대해서 구간 합을 빠르게 구하기 위해서는 리스트 맨 앞부터 특정 위치까지의 합을 미리 구해놓는 것이 좋다.

N개의 수에 대하여 해당 인덱스까지의 누적 합을 계산하여 배열 P에 저장한다.
매 M개의 쿼리 정보 [L,R]을 확인할 때, 구간 합은 P[R]-P[L-1]

5. 그리디 알고리즘

현재 상황에서 나중을 고려하지 않고 지금 당장 좋은 것만 고르는 알고리즘
문제에서 가장 큰 순서대로, 가장 작은 순서대로와 같이 간단한 기준을 제시해주며, 정렬 알고리즘과 짝지어 출제된다.

거스름돈 유형이 대표적인 그리디 알고리즘인데 이때 제시된 큰 거스름돈들은 자신보다 작은 거스름돈들(모두)의 배수여야 한다.
주어진 수 중에서 m번 더해서 가장 큰수를 만들고 연속으로 k번을 초과해서 더할 수 없는 문제
- 일일이 다 더하기 보다는 규칙을 확인해서 한 번에 처리한다.
- m//(k+1) 만큼 규칙적으로 묶을 수 있는 부분은 한 번에 처리하고 m%(k+1)도 한 번에 처리하는 것이 좋은 처리 방식
N이 1이 될때까지 1빼기 연산과 k로 나누기 연산하기
- 나누기 연산을 한 번에 할 수있는 특별한 방법이 없지만 빼기 연산은 N%K를 통해 나머지를 한 번에 빼면서 처리

6. 완전탐색, 시뮬레이션

완전 탐색 : 모든 경우의 수를 다 계산하는 방법
시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 방법

완전 탐색과 시뮬레이션 문제는 대부분 이동에 관련된 문제가 많다.

방향 경로에 따라 dx, dy 리스트를 만들어 활용하는 것이 좋다. 필요하다면 방향도 리스트로 만들어 for문을 돌리면서 입력된 방향과 일치하는 경우 px, py로 사전에 x,y의 이동 후 경로를 확인하고 조건에 따라 이동 여부를 확인하는데 사용하는 것도 좋은 방법이다.
dx와 dy 중 하나는 일정한 거리만큼 이동하는데 하나는 +a도 가능하고 -a도 가능한 경우에는 step 리스트를 따로 만들어 모든 경우의수를 step[[2,1],[2,-1]]같이 만들어서 활용하자.

대체로 완전탐색과 시뮬레이션 문제는 문제의 길이가 긴편이고 코드도 긴 편이다. 따라서 pypy3를 선택하도록 하고 메모리 제한이 있으므로 1,000만 이상의 리스트는 사용하지 않도록 하자.

6. DFS/BFS

프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있다.

인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식

두 방식은 메모리 측면에서 차이를 보인다. 메모리 측면에서 보자면 인접 행렬 방식은 모든 관계를 저장하므로 메모리가 불필요하게 낭비된다. 인접 리스트 방식은 연결 정보만을 저장하기 때문에 메모리의 효율적 사용이 가능하다. 하지만 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.

DFS

DFS는 깊이 우선 탐색이라고 하며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 즉, 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후 다시 돌아가 다른 경로를 탐색하는 알고리즘이다.
구현할 때 재귀함수의 사용(스택 자료구조)과 방문표시를 위해 따로 리스트를 선언하거나 주어진 그래프에 덮어씌운다는 것을 기억하자.

방문 표시를 위해 선언한 리스트에 탐색 시작 노드를 방문 처리한다.
for문을 사용해서 시작 노드의 인접노드를 확인한다.
방문하지 않은 인접노드의 경우 재귀함수를 호출하여 방문하지 않는 노드에 대해서 다시 DFS를 수행한다.

일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다. DFS의 기능을 생각하면 순서에 상관없이 처리해도 되지만, 코딩 테스트에서는 번호가 낮은 순서부터 처리하는 경우가 있기에 관행적으로 번호가 낮은 순서부터 처리하도록 구현하는 편이다.
cf) 재귀함수는 스택 자료구조
컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다. 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다. DFS는 스택을 이용하는 알고리즘이기에 재귀를 사용하면 간결하게 구현할 수 있다. 데이터의 개수 N개인 경우 O(N)의 시간이 소요된다.

시간 복잡도

인접 리스트로 표현할 경우 : O(V+E)
- 모든 정점을 한 번씩 방문하고, 모든 간선을 한 번씩 검사하기 때문
인접 행렬로 표현할 경우 : O(V^2)
- for loop를 V만큼 돌기 때문에 O(V) 시간이 필요한데 모든 정점을 방문할 때마다 dfs를 호출하므로 V * O(V) = O(V^2)

BFS

BFS는 너비 우선 탐색이라고 하며, 가까운 노드부터 탐색하는 알고리즘이다. BFS의 구현에서는 큐 자료구조를 이용하는 것이 정석이다. DFS와 마찬가지로 방문 리스트를 따로 작성하거나 주어진 그래프에 덮어씌우면서 방문표시를 한다는 점을 기억하자.

탐색 시작 노드를 큐에 삽입하고 방문처리 한다.
while문을 이용해서 큐가 비어있을 때까지 3번 과정을 반복한다.
큐에서 노드를 꺼내면서 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.

시간 복잡도

인접 리스트로 표현할 경우 : O(V+E)
- 모든 정점을 한 번씩 방문하고, 모든 간선을 한 번씩 검사하기 때문
인접 행렬로 표현할 경우 : O(V^2)
- for loop를 V만큼 돌기 때문에 O(V) 시간이 필요한데 모든 정점을 방문할 때마다 bfs를 호출하므로 V * O(V) = O(V^2)

BFS와 DFS 어느 것을 선택할까?

사실 코드레벨에서 본다면 DFS가 BFS보다 훨씬 간단하다. 따라서 DFS와 BFS로 모두 풀 수 있는 경우에는 DFS를 사용하는 것이 편할 수 있다.
예시로 목적지가 정해져 있는 미로에서 최소 이동 칸 수를 구하는 문제를 보면 갈림길에서 어디로 이동해야 할지 선택해야 한다. 이런 경우에는 BFS를 통해 해당 좌표마다 그래프에 이동 칸수를 저장해두면 된다. 이처럼 해당 좌표를 기준으로 모든 경로에 대해 고려가 필요하다면 BFS를 사용하는 것이 좋은 선택이다.
최종 목적지가 정해져 있지 않은 단순히 어느 조건에 따라 탐색하고 탐색한 위치를 방문처리하고 탐색을 종료하는 경우라면 DFS를 사용하는 것이 좋은 선택이다.
참고로 코딩 테스트에서 재귀 함수로 DFS를 구현할 경우, 컴퓨터 시스템 동작 특성상 실제 프로그램의 수행 시간이 느려질 수 있어 조금 더 빠르게 구현하고 싶다면 BFS를 사용해야 한다.

7. 정렬

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 파이썬에서는 특정한 리스트의 원소를 뒤집는 메서드를 제공하기 때문에 내립차순 정렬은 오름차순 정렬을 수행한 후 결과를 뒤집어서 만들 수 있다. 리스트 뒤집기 연산은 O(N)의 복잡도로 간단히 수행 가능하다.

선택 정렬

가장 원시적인 방법으로 매번 가장 작은 것은 선택해서 정렬되지 않은 원소 중 가장 작은 인덱스의 위치와 스왑하여 정렬하는 알고리즘이다. for문을 n-1번 수행하게 되는데 n-1번 수행하면 마지막 원소는 자동으로 자기 자리를 찾아가기 때문이다. 시간 복잡도는 직관적으로 for문이 2번 중첩되므로 O(N^2)이다.

삽입 정렬

삽입 정렬은 주어진 상태에서 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 매우 효율적이다. 삽입 정렬은 첫 번째 데이터가 정렬되어 있다고 가정하고 두 번째 데이터부터 정렬을 시작한다. 선택 정렬과 마찬가지로 for문 안에서 스왑을 사용한다. 시간 복잡도는 for문이 2번 중첩되므로 평균적으로 O(N^2)이지만, 이미 정렬이 거의 완료된 경우는 매우 빠르게 동작한다. 최선의 경우는 원소를 비교만 하고 끝나기 때문에 O(N)의 복잡도를 가진다.

퀵 정렬

퀵 정렬은 가장 많이 사용되고 빠른 정렬 알고리즘이다. 피벗을 설정하고 리스트를 분할하는 방법에 따라 여러 방식으로 구분된다. 퀵 정렬은 피벗 설정에 따라 평균적으로 O(nlogn), 최악의 경우 O(N^2)의 시간 복잡도를 가진다. 퀵 정렬은 피벗 설정에 따라 구현 방법이 달라지며 재귀함수를 사용한다는 것을 기억하고 아래 두 가지 구현 방법은 꼭 기억해두자.

피벗을 맨 앞의 원소로 잡는 방법

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

def quick_sort(array):
    if len(array) <= 1:
        return array
    pivot = array[0]
    tail = array[1:]
    left_side = [i for i in tail if i <= pivot]
    right_side = [i for i in tail if i > pivot]
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

array= quick_sort(array)
print(array)

시간면에서는 약간 비효율적이지만 매우 간단하게 구현할 수 있으므로 꼭 기억하자.

피벗 설정을 중간값으로 하여 최악의 경우를 막는 방법

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

def mid_sort(array, left, mid, right):
    if array[left] > array[mid]:
        array[left], array[mid] = array[mid], array[left]
    if array[left] > array[right]:
        array[left], array[right] = array[mid], array[right]
    if array[mid] > array[right]:
        array[right], array[mid] = array[mid], array[right]

def quick_sort(array):
    def quick(arry, left, right):
        mid = (left + right) // 2
        mid_sort(arry, left, mid, right)
        array[mid], array[right - 1] = array[right - 1], array[mid]
        pivot = array[right - 1]
        pr = right - 2
        pl = left + 1
        while pr >= pl:
            while array[pl] < pivot: pl += 1
            while array[pr] > pivot: pr -= 1
            if pr >= pl:
                array[pl], array[pr] = array[pr], array[pl]
                pr -= 1
                pl += 1
            # 이 상황에서는 left와 right는 위에서 정렬을 한 상태고
            # pr = right -2인데 pr이 left와 같다는 뜻은 정렬할 것이 없는
            # 상태라는 뜻이다.
            if left < pr: quick(arry, left, pr)
            if right > pl: quick(arry, pl, right)

    n = len(array)
    quick(array, 0, n - 1)

quick_sort(array)
print(array)

리스트의 맨 앞, 맨 뒤, 중간을 뽑아서 오름차순 정렬한 뒤 중간값을 pivot값으로 설정하고 리스트의 맨 뒤에서 바로 앞에 값과 스왑한다. 그러면 맨 앞, 맨 뒤, 맨 뒤에서 바로 앞은 정렬이 완료된 상태이다. 그럼 나머지 범위를 가지고 퀵 정렬을 진행하면 된다. 이렇게 하면 나눠야 하는 부분이 한쪽으로 쏠리는 경우를 막을 수 있으므로 최악의 경우는 막을 수 있다.

계수 정렬

계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용가능한 정렬 알고리즘이다. 계수 정렬은 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문에 가장 큰 데이터와 가장 작은 데이터를 알고 있어야 한다. 또 둘의 차이가 메모리상 1,000,000을 넘지 않는 것이 좋고 데이터 값의 중복이 많을 수록 효과적으로 사용할 수 있다.
모든 데이터가 양의 정수인 상황에서 데이터의 개수 N, 데이터의 최대값의 크기가 K일 때 복잡도는 O(N+K)이다. N개의 데이터를 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시켜야하고, 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최대값의 크기(배열의 총 길이)만큼 반복을 수행해야하기 때문이다.

정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. 이는 병합 정렬을 기반으로 만들어졌다. 퀵 정렬보다는 느리지만 최악의 경우에도 O(nlogn)을 보장해 주는 특징이 있다. 따라서 특정한 요구사항이 없다면 정렬 라이브러리를 사용하는 것이 좋다.

sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 리스트 자료형으로 반환해준다. reverse=True 입력시 역순으로 반환한다.
sort()는 리스트 객체의 내장함수로 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다는 특징이 있다.
두 함수 모두 key매개변수를 입력받을 수 있는데 key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.

a = [7,5,9,0,3,1,6,2,4,8]
a.sort()

b = [7,5,9,0,3,1,6,2,4,8]
b=sorted(b)

a = [('바나나',2),('사과',5),('당근',3)]
result = sorted(a,key = lambda x:x[1])

8. 이진 탐색

순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 알고리즘이다. count() 메서드 이용시 내부에서는 순차 탐색이 수행된다.

이진 탐색

이진 탐색은 찾으려는 데이터와 중간점 위치의 데이터를 비교하고 아닐 경우 범위를 절반으로 줄이고 다시 중간점 위치의 데이터와 비교하는 과정을 반복하는 알고리즘이다. 이진 탐색은 배열 내부의 데이터가 반드시 정렬되어 있어야만 사용 할 수 있고 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다. 확인 과정에서 원소가 절반씩 줄어든다는 점에서 시간 복잡도는 O(logn)이다.
이진 탐색은 재귀함수와 while문으로 구현할 수 있는데 웬만하면 재귀보다는 반복문이 더 좋은 퍼포먼스를 보여주기 때문에 반복문을 사용하는 것이 좋다. 또한, 이진 탐색 문제는 입력 데이터가 많거나 탐색 범위가 매우 넓으므로 input보다는 sys라이브러리의 readline 함수를 사용하는 것이 좋다.
이진 탐색을 사용해야한다고 알아차리는 것은 어렵지 않다. 이진 탐색을 사용하는 경우는 탐색의 범위가 매우 큰 상황을 가정하는 경우가 많기 때문이다. 데이터의 개수나 값의 범위가 1,000만 단위 이상을 넘어가면 반드시 이진 탐색을 고려해보면 될 것이다. 코딩 테스트에서 이진 탐색은 단골 문제이므로 다시 한 번 정리해 보고 가자.

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

이진 탐색 트리

큰 데이터를 처리하는 소프트웨어는 대부분 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능하다.
이진 탐색 트리의 특징

부모 노드보다 왼쪽 자식 노드가 작다.
부모 노드보다 오른쪽 자식 노드가 크다.

단순 데이터 존재 여부 확인: in

in list, tutple이 올 경우 하나하나 순회하기 때문에 O(N)의 복잡도를 가진다. 이 경우에는 이진 탐색의 사용이 더 빠르다.
in set, dictionary의 경우 내부적으로 hash를 통해서 자료들을 저장하기 때문에 O(1)이 가능하고 해시 성능이 떨어지면 O(N)의 복잡도를 가진다.

따라서 단순히 어떤 데이터가 존재하는지의 여부만 확인하면 되는 경우는 in set, dictionary를 사용하는 것이 가장 간결하고 효율적이다.

cf) set 주의사항
set 함수는 입력 순서와 관계 없이 오름차순으로 자동 정렬하여 집합을 만든다.

9. 다이나믹 프로그래밍

다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘이다. 즉, 메모리 공간을 약간 더 사용하면서 연산 속도를 비약적으로 증가시킬 수 있는 방법이다. 사용 조건은 다음과 같다.

큰 문제를 작은 문제로 나눌 수 있다.
작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
- 2번과 같은 특징 때문에 점화식을 알면 대부분 쉽게 풀 수 있다.

다이나믹 프로그래밍은 2가지 방식(탑다운, 보텀업)이 있다. 탑다운(메모이제이션)방식은 하향식이라고 하며, 보텀업 방식은 상향식이라고 한다. 메모이제이션은 하양식이기 때문에 보통 재귀를 통해 구현하고, 다이나믹 프로그래밍은 상향식(보텀업)이기 때문에 보통 반복문을 통해서 구현한다.
메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 말한다. 메모이제이션은 값을 저장하는 방법으로 캐싱이라고도 한다. 메모이제이션은 탑다운 방식에만 국한되어 사용하는 표현이다. 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하고, 다이나믹 프로그래밍과는 별도의 개념이다. 다이나믹 프로그래밍은 저장된 결과를 다시 이용해야 하는데 메모이제이션은 한 번 계산된 결과를 어딘가에 담아 놓기만 하고 활용하지 않을 수도 있기 때문이다.
다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다. 보텀업 방식에서 사용되는 결과 저장용 리스트는 dp테이블이라고 부른다.
다이나믹 프로그래밍은 재귀함수와 반복문으로 구현할 수 있다. 하지만 일반적으로 반복문으로 구현하는 것이 성능이 더 좋다. 재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수도 있기 때문이다.

cf)언제 사용할까?

완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래걸리면 다이나믹 프로그래밍을 적용할 수 있는지, 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자.
다이나믹 프로그래밍을 적용하기로 했다면, 한 번에 정답에 접근하는 것이 아니고 정답을 구하기 위한 처음 단계부터 시작해서 단계별로 정답에 접근해야 한다.
뒤에서부터 시작했더니 계속 조건에 의해 값이 변화해서 방법을 찾기가 어렵다 -> 보텀업 방식으로 바닥부터 시작해서 조건을 따라가면 해결할 수 있다.

대표적인 예제

여러가지 연산이 주어지고 입력한 숫자를 원하는 수로 만드는 최소 연산 횟수
- 주어진 값부터 나누기 빼기 등등의 연산을 하면 뭐가 최소인지 알 수 없다. 따라서 원하는 수부터 연산을 시작해서 입력한 숫자까지 만드는 방식을 생각해야한다.
- 1부터 원하는 수까지 최소연산횟수를 저장 및 활용하면서 풀이
- 뺄셈 연산을 기본으로 하고 나눗셈 연산을 if문을 활용해 최소값을 dptable에 저장
주어진 수를 이용하여 규칙에 따라 최대 합 구하기
- n번 인덱스까지 도달했을 때 최대 합을 누적해서 저장하면서 기억
- 점화식은 제일 마지막 부분을 예시로 먼저 생각하여 점화식을 세우고 처음 부분은 따로 수정하는 방식으로 접근
해당 넓이를 주어진 방식으로 덮기
- n번 인덱스까지 도달했을 때 최대합을 누적해서 저장하면서 기억
- 점화식은 제일 마지막 부분을 예시로 먼저 생각하여 점화식을 세우고 처음 부분은 따로 수정하는 방식으로 접근
화폐가 배수가 아닌 경우의 거스름돈 최소 화폐 구성
- 0부터 n원까지 주어진 화폐로 for문을 돌리면서 누적으로 min을 통해 최소 화폐 개수 저장

대표적 예제로만 봐도 알 수 있는 다이나믹 프로그래밍 문제의 특징

n번 인덱스까지 도달했을 때까지 누적으로 해당 내용을 기억하며 다음 번에 사용
점화식으로 간단하게 풀이 가능
보텀업 방식으로 접근하지 않으면 접근이 어려움

10. 최단 경로

최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 길 찾기 알고리즘이라고도 하며, 보통 그래프로 표현한다. 종류는 여러 가지가 있지만 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘으로 대부분 해결할 수 있다.

다익스트라 최단 경로 알고리즘

특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이며, 그리디 알고리즘으로 분류된다. 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문이다.
특정 노드에서 다른 노드로 가는 각각의 비용만 구하고자 하는 목적을 가진 알고리즘이므로 인접 리스트 방식을 사용한다.

출발 노드 설정 및 최단 거리 테이블 초기화
출발 노드 우선순위 큐에 삽입과 최단 거리 테이블에서 출발 노드 인덱스의 값을 0으로 초기화
while문을 통해 q가 빌 때까지 4 ~ 5 과정을 반복
큐에서 꺼내고 해당 노드를 거쳐 최단 거리가 갱신될 필요가 있는 노드에 대해 최단 거리를 갱신 하고 큐에 삽입

다익스트라 최단 경로 알고리즘에서는 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택하는 과정을 반복하는데 이렇게 선택된 노드는 최단 거리가 완전히 선택된 노드이다. 자기 자신보다 짧은 거리에 있는 노드는 이미 다 계산을 마쳤고 해당 노드가 선택되는 차례가 온 것은 자신에게 오는 최소 거리가 다 갱신된 것이기 때문이다. 따라서 더이상 반복해도 해당 노드의 최단 거리는 변하지 않는다. 이와 같은 이유로 사실상 마지막 노드에 대해서는 해당 노드를 거쳐 다른 노드로 가는 경우가 있더라도 확인할 필요가 없다. O(ElogV)의 시간 복잡도를 가진다.(노드의 개수 V, 간선의 개수 E) 한 번 처리된 노드는 더이상 처리하지 않으므로 logV의 연산과 자신과 연결된 간선을 모두 확인하므로 E번 반복해서 O(ElogV)이다.

Cf)우선순위 큐
최단 거리 노드 선택은 우선순위 큐를 사용하는데 우선순위 큐는 첫 번째 원소를 기준으로 우선순위를 설정하고 파이썬 라이브러리에서는 기본적으로 최소 힙 구조를 이용한다. 따라서 최대 힙을 사용하고자 한다면 부호만 음수로 붙여서 넣고 꺼낼 때 부호를 다시 붙여 원래 값으로 되돌리는 테크닉을 사용하자. 참고로 우선순위 큐의 삽입, 삭제 연산은 O(logn)의 복잡도를 가지고 N번 수행하게 되면 O(nlogn)이다.

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우에 사용하는 알고리즘이다. 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하기 때문에 인접 행렬 방식을 사용한다. 플로이드 워셜 알고리즘은 다이나믹 프로그래밍이다. 노드의 개수가 N이라고 할 때 N번 만큼 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하여 기록하기 때문이다.
각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다. 예를 들어 1번 노드에 대한 최단 경로 확인은 다음과 같다. A -> 1번 노드 -> B VS A -> B 비교를 통해 최소 비용을 리스트에 갱신한다. (A,B) 쌍을 선택하는 방법은 해당 노드를 제외한 N-1개에서 2개를 선택하는 순열과 같다. 조합이 아닌 순열인 이유는 2차원 리스트이기 때문이다. 구현할 때는 라이브러리사용보다는 3중 for문 을 사용하여 구현하는 것이 간단하다. 또한 반드시 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화하도록 하자.
N-1개에서 2개를 선택하는 순열의 복잡도는 O(N^2)이다. 이 과정을 N번 반복해야 하니 O(N^3)이다. 직관적으로는 3중 for문이므로 O(N^3)으로 이해해도 된다.
참고로 잘 쓰이진 않지만, 플로이드 워셜 알고리즘을 수행하고 나서 (i,i) 값이 음수이면 i에서 i로 되돌아오는 음수 싸이클이 존재한다고 판단할 수 있다.(이는 점화식을 보면 쉽게 이해할 수 있다.)

알고리즘 선택
그래프 유형의 대표적 문제는 도시끼리 다리로 연결되어있고 다리에 따라 시간비용이 다른 가운데 최소 시간을 구하는 문제이다. 다익스트라를 선택할 것인가 플로이드 워셜을 선택할 것인가는 간단하다. 범위에 큰 경우에는 당연히 시간 복잡도를 고려해서 다익스트라 알고리즘을 선택해야 한다. 하지만 범위가 크지 않은 경우에는 문제의 유형에 따라 편한 방법은 선택하면 된다. 대부분 두 가지 알고리즘으로 모두 풀 수 있는데 최소 경로중에 어딘가를 반드시 들려야 한다면 플로이드 워셜을 고려하고 아닌 경우에는 다익스트라를 고려하면 된다.

벨만 포드 알고리즘

벨만 포드 알고리즘은 음의 간선이 포함된 상황에서 최단 거리를 찾는 알고리즘이다.
최단 거리는 최대 v-1개의 간선을 갖기 때문에 v-1번의 반복으로 간선을 확인하는데 v번 수행했을 때 최단 거리 갱신이 발생한다면 음의 싸이클이 존재하는 것으로 판단하여 음수 싸이클도 감지할 수 있다.
시간 복잡도는 정점의 개수만큼 간선 확인을 반복하므로 O(VE)이다.
특정 시작점이 주어지고 음의 싸이클 여부를 판단할 경우 위와 같은 방식을 사용하면 되지만, 그래프 전체에 대해 음의 싸이클이 존재하냐고 묻는다면 위와 같이 하면 시간초과가 나올 가능성이 크다. 모든 노드를 시작점으로 두고 확인해야하는데 파이썬은 그러기엔 느리기 때문이다.
그래프 전체에 대해 음의 싸이클의 존재 여부를 묻는 문제에서는 대부분 최단거리를 묻지 않는다.
따라서 로직상 시작위치와의 연결을 판단하기 위해서 작성했던 dis[current] != INF조건을 제거하고, 아무시작점이나 넣고 진행한 뒤 V번째 수행에서 갱신이 발생하면 음의 싸이클이 존재한다고 판단하면 된다.
이때는 최단 거리 테이블은 의미가 사라지고 그저 음의 싸이클 여부만 판단하는 테이블이 된다.

11. 그래프 이론

서로소 집합

서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할 수 있기 때문에 union-find 자료구조라고도 한다.

union(합집합) : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
find(찾기) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산(압축기법과 재귀 함수로 구현)
parent 리스트 : 해당 노드의 부모 노드를 저장하는 리스트

서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현하는데 서로소 집합 정보(합집합 연산)가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다.

union(합집합) 연산을 함수로 정의하고 서로 연결된 두 노드 A,B를 인자로 준다.
함수 내부에서는 A와 B의 루트 노드를 확인한다.
- 루트 노드가 같다면 이미 같은 집합
- 루트 노드가 다르다면 더 작은 원소가 부모노드가 되도록 구현한다.(큰 원소가 작은 원소를 가리키도록)
모든 union(합집합) 연산을 처리할 때까지 1 ~ 2 과정을 반복한다.

노드의 개수가 V개이고, 최대 V-1개의 union 연산과 M개의 find 연산이 가능할 때, 경로 압축 방법을 적용한 시간 복잡도는 O( V + M (1 + log(밑 2-M/V) (V) ) )이라고 알려져 있다.

서로소 집합을 활용한 무방향 그래프 내 사이클 판별

각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
- 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행
- 루트 노드가 같다면 사이클이 발생한 것으로 인지
모든 간선에 대해 1번 과정을 수행하고 루트 노드가 같은 경우가 발생하지 않는다면 사이클이 발생하지 않는 것이다.

신장 트리

신장 트리는 그래프 알고리즘 문제로 자주 출제되는 문제 유형이다. 신장 트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하기 때문에 신장 트리라고 한다.

크루스칼 알고리즘

신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 최소 신장 트리 알고리즘이라고 한다. 대표적인 최소 신장 트리 알고리즘으로는 크루스칼 알고리즘이 있다. 크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. 핵심은 가장 짧은 간선부터 차례대로 union연산을 하고 사이클이 발생시키는 간선은 제외하는 것이다. 과정은 다음과 같다.

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

최소 신장 트리는 일종의 트리 자료구조이므로, 최종적으로 신장 트리에 포함되는 간선의 개수가 (노드의 개수 -1)과 같다는 특징이 있다. 크루스칼 알고리즘에서 시간이 가장 오래 걸리는 부분은 간선을 정렬하는 작업이다. 따라서 시간 복잡도는 O(ElogE)이다. (E는 간선의 개수)

위상 정렬

위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 즉, 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다. 대표적 예시로는 선수과목이 정해진 커리큘럼이 있다. 위상 정렬 알고리즘을 이해하기 위해서는 진입차수를 알아야 한다. 진입차수란 특정한 노드로 들어오는 간선의 개수를 의미한다. 구체적인 알고리즘은 다음과 같다.

진입차수를 기록하는 리스트를 초기화하고 진입차수가 0인 노드를 큐에 넣는다.
큐가 빌 때까지 다음 과정을 반복한다.
- 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

모든 원소를 방문하기 전에 큐가 비게 된다면 싸이클이 존재한다고 판단할 수 있다. 추가적으로 위상 정렬의 답안은 여러 가지가 될 수있다. 큐에 들어가는 원소가 2개 이상인 경우가 있다면 큐에 들어가는 순서에 따라 답안이 달라지기 때문이다.
시간 복잡도는 O(V+E)이다. 모든 노드를 차례대로 확인하면서, 해당 노드에서 출발하는 간선을 차례대로 제거해야 하기 때문이다.
간단한 위상 정렬같은 경우에는 인접리스트로 연결된 간선들을 저장해서 풀이하는데 만약 이후에 간선 정보가 바뀌게 되는 경우는 인접리스트가 아닌 인접행렬로 풀이해야 한다.(찾아서 지우고 수정해야하기 때문)

기출 풀면서 고민했던 내용

항상 문제를 풀기 전에 어떤 식으로 풀지 주석으로 정리하고 들어가야 꼬여도 다시 돌아와서 정리할 수 있다.
대부분의 문제는 자료구조를 사용해야 풀리기 때문에 어떤 자료구조를 사용해야할지 정하고 들어간다.
바로 아이디어가 생각나면 진행하겠지만, 진행하던 도중 풀이가 막히게 된다면 잘못된 알고리즘을 선택했을 확률이 높다. 계속 해당 알고리즘만 생각하면 결국에는 빠져나올 수 없기 때문에 어느정도 마지노선 시간을 정해두고 해결할 수 없는 경우 다른 알고리즘을 생각해야 한다.
파이썬의 리스트의 경우 시작지점만 범위 인덱스 안에 있으면 끝지점의 인덱스는 범위를 넘어가도 알아서 잘라서 처리해준다.
- a=[1,2,3,4] -> a[3:7] 이렇게 표기해서 알아서 잘라준다.
방문처리를 기록해야하는 그래프 이동 문제에서 방문처리해야하는 좌표가 1개가 아니라 2개 이상인 경우 리스트 안에 집합 자료형을 사용해서 저장한다.
- ls = [{(1,1),(1,2)}]
- 집합 자료형은 순서를 보장하지 않기 때문에 {(1,2),(1,1)} 을 갖고 in으로 해도 있는지 없는지 확인할 수 있다.
범위가 억단위로 넘어간다면 이진 탐색을 떠올린다.
- 이진 탐색에도 여러 가지 유형이 있지만 틀은 명확하다.
- start와 end 지점의 기준을 세우고, 어느 시점에 mid를 이용해 start와 end 지점을 수정할 건지를 정하면 된다.
- 어려운 문제의 경우 mid를 어느 시점에 사용할지에 대해 구체적인 로직이 한번 더 들어간다.
- 이진 탐색은 정렬된 형태에서 진행한다는 조건이 있는데 파이썬 정렬은 글자수에 관계없이 우선순위에 따라 진행되므로 글자수에 따라 이진 탐색이 필요한 경우, 글자수를 기준으로 따로 리스트에 보관하고 해당 글자수에 맞는 리스트를 꺼내서 탐색해야한다.
파이썬 역순 출력은 [::-1]을 사용하는데 -1의 경우 맨 앞에 인덱스는 가장 마지막 인덱스가 들어가서 생략되는 형태이다.
점화식을 세워야 하는 경우, 반드시 가설 을 먼저 세우고 진행한다.
- 예를 들면, 앞에 인덱스까지는 값이 전부 최대값으로 채워져있다고 가정하고, 현재 인덱스의 최대값을 어떻게 구할까? 이런식으로 접근한다.
- 보통 dp의 문제의 경우 점화식을 세우게 된다.
  - 일반적인 문제라면, 처음부터 끝까지 해당 인덱스의 값에 최대 혹은 최소값을 누적해나가면서 풀이를 진행한다.
  - 주어진 입력값에 따라 끝점이 범위를 초과하는지 검증이 필요한 문제의 경우, 역으로 끝점을 시작점으로 두고 시작점을 끝점으로 두고 진행한다. 또한, 일반적으로 첫항의 점화식을 위해 맨 앞에 더미를 붙이는데 역으로 진행하게 되면 끝점에 더미를 하나 붙인다.
  - 다소 복잡한 dp문제의 경우, 앞쪽의 인덱스가 누적 최대, 최소값이 아니라 특정 조건에 의한 맞는 누적값을 저장하는 경우가 있다. 이때는 앞에 있는 것 모두와 비교해서 누적값을 찾아야 하고, 최종 답안을 구하기 위해 마지막 인덱스 값이 아니라 누적 리스트를 이용해 한번 더 연산을 해서 구하게 된다.
위상 정렬은 전체의 순위를 구할 때 사용하는 알고리즘이기 때문에 특정 요소의 상대적 순위만을 구하는 문제에서는 사용할 수 없다.
- 정점 개수 전에 큐가 비면 싸이클
- 정점 개수 전에 큐에 2개 이상 존재시, 정확한 순위 판단 불가능
플로이드 워셜
- 수행 이후에 i,i로 이동하는 값이 음수라면 음의 싸이클 존재
벨만 포드
- 시작점이 주어진 경우, n번째 루프시 변화가 발생하면 음의 싸이클 존재
- 기본적인 벨만 포드 알고리즘에서 시작점이 주어지고 진행하는 경우, if문으로 해당 정점으로 이동 가능한 경우에 대해서 갱신이 되는데, 최단 경로에는 관심이 없고 주어진 그래프가 음의 싸이클이 존재하는지에만 관심이 있다면, 시작점은 아무거나 넣고 if문에서 해당 정점으로 이동가능한 경우에 갱신하는 조건을 제외시켜버리고(언제든지 갱신 가능) n번째 갱신이 된다면 그래프에서 음의 싸이클이 존재하는 것으로 판단한다. 이때는 최단 거리는 구할수 없다.
편집 거리 같은 알고리즘은 모르고 있다면 풀기 어렵기 때문에 이런 알고리즘은 알고 있어야 풀 수 있다.

1. 개요

알고리즘 설계시 주의사항

에라토스테네스의 체

투 포인터

특정한 합(M)을 가지는 부분 연속 수열 찾기

이미 정렬된 두 리스트 합치기

여러 쿼리의 구간 합 계산

DFS

BFS

BFS와 DFS 어느 것을 선택할까?

선택 정렬

삽입 정렬

퀵 정렬

계수 정렬

정렬 라이브러리

순차 탐색

이진 탐색

이진 탐색 트리

단순 데이터 존재 여부 확인: in

다익스트라 최단 경로 알고리즘

플로이드 워셜 알고리즘

벨만 포드 알고리즘

서로소 집합

서로소 집합을 활용한 무방향 그래프 내 사이클 판별

신장 트리

크루스칼 알고리즘

위상 정렬

기출 풀면서 고민했던 내용

Templates (for web app):

Error