[알고리즘] 탐색, 순회, 검사, 경로

사전 탐색

• 탐색
  • key와 연관된 데이터 원소를 반환하는 것
  • 사전을 구현하는 가장 큰 목적이다.

1. 선형탐색

• 전체를 하나씩 돌며, 해당하는 key를 찾으면 반환
• 시간복잡도 : O(n)
• 공간복잡도 : O(1) - 입력 데이터구조에 대해 읽기 작업만 수행

2. 이진탐색

• 가운데 원소와 비교해서 좌우 하나를 선택하는 과정을 재귀적으로 수행한다.
• 입력이 순서리스트일 때 가능하다.
• 시간복잡도
  • 배열로 구현 시 : O(log n)
  • 연결리스트로 구현 시 : O(n) - 가운데 위치로 접근하는데만 O(n) 시간 소요

---

그래프 순회

• 인접 리스트로 구현 기준

1. 깊이 우선 탐색(DFS)

• 전위순회(=선위순회)와 유사

• 방식

  • 특정 정점을 조사하는 과정
    • 인접 정점들을 조사해서 안 가본 곳이 있으면 방문해서, 해당 저점을 조사한다(재귀)
    • 반환되면, 다음 인접 정점을 조사한다.
    • 더이상 갈 인접 정점이 없으면 반환한다.
  • 더이상 조사할 정점이 없을 때까지 반복한다.

• DFS에 의해 라벨된 간선들은 신장트리(DFS tree)가 된다.
  (모든 정점을 방문했고, 사이클은 없다.)

• 시간복잡도 : O(n+m)

  • n은 정점 수, m은 간선 수
  • 각 정점 2번 라벨(fresh, visited) - 2n
  • 각 간선 2번 라벨(fresh, tree/back) - 2m
  • 각 정점별로 incidentEdges(부착 간선 모두 호출) 1번 호출 - m

• 응용

  • 경로 찾기(최단 경로 x)
  • 이중 연결 요소

2. 넓이 우선 탐색(BFS)

• 레벨순회와 유사
• 방식
  • 큐와 while문 이용
  • 한 바퀴 돌 때마다 하나씩 큐에서 반환
  • 큐에서 하나를 반환할 때 마다, (아직 방문하지 않은) 인접 정점들을 큐에 삽입
• BFS에 의해 라벨된 간선들을 신장트리(BFS tree)가 된다.
• 시간복잡도 : O(n+m)
  • n은 정점 수, m은 간선 수
  • 각 정점 2번 라벨(fresh, visited) - 2n
  • 각 간선 2번 라벨(fresh, tree/cross) - 2m
  • 각 정점별로 리스트(큐)에 한 번 삽입 - m
• 응용
  • 최단 경로 찾기

---

그래프 검사

1. 강연결성 검사

• 강연결성 : 모든 정점에서 다른 모든 정점으로 도달가능하다.
  • 도달가능성 : 두 정점 사이에 방향경로가 존재한다.
• 그래프 G의 강연결성 검사 방법
  • G의 임의의 정점 v에서 DFS 수행
  • 모든 정점을 방문하지 않은 경우 : False 반환하고 종료
  • 모든 정점을 방문 했다면 : 간선을 모두 역행시킨 G'에서 DFS 수행
  • 모든 정점을 반문했다면 True, 아니라면 False 반환하면 종료
• 시간복잡도 : O(n+m)

---

최단경로 구하기

• 아래 2가지 모두 동적 프로그래밍 기법

이진탐색 vs 분할통치 vs 동적프로그래밍

• 이진탐색 : 이등분된 양쪽 범위 중 한쪽만 고려
• 분할통치 : 이등분해서 subproblem 2개 만든 후, 양쪽 각각에 대해 동일한 작업 수행(양방향)
• 동적 프로그래밍 : 앞서 계산한 결과의 내용을 뒤에 활용. 반복적으로 동일 작업 수행

1. Floyd-Warshall 알고리즘(플로이드 와샬/워셜)

