Approach

(1) Greedy: 정당성 검증

(2) DP: 최적 부분 구조, 부분 문제 중복

(2) Divide & Conquer: 최적 부분 구조 only, 특정 조건을 만족하는 최적값?

(2) Parametric Search: 결정함수 이분화, 조건함수 단조함수

(3) DFS: 모든 경로 탐색, 스택으로 구현

(3) BFS: 최단거리 탐색, 단계별 정점 탐색, 큐로 구현

1. Greedy

• 그리디 알고리즘(탐욕법)은 현재 상황에서 당장 좋은것만 고르는 방법을 의미한다.
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
• 해당 알고리즘에서는 그 정당성 분석이 중요하다.
  • 단순히 가장 좋은것을 반복적으로 선택해도 최적의 해를 찾을(보장할) 수 있는지 검토해야 한다.
• 코테에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.
  • ex) 거스름 돈 문제(작은 단위의 동전을 종합하여 다른 해가 나올 수 없기 때문)

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

• 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단경로를 계산한다.
• 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다.
  • 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다.
• 다익스트라 최단경로 알고리즘은 그리디 알고리즘으로 분류된다.
  • 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.
• 알고리즘의 동작과정은 다음과 같다.
  1. 출발 노드를 설정한다.
  2. 최단 거리 테이블을 초기화 한다.
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. (그리디 알고리즘)
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다.
  5. 위 과정에서 3번과 4번을 반복한다.
• 알고리즘의 특징은 다음과 같다.
  • 그리디 알고리즘: 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.
  • 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다.
    • 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.
  • 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단거리 정보가 저장된다.
    • 완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야 한다.
• 총 $O(V)$번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 한다.
• 따라서 전체 시간 복잡도는 $O(V^2)$이다.
• 일반적으로 코딩 테스트의 최단 경로 문제에서 전체 노드의 개수가 5000개 이하라면 이 코드로 문제를 해결할 수 있다.

2. Implementation (완전탐색, 시뮬레이션)

• 완전탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결방법 <- 확인(탐색)해야 할 전체 데이터의 개수가 100만개 이하일 때
• 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례로 수행해야 하는 문제 유형
• ex) 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• ex) 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• ex) 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• ex) 적절한 라이브러리를 찾아서 사용해야 하는 문제
• ex) 모든 순열과 조합을 찾아야 하는 문제
• 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향백터가 자주 활용된다.

// 동, 북, 서, 남
dx = {0, -1, 0, 1}; // 행
dy = {1, 0, -1, 0}; // 열

// 현재 위치
x, y = 2, 2

for (i = 0; i < 4; ++i)
{
	// 다음 위치 // 동북서남 탐색
	nx = x + dx[i];
	ny = y + dy[i]
	print(nx, ny);
}