알고리즘 정리

2021년 08월 23일
제작기간 2021년 8월 16일 ~ 8월 23일
태그 CS

📚 Reference 알기 쉬운 알고리즘

1. 탐색

  • 순차탐색 (Sequential Serch)
    • 주어진 순서에 따라 차례로 탐색
  • 이진탐색 (Binary Search)
    • 정렬된 데이터에서, 1/2 지점의 값을 기준으로 범위를 줄여나가는 탐색
  • 보간탐색 (Imterpolation Search)
    • 탐색하고자 하는 값이 있을 법한 곳부터 탐색

2. 알고리즘

표현 방법

  • pseudo code(의사 코드): 알고리즘을 쉽게 표현할 수 있는, 코드와 유사하게 생긴 코드

분류

  • 분할 정복 (Divide-and-Conquer)
  • 그리디 (Greedy)
  • 동적 계획 (Dynamic Programming)
  • 근사 (Approximation)
  • 백트래킹 (Backtracking)
  • 분기 한정 (Branch-and-Bound)
  • Random(랜덤), Parallel(병랼), Distributed(분산), Quantum(양자택일), Genetic(유전자)…
  • 문제에 기반을 둔 분류
    • 정렬 알고리즘, 그래프 알고리즘, 기하 알고리즘…

복잡도

  • 시간복잡도(time complexity): 수행 시간
  • 공간복잡도(space complexity): memory공간의 크기
  • 최악/평균/최선 경우 분석으로 나뉨
  • asymptotic notation(점근적 표기): 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현
    • Big O 표기: 점근적 상한
    • Big Omega 표기: 점근적 하한
    • Theta 표기: 복잡도의 상한과 하한이 동시에 적용

3. 분할 정복 알고리즘 (Divide-and-Conquer)

주어진 문제의 입력을 분할하여 문제를 해결하는 방식.

  • subproblem(부분문제)
    • 분할된 입력에 대한 문제
    • 부분 문제는 가장 작은 단위까지 분할

합병 정렬 (Merge Sort)

  • 2개의 subproblem으로 분할 + subproblem의 크기가 1/2

퀵 정렬 (Quick Sort)

  • pivot을 정하여 작은 것은 좌로 큰 것은 우로 넘기는 방식
  • 큰 입력에서 가장 좋은 성능을 보임

선택 문제 (Selection)

  • n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제
  • 정렬된 입력에서 고르는 Binary Search의 방식을 사용
    • 피봇을 선택하여 small group과 large group을 구분
    • 각 그룹의 크기를 통해서 k번째 숫자가 속한 그룹 선택
  • subproblem의 크기가 일정X
  • median(중앙값)을 찾는데 자주 활용

최근접 점의 쌍 찾기 (Closest Pair)

  • 2차원 평면상의 n개의 점에서 가장 가까운 한 쌍 찾는 문제
  • 점의 개수를 1/2이 되게 공간을 나눠나가며 비교
  • 경계선의 점 거리를 고려해야 함

4. 그리디 알고리즘 (Greedy)

  • 최적화(optimization) 문제를 해결하는 알고리즘
    • 가장 좋은(최대/최소…) 해를 찾는 문제
    • 언제나 최적의 답은 아님

최소 신장 트리 (Minimum Spanning Tree)

  • 가중치 그래프에서 사이클 없이 연결한 트리 중 선분들의 가중치 합이 최소인 트리
  • Kruskal(크러스컬)
    • 가중치의 오름차순으로 선분 정렬하여 list L 생성
    • L에서 가중치가 최소인 선분 e를 가져오고 L에서 제거
    • e가 트리 T (최소신장트리) 에 추가되어 사이클을 만들면 추가
  • Prim(프림)
    • 가중치 그래프에서 임의의 점 p 선택
    • p가 아닌 점 v(n-1개)에 대해, (p, v)가 그래프 상에 있으면 각 가중치를 저장, 없으면 굉장히 큰 수로 지정
    • p먼 추가된 트리, T를 생성
    • T애 속한 점 u와 속하지 않은 점 v에 대해, (u, v)의 가중치가 최소인 선분을 추가
    • (이 때, 새로 추가된 v와 T 외부의 점 w의 가중치가 (p, w)의 가중치보다 작으면 갱신)