• 모든 정점 간의 상호 최단 경로 구하기
• 이행적 폐쇄 구하기에도 사용 가능
  • 이행적 폐쇄 : 방향경로가 존재하면, 모두 직행 간선이 존재하는 그래프
  • 1번 정점을 다리로 하면, 방향 간선이 없는 두 정점 사이에 방향 경로가 존재하면, 두 정점 사이에 간선 삽입
  • 모든 정점을 기준(다리)로 동일 작업 반복
  • 시간복잡도 : O($n^3$)
    • 모든 정점을 기준(다리)k로(n), 모든 다른 정점을 start로(n), 그외 모든 정점을 end로(n)
• 실행방법
  • 모든 정점 간의 간선의 가중치를 최소거리로 표시
  • 1번 정점을 거치면, 기존 최소 거리보다 짧은 경로가 생긴다면, 최소 경로 갱신
  • 모든 정점에 대해 같은 작업 반복

2. Dijkstra 알고리즘(다익스트라 알고리즘)

• 출발 정점 기준으로 최단 경로 구하기

1. 출발 정점으로부터 다른 모든 정점까지의 거리 담기(연결 안되면 INF 무한)
2. 출발 정점에서 가까운 정점을 선택한다.
3. 기존 거리와 선택한 정점을 거쳐서 가는 거리를 비교해서, 짧은 것을 선택한다.
4. 위 과정을 모든 정점이 선택될 때까지 반복한다.

시간복잡도 : O(m log n)

---

최소신장트리(MST) 구하기

• 아래의 3가지 알고리즘 모두, 탐욕적 선택 속성이 증명된 알고리즘이다.
  • 탐욕적 선택 속성 : 탐욕법 통해 최적해를 구할 수 있다
  • 탐욕법 : 항상 그때 선택 가능한 것 중 최적의 것부터 차례로 선택
    • 잔돈 거스트기, 배낭문제 등은 탐욕적 선택 속성 x
    • 부분적 배낭 문제(선택한 항목의 부분만 가져가도 괜찮음)은 탐욕법으로 최적해 가능
    • NP 완전문제(항목 늘어나며 갑자기 느려짐, x의 모든 조합 구하기, 모든 버전 계산 필요)는 근사 알고리즘(ex. 탐욕법)을 쓰는 게 좋다.

1. Prim-Jarnik 알고리즘 (프림 알고리즘)

1. 임의의 정점1개를 배낭에 넣고 시작
2. 배낭 속 정점에서, 배낭 밖 정점으로 이어지는 모든 간선 중 가중치를 가진 간선을 선택한다.
   해당 간선과 연결관 정점은 배낭으로 들어온다.
3. 모든 정점이 배낭에 들어올 때까지 2번을 반복한다.

• 시간복잡도 : O($n^2$)
  • 주 반복문 n, 내부 반복문 n
  • 이진 힙/피보나치 힙 + 인접 리스트 사용 시, O(n log n) 정도까지 떨어질 수 있는 듯 하다.

2. krustal 알고리즘 (크루스칼 알고리즘)

1. 모든 간선들을 오름차순으로 정렬한다.
2. 사이클을 형성하는 간선을 제외하고, 앞에서부터 하나씩 MST에 간선을 추가한다.
   • 선택된 간선으로 연결된 정점들은 하나로 묶어 생각한다.(부모 노드가 같다고 생각한다.)
   • 새로운 간선의 양쪽 정점이 묶여 있으면(부모 노드가 같으면) 사이클을 형성하는 간선이다.
3. 2의 과정을 모든 간선이 하나의 배낭에 들어갈 때까지 반복한다.

• 시간복잡도 : O(m log m) - 간선을 정렬하는 시간

3. Baruvka 알고리즘(보루프카 알고리즘), Sollin 알고리즘

1. 모든 정점에서 각각 가장 가중치가 작은 간선을 마크한다.
   1) 마크된 간선 양쪽의 정점은 하나로 묶는다.
   2) 중복간선이 생기면 하나만 마크한다.
2. 위 과정을 모든 정점이 연결될 때까지 반복한다.

• 시간복잡도 : O(m log n)
  • 1회전마다, 정점들 별로 간선 조사 - 모든 간선들 2번씩 조사 : O(m)
  • 최전 마다 배낭 수는 최소 절반으로 줄어든다. - 총 반복회수 : O(log n)