알고리즘 간단 정리

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

• 주어진 문제를 여러 개의 작은 문제로 나누어 푼 다음, 그 결과들로 주어진 문제를 푼다. 즉 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 때 적용된다.
• 구현 방식
  • 메모이제이션: 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 분할 정복은 문제를 분할했을 때 겹치는 문제가 발생하지 않는다. 반면 DP는 겹치는 문제가 발생하기 때문에 메모제이션이 필요하다.
  • Top-Down 방식: 재귀 함수를 이용하여, 큰 문제 해결을 위해 작은 문제를 호출하는 방식이다. 
  • Bottom-Up 방식: 반목문을 이용하여, 작은 문제부터 차근차근 답을 도출하는 방식이다.
  • 재귀 함수를 사용할 경우, depth가 깊어지는 문제가 생길 수 있으므로 가급적 Bottom-Up 방식이 권장된다
• 메모리를 소비해가며 샅샅이 뒤진다는 점에서 실행 시간이 그리디 알고리즘에 비해서 떨어지지만, 그리디 알고리즘보다 좀 더 폭넓은 범위에서 근사치가 아닌 정확한 값을 얻을 수 있다.

그리디

• 현재 상황에서 현재 당장 가장 좋은 것만 고르는 것이다.
• 당장의 좋은 것만 선택하는 것이 꼭 최적의 해를 도출하지는 않을 수 있기 때문에, 당장의 좋은 것만 반복적으로 선택해도 최적의 해를 구할 수 있는지 정당성을 생각하는 것이 중요하다.
  • ex, 동전 문제: 액수가 큰 동전의 액수가 작은 동전의 액수의 배수일 때만 그리디가 정당(500, 100, 50)
• 그리디 알고리즘이 활용되는 문제들의 특징은 다음과 같다.
  • 문제의 성질이 동일하게 보존된다.
  • 같은 전략을 반복적으로 취할 수 있어야 한다.(이전의 최적의 선택이 이후의 최적의 선택에 영향을 주지 않음(독립적))
  • 부분에 대한 최적의 해가 전체의 최적의 해를 만족한다.

분할 정복

• 분할 정복은 말 그대로 분할과 정복으로 나눠서 해결하는 기법이다. 문제가 작아지면 작아질수록 풀기 쉬워지는 성질을 이용한 것이다. 따라서 대체로 분할 정복은 재귀 호출과 잘 사용된다.
• 분할 정복이 유용하게 사용되는 경우는, 그냥 풀었을 때보다 이미 풀린 분할된 부분 문제들을 합치는 것이 더 빠른 경우이다. 그 예로 변합 정렬, 이분 탐색, 거듭제곱 연산 등이 있다.

DFS/BFS

• BFS는 넓이 우선 탐색으로 큐(Queue)를 사용하고, DFS는 깊이 우선 탐색으로 재귀를 사용한다.
• BFS와 DFS의 시간복잡도는 O(V+E)이다. 이때 V는 노드의 개수, E는 간선의 개수이다.

플로이드

• 최단 경로 알고리즘으로, 3중 for문 형태로 시간 복잡도는 O(N^3)이다.
• 최단 경로를 저장하는 2차원 배열(dist[][])을 준비하고, 자기 자신으로 가는 dist[i][i]는 0으로, 나머지는 무한 값으로 초기화해준다. (문제에 따라서 자기 자신으로 이동이 안될 수 있는데, 그때는 dist[i][i]도 무한 값으로 초기화한다.)
• i에서 j로 이동할 때, k를 거치지 않는 경우와 k를 거치는 경우를 비교해서 최단 거리를 갱신해준다. 모든 정점을 k라고 두어서 순차적으로 갱신해주면 된다. 

정렬 알고리즘

참고: https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4

• 선택 정렬
  • 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.
  • 시간 복잡도: O(N^2)
• 삽입 정렬
  • 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
  • 시간 복잡도: O(N^2), 데이터가 거의 정렬되어 있는 상태이면 매우 빠르게 동작한다. 
• 퀵 정렬
  • 기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.
  • 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.
  • 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터로 설정한다.
  • 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN) (너비 * 높이 = N * logN)을 기대할 수 있다.
  • 하지만 최악의 경우 O(N^2)의 시간 복잡도를 갖는다.
• 계수 정렬
  • 특정 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다.
  • 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.
  • 데이터 개수가 N, 데이터 중 최댓값이 K일 때 최악의 경우에도 시간 복잡도 O(N + K)를 보장한다.
  • 계수 정렬은 때에 따라 심각한 비효율성을 초래할 수 있다. (ex, 데이터가 0과 999,999로 단 2개만 존재하는 경우)
  • 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적이다.