그 외

  1. 다익스트라 (Dijkstra)
    • Prim과 달리 지정된 출발점(s)에서 시작
    • 모든 점에 대한 가중치를 매우 큰 수, s에 대한 가중치를 0으로 초기화
    • s로부터 최단거리가 확정되지 않은 각 점에 대해, (s, v)의 가중치가 최소인 점 v의 가중치를 최소로 확정
    • s로부터 v를 통해 가중치를 줄일 수 있는 각 점 w의 가중치를 갱신
    • 반복
  2. 부분 배낭 문제 (Fractional Knapsack)
    • 담은 물건 list L, 배낭의 용량 C, 배낭 안의 물건 가치 합 v
    • 무게당 가치가 큰 물건을 추가
    • 반복
    • 물건을 부분적으로 더 담을 여유가 있으면 추가
  3. 집합 커버 문제 (Set Cover)
    • 최적해 대신 근사해(approximation solution)을 찾아야 함
    • U의 원소를 가장 많이 포함하고 있는 set을 선택하는 것을
    • 반복
  4. 작업 스케줄링 (Task Scheduling)
    • 시작시간의 오름차순으로 task 정렬한 list L
    • 가장 이른 시작시간의 task를 우선 배정
    • 다음으로 이른 시작시간의 task를 작업 가능한 Machine에 지정
    • 반복
  5. 허프만 압축 (Huffman compression)
    • prefix property(접두부 특성)이 존재
    • n개의 노드들의 빈도수에 대한 우선순위인 큐 Q
    • 빈도수가 가장 작은 노드 두 개를 Q에서 제거 후, 두 노드를 새 노드 N의 자식으로 설정
    • N을 Q에 삽입
    • 반복
    • 트리가 완성되면, root부터 왼쪽은 0, 오른쪽은 1을 부여
    • leaf node는 루트 다음부터 부여된 숫자를 읽어와 허프만 코드를 부여받음

5. 동적 계획 알고리즘 (Dynamic Programming)

  • 최적화 문제를 해결하는 알고리즘
  • 부분문제를 해결한 후, 그 해들을 이용해 큰 부분문제를 해결하는 방식

모든 쌍 최단 경로 (All Pairs Shortest Paths)

  • 각 쌍의 점 사이로 최단 경로를 찾는 문제
  • 각 점을 시작으로 다익스트라 알고리즘으로 해결 가능
  • 플로이드-워셜 알고리즘 (Floyd-Warshall)
    • 가중치 합이 음수가 되는 사이클은 없어야함
for k = 1 to n
  for i = 1 to n (단,i≠k)
    for j = 1 to n (단, j≠k, j≠i))
      D[i,j] = min(D[i,k]+D[k,j], D[i,j])

연속 행렬 곱셈 (Chained Matrix Multiplications)

  • 연속된 행렬들 곱셈에 필요한, 원소 간의 최소 곱셈 횟수 찾기
  • 적절한 행렬의 곱셈 순서를 찾아야 함
  • 이웃하는 행렬들끼리 곱하는 모든 부분문제를 해결
  • 부분문제의 크기를 변화해가며 계산
  • 각 행렬들을 가로 세로로 나열하여 만든 테이블로 표현 가능
    • i = j인 C[i, j]는 같은 행렬 끼리의 곱임으로 0으로 초기화 하고 upper triangle 부분만 사용

편집 거리 문제 (Edit Distance)

  • S를 T로 바꾸기까지 최소 편집 연산 횟수 구하는 문제
  • S의 길이와 T의 길이를 기반으로 한 2차원 배열로 표현
  • E[i,j]를 E[i,j-1], E[i-1,j], E[i-1,j-1]를 참조하여 계산
  • 여기서 E[i,j] = S의 접두부 i개를 T의 접두부 j개 문자로 변환시키는 데 필요한 최소 편집 연산 횟수 (편집 거리)

배낭 문제 (Knapsack)

  • 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제
  • 고려할 물건의 수와 배낭의 용량을 점점 늘려가며 해를 찾음

6. 정렬 알고리즘

