한재원

한재원

🛠️ 저는 커서 백엔드 개발자가 될래요!

[알고리즘] 기타 알고리즘

Updated: Categories:

기타 다양한 알고리즘에 대해 알아보자 (feat. 이분탐색, 탐욕법, 동적계획법, 최단경로, 최소비용)

  • 시간복잡도 : O(logN)
  • 범위를 두 부분으로 분할하여 탐색하는 방식
  • 반드시 데이터가 정렬되어 있어야 한다
  • left, right 포인터의 중앙값인 mid를 탐색하고 포인터를 이동시킨다


탐욕법 (Greedy)

  • 시간복잡도 : 매번다름
  • 현재의 상황에서 가장 최선의 선택을 하는 알고리즘
    • 매순간 최선의 선택을 했을때 최적해가 나온다는 것이 보장되어 있어야 함.


동적계획법 (Dynamic Programming)

  • 시간복잡도 : 매번다름
  • 문제 해결과정의 결과들을 저장하여 중복된 행위를 줄이는 알고리즘
    • 부분 문제의 최적 결과값을 사용해 전체 문제의 최적 결과를 낼 수 있어야 함
    • 보통 dp 배열에 결과를 저장하면서 풀어낸다.
  • 두가지 방식을 사용한다
    • Top-Down : 재귀를 사용하여 dp를 끝부터 채운다
    • Bottom-Up : for문을 사용하여 dp를 처음부터 채운다


그래프 - 탐색

  • 시간복잡도 : O(V+E)
  • 큐를 사용해 구현
  • 탐색 값이 그래프 중간에 있는 경우 유리함
  • 시간복잡도 : O(V^2)
  • 스택이나 재귀를 사용해 구현
  • 탐색 값이 그래프 끝에 있는 경우 유리함

백트래킹 (Back Tracking)

  • DFS중 불필요한 경로는 가지 않고 되돌아 가는것
    • 이를 가지치기(pruning)이라고 함


그래프 - 최단경로

다익스트라 (Dijkstra)

  • 시간복잡도 : O(E*logV)
  • 하나의 시작정점이 주어질 때 다른 정점으로의 최단거리를 구하는 알고리즘
  • 음수인 가중치를 포함한다면 사용할수 없음
  • 동적계획법과 우선순위큐를 사용한 BFS로 구현한다
    1. 정점의 최소거리를 저장하는 distance 배열을 만듬
    2. 초기값은 INF로 채운다
    3. 현재 정점의 인접정점을 하나씩 방문큐(우선순위큐)에 넣고 거리를 배열에 업데이트한다
      • 업데이트시 (현재 정점의 누적거리) + (인접정점까지의 거리)가 인접정점의 누적거리보다 작아야 함
    4. 큐에서 다음 방문할 정점을 꺼내고 방문
    5. 큐가 빌때까지 반복
  • 우선순위큐를 사용하는 이유
    • 방문예정큐는 현재 정점과의 거리를 기준으로 오름차순 정렬함

플로이드-와샬 (Floyd-Warshall)

  • 시간복잡도 : O(V^3)
  • 모든 정점에서 다른 정점으로의 최단거리를 구하는 알고리즘
  • 음수인 가중치를 포함해도 사용가능
  • 최단거리를 저장하는 2차원배열과 3중 for문으로 구현한다
    1. 최단거리 배열을 초기화한다
      • 인접정점간 간선 가중치를 저장함.
      • 자기 자신이면 0, 인접하지 않으면 INF
    2. 중간 방문정점 k를 모두 순회하며 시작정점 -> k -> 도착정점의 거리를 구해 업데이트한다
      • 만약 방문하는 것이 더 효율적이라면 업데이트


그래프 - 최소비용신장트리 (Minimum-cost Spanning Tree)

  • 가중치 무방향 그래프에서 사용됨
  • 모든 정점을 연결할때, 최소 비용으로 연결하는 모든 방법을 찾는 알고리즘

크루스칼 (Kruskal)

  • 시간복잡도 : 정렬알고리즘에 좌우됨
  • 간선을 기준으로 트리를 구성하는 방식
  • 탐욕법과 리스트를 사용해 구현함
    1. 그래프의 모든 간선 가중치 리스트를 정렬한다
    2. 가중치 리스트 순서대로 간선을 추가하며 트리를 구성한다
    3. 만약 간선 추가시 사이클이 생기게 되면 이를 회피한다
      • 사이클 발생 여부는 Union-Find 알고리즘을 통해 검사한다
  • 간선이 적을때 적합함 (정렬할게 적기때문에)

프림 (Prim)

  • 시간복잡도 : O(V^2), O(E*logV)(우선순위큐 사용시)
  • 정점을 기준으로 트리를 구성하는 방식
  • 탐욕법과 우선순위큐를 사용해 구현함
    1. 시작 정점을 지정함 (랜덤하게 지정해도 결과는 같다)
    2. 현재 정점과 인접한 정점들을 우선순위큐(가중치 우선)에 넣는다
    3. 우선순위큐에서 다음 방문할 정점을 poll
      • 만약 사이클이 만들어진다면 다음 정점을 poll
    4. 반복
  • 간선이 많을때 적합함