정렬 알고리즘	평균 시간 복잡도	공간 복잡도	특징
선택 정렬	O(N^2)	O(N)	아이디어가 매우 간단하다.
삽입 정렬	O(N^2)	O(N)	데이터가 거의 정렬되어 있을 때 가장 빠르다.
퀵 정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합하며 빠르다.
계수 정렬	O(N + K)	O(N + K)	데이터 크기가 한정되어 있는 경우에만 사용이 가능하지만 매우 빠르다.

이진 탐색

이진 탐색은 정렬 후 최대값, 최소값, 중간값을 활용하는 탐색 기법이다. 탐색 범위가 크면 이진 탐색을 떠올리자.

Upper Bound / Lower Bound

참고: https://m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=221045300639&proxyReferer=https:%2F%2Fwww.google.com%2F 

 

이진 탐색을 이용한 알고리즘으로 Upper Bound와 Lower Bound가 있다. 원하는 값을 못 찾았을 때 -1 등을 반환하는 이진탐색과는 달리, UpperBound와 LowerBound는 원하는 값을 초과하는 첫번째 위치, 원하는 값 이상의 첫번째 위치를 반환한다.

 

정렬된 배열에서 찾고자 하는 값 target이 있을 때 UpperBound와 LowerBound는 다음과 같다.

• Upper Bound: target보다 큰 첫번째 위치 (초과)
• Lower Bound: target과 같거나 큰 첫번째 위치 (이상)

예를 들어 배열 {1, 3, 3, 5, 7}이 있을 때

• target이 3이면, Upper Bound는 인덱스 2이고 Lower Bound는 인덱스 1이다.
• target이 2이면, Upper Bound는 인덱스 1이고 Lower Bound도 인덱스 1이다.

좌표 압축

주어진 수들의 크기 순서만 중요할 때, 그 수들을 인덱스로 사용할 때, 인덱스로 압축하는 방법이다.

• ex, 30, 20, 10, 40 ➡️ 2, 1, 0, 3
  • 기존 배열(30, 20, 10, 40)을 정렬한 새로운 배열을 만든다. (10, 20, 30, 40)
  • 기존 배열 값들을 새로운 배열에서 이분 탐색하여 인덱스를 구한다. (2, 1, 0, 4) (시간 복잡도: O(N * logN))

다익스트라

• 다익스트라는 비용이 음수일 때는 사용할 수 없다.
• O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 한다. 따라서 전체 시간 복잡도는 O(V^2)이다.
  • 따라서 일반적으로 코딩 테스트의 최단 경로 문제에서 전체 노드의 개수가 5,000개 이하라면 다익스트라를 사용할 수 있다.
• 우선순위 큐를 사용하면 최적화를 할 수 있다.
  • 우선 순위 큐를 구현하기 위해 사용되는 자료구조는 힙이다. 힙은 삽입 시간이 O(logN), 삭제 시간이 O(logN)이다.
  • 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 우선순위 큐를 사용한다. 
  • 우선순위 큐를 사용하면 O(ElogV)의 시간 복잡도를 갖는다.
    • 노드를 하나씩 꺼내서 반복문을 진행할 때는 노드의 개수 V 이상으로 수행되지 않는다. 
    • 우선순위 큐에서 꺼낸 노드와 이어진 다른 노드들을 확인하는 횟수는 최대 간선 개수 E만큼 수행된다. 
    • 따라서 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 빼는 연산과 유사하다. 따라서 O(ElogE)로 판단할 수 있다. 
    • 그리고 중복 간선을 포함하지 않는다면, O(ElogV)로 판단할 수 있다. (O(ElogE) ➡️ O(ElogV^2) ➡️ O(2ElogV) ➡️ O(ElogV))

벨만 포드 알고리즘

• 벨만 포드는 음의 간선이 포함된 상황에서도 최단 거리를 구할 수 있다.
• 음수 간선의 순환을 감지할 수 있다.
• 시간 복잡도: O(V*E)
• 벨만 포드 알고리즘의 실행 순서
  1. 출발 노드를 설정한다.
  2. 최단 거리 테이블을 초기화한다.
  3. 다음 과정을 N - 1번 반복한다.
     1. 전체 간선 E개를 하나씩 확인한다.
     2. 각 간선을 거쳐서 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
  4. 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행한다. 이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.
• 다익스트라 알고리즘과 비교
  • 다익스트라
    • 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
    • 음수 간선이 없는 경우에만 최적의 해를 찾을 수 있다.
  • 벨만 포드
    • 매번 모든 간선을 전부 확인한다. 따라서 벨만 포드는 다익스트라에서의 최적의 해를 항상 포함한다.
    • 다익스트라에 비해서 시간이 오래 걸리지만, 음수 간선 순환을 감지할 수 있다.