bubble sort

  • 이웃하는 숫자를 비교하여 작은 수를 앞으로 이동시키는 과정 반복

selection sort

  • 배열 전체에서 최솟값 선택
  • 배열의 0번 원소와 자리 바꿈
  • 0번 원소를 제외한 나머지 원소들로 위 과정 반복
  • input insensitive: 항상 일정한 시간복잡도

insertion sort

  • 정렬이 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 알맞은 위치에 삽입 과정 반복

shell sort

  • gap이 5가되는 숫자끼리 그룹을 만들어서 그룹별 정렬
  • gap을 줄임
  • 각 그룹별로 삽입 정렬
  • 마지막에는 gap을 1로 설정하고 수행

heap sort

  • heap: 각 노드의 값이 자식 노드의 값보다 큰 완전 이진 트리
  • 힙의 루트의 숫자를 가장 마지막에 있는 노드와 바꿈
  • 새로 루트에 저장된 숫자로 인해 위배된 힙 조건 해결
  • 힙 크기 1 줄임
  • 위 과정 반복

정렬 문제의 하한

  • comparison sort: 숫자끼리 비교
  • lower bound: 이보다 낮을 수 없음
  • decision tree: 루트로부터 비교 결과에 따라 정렬된 결과가 저장

radix sort

  • 각 radix를 비교하여 정렬
  • stability 보장 필요: 정렬 시, 중복된 숫자의 순서가 입력에서의 순서와 동일

external sort

  • memory 용량이 입력의 크기에 비해 작음
  • merge sort: 부분적으로 memory에 읽고, 합병을 수행 후, 저장하는 작업 반복

7. NP-완전 문제

P(polynomial) 문제

NP 문제

  • 비결정적 다항식 시간 알고리즘
  • 해를 추측하고 확인 후에 결정

NP-완전(nondeterministic polynomial-complete) 문제

  • reduction: 어떤 문제를 다른 문제로 환원
  • 문제 A의 입력을 문제 B format으로 변환 후, B를 수행, 결과를 문제 A의 해로 변환
  • 시간 복잡도: 입력 변환 시간 + 알고리즘 시간 + 해 변환 시간

NP-완전 문제 종류

  • SAT(satisfiability)
  • Subset Sum: 주어진 정수 집합 S의 원소의 합이 K가 되는 S의 부분 집합 찾기
  • Partition: 주어진 정수 집합 S를 분할하여 원소의 합이 같은 2개의 부분 집합 X, T를 찾는 문제
  • Knapsack
  • Vertex Cover: 각 선분의 양 끝점들 중에서 적어도 1개의 점을 포함하는 점의 집합
  • Independence Set: 주어진 그래프에서 서로 연결하는 선분이 없는 점들의 집합
  • Clique: 주어진 그래프에서 모든 점들 사이를 연결하는 선분이 있는 부분 그래프
  • Graph Coloring
  • Set Cover: 부분 집합 중 합집합하여 S와 같게 되는 부분
  • Longest Path: 가장 긴 경로 (반복되는 점 X)
  • Traveling Salesman: 임의의 한 점에서 모든 점을 1번씩 방문하고 돌아오는 최단 경로
  • Hamiltonian Cycle: 임의의 한 점에서 모든 점을 1번씩 방문하고 돌아오는 경로
  • Bin Packing: 용량이 C인 통을 가장 적게 사용하여 물건을 모두 채우는 문제
  • Job Scheduling: n개의 작업과 작업 시간, m개의 동일 성능 기계가 주어졌을 때, 모든 작업을 가장 빨리 종료되도록 작업을 기계에 배정하는 문제

8. 근사 알고리즘

  • Approximation algorithm
    • NP-완전 문제를 해결하기 위해서는 다항식 시간, 모든 입력에 대한 해, 최적해 중에 1개를 포기해야함
    • 최적해를 포기하여 근사해를 구할 수 있음
    • approximation ratio를 제시해야함 (1.0에 가까울 수록 정확도가 높음)

여행자 문제 (Traveling Salesman Problem)

  • 임의의 점에서 모든 점을 1번씩 방문하고 초기점으로 돌아오는 경로를 최소화하는 문제
  • 최소 신장 트리(Minimum Spanning Tree)의 근사로 해결 가능
    • 최소 신장 트리를 구함
    • 삼각 부등식의 원리를 적용 + 중복 방문된 도시 제거
    • 간접적인 최적해의 값으로 MST의 가중치 합을 선정

정점 커버 문제 (Vertex Cover)

  • 주어진 각 선분의 양 끝점 중 적어도 한 점은 포함하는 점들의 집합 중 최소 크기 구하는 문제
  • 집합 커버 문제의 근사로 해결 가능
  • 선분을 선택하는 방식으로 모든 점 커버 가능
    • 커버가 되지 않은 선분들을 선택함
    • 이 선분들의 집합을 maximal matching이라 칭함
    • maximal matching의 양 끝점의 집합
    • maximal matching의 선분의 수를 간접적인 최적해로 선정

통 채우기 문제 (Bin Packing)

  • First Fit
  • Next Fit: 직전에 넣은 통에 여유가 있으면 그 통 선택
  • Best Fit
  • Worst Fit

작업 스케줄링 문제 (Job Scheduling)

  • 가장 일찍 끝나는 기계에 작업 배치
  • 근사해 < 최적해 2배

클러스터링(Clustering) 문제

  • 주어진 n개의 점을 k개의 그룹으로 나누고 중심 점을 k가 선택하는 문제
    • 임의의 점을 선택
    • 남은 점들 중에서, 선택된 점들과의 거리 중 가장 짧은 거리를 기준으로, 가장 먼 점을 선택하여 센터로 지정
    • k개의 점을 구할 때까지 반복
    • k+1의 점을 위와 같은 방식으로 구함
    • k+1의 점과 가장 가까운 센터를 기준으로 반경 결정
  • 근사비율은 2를 넘지 않음

9. 해 탐색 알고리즘

백트래킹 기법 (Backtracking)

  • 깊이 우선 탐색
  • 해가 아니면 되돌아가서 다시 해를 찾아가는 기법
  • optimization(최적화)문제와 decision문제 해결 가능
  • 최악의 경우 2의 n승개의 노드를 모두 탐색 (Exhaustive Search의 시간복잡도와 동일)

분기 한정 기법 (Branch-and-Bound)

  • 특정한 값을 부여하고 노드의 한정값을 활용하여 가지치기
  • 가장 우수한 한정값을 가진 노드를 우선 탐색(Best First Search)
  • 한정값이 최적해보다 낮거나 같으면 탐색 X
  • ex) 여행자 문제
    • 임의의 점 v의 한정값: 시작점 ~ v 경로 길이 + v ~ 시작점(다른 점들을 1번씩 방문)경로의 예측 길이
    • 예측 길이에는 가장 짧은 두 선분의 가중치의 평균 합을 이용

유전자 알고리즘 (Genetic Algorithm)

  • 여러 개의 해를 임의로 생성하여 초기 generation으로 지정 후, 다음 세대의 해를 생성
    • 반복 수행을 통해 최적해에 다가가므로 candidate solution이라고 함
  • 마지막 세대의 가장 우수한 해를 리턴
  • fitness value: 후보해의 값, 최적해에 근접하면 ‘우수한 해’
  • 후보해 생성 방법
    • selection 연산
      • 현 세대의 후보해 중에서 우수한 후보해 선택
    • crossover 연산
      • 선택 연산 수행 후의 후보해 사이에 수행
      • 교차점 이후의 부분을 서로 교환
      • crossover rate: 교차 연산을 수행할 후보해의 수
    • mutation 연산
      • crossover이 수행된 후에 수행
      • 후보해의 일부분을 임의로 변형
      • 이후 세대에서 더 우수한 후보해를 생성하기 위함
      • 더 우수한 해가 출현하지 않으면 종료
      • 최적해를 알 수 없음

모의 담금질 기법 (Simulated Annealing)

  • 후보해에 대해 이웃하는 이웃해를 정의
  • 항상 전역 최적해를 찾지는 않음
  • 초기 해로부터 탐색이 진행
  • 이웃하는 해를 정의
    • insertion (삽입)
    • switching (교환)
    • inversion (반전)