우주의WouldYou

출처: www.youtube.com/watch?v=acqm9mM1P6o

<최단 경로 문제>

- 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘

- 다양한 문제 상황

    1. 한 지점에서 다른 한 지점까지의 최단 경로

    2. 한 지점에서 다른 모든 지점까지의 최단 경로

    3. 모든 지점에서 다른 모든 지점까지의 최단 경로

- 각 지점(국가, 마을, 도시등)은 그래프에서 노드로 표현

- 지점 간 연결된 도로는 그래프에서 간선으로 표현

- 기본적으로 dp로 분류됨

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

- 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.

- 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작

    - 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다.

- 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류

    - 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복

<다익스트라 최단 경로 알고리즘 동작 과정>

- 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있음

- 처리 과정에서 더 짧은 경로를 찾으면 '이제부터는 이 경로가 제일 짧은 경로야'라고 갱신

현재값, 갱신된 값, 갱신 여부

<특징>

- 그리디 알고리즘: 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정 반복

- 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음

    : 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해

- 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장

    : 완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야 한다.

<간단한 구현 방법>

1. 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인(순차탐색)한다.

#python dijkstra
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미, 10억 설정

n, m = map(int, input().split()) #노드 개수, 간선개수 입력 받기

start = int(input()) # 시작 노드 번호 입력 받기

graph = [[] for i in range(n+1)] # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트(연결리스트 형태로 그래프 초기화)

visited = [False] * (n+1)# 방문한 적이 있는지 체크하는 목적의 리스트 만들기

distance = [INF] * (n+1) # 최단거리 테이블을 모두 무한으로 초기화

for _ in range(m): # 모든 간선 정보 입력
    a, b, c = map(int, input().split())
    
    graph[a].append((b, c)) # a번 노드에서 b번 노드로 가는 비용이 c라는 의미(묶어서 넣어준다)

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드 반환
def get_smallest_node():
    min_value = INF
    index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
     return index
     
 def dijkstra(start):
     # 시작 노드에 대해 초기화
     distance[start] = 0 
     visited[start] = True
     for j in graph[start]:
         distance[j[0]] = j[1]
         
     for i in range(n-1): #시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
         now = get_smallest_node() # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
         visited[now] = True
         for j in graph[now]: #현재 노드와 연결된 다른 노드 확인
             cost = distance[now] + j[1]
             if cost < distance[j[0]]: #현재 노드를 거쳐 다른 노드로 이동하는 거리가 더 짧은 경우
                 distance[j[0]] = cost

#다익스트라 알고리즘 수행
dijkstra(start)

#모든 노드로 가기 위한 최단 거리 출력
for i in range(1, n+1):
    if distance[i] == INF: #도달할 수 없는 경우, 무한 출력
        print("INFINITY")
    else:
        print(distance[i]) #도달 가능한 경우 거리 출력

#c++ dijkstra

int n, m, start;
vector<pair<int, int>> graph[100001]; //각 노드에 연결되어 있는 노드에 대한 정보를 담은 배열

bool visited[100001]; //방문한 적이 있는지 체크하는 목적의 배열 만들기
int d[100001]; //최단거리 테이블

//방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
int getSmallestNode(){
    int min_value = INF;
    int index = 0;
    for(int i = 1; i <=n; i++){
        if(d[i] < min_value && !visited[i]){
            min_value = d[i];
            index = i;
        }
    }
    return index;
}

void dijkstra(int start){
    //시작 노드에 대해 초기화
    d[start] = 0;
    visited[start] = true;
    for(int j=0; j < graph[start].size(); j++)
        d[graph[start][j].first] = graph[start][j].second;
    // 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
    for(int i=0;i < n-1; i++){
        //현재 상태를 기준으로, 최단 거리가 가장 짧은 노드를 꺼내서 방문처리
        int now = getSmallestNode();
        visited[now] = true;
        //현재 노드와 연결된 다른 노드를 확인
        for(int j=0; j < graph[now].size(); j++){
            int cost = d[now] + graph[now][j].second;
            //현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if (cost < d[graph[now][j].first]) 
                d[graph[now][j].first] = cost; //갱신
         }
     }
 }
 
 int main(){
     cin >> n >> m >> start;
     
     //모든 간선 정보 입력
     for(int i=0; i < m ; i++){
         int a, b, c;
         cin >> a>> b>> c;
         //a번 노드에서 b번 노드로 가는 비용이 c라는 의미
         graph[a].push_back({b, c})
     }
     
     
     //최단 거리 테이블을 모두 무한으로 초기화
     fill_n(d, 100001, INF);
     //알고리즘 수행
     dijkstra(start);

     for(int i= 1; i <=n; i++){
         if (d[i] == INF)
             cout << "INFINITY"<<endl;
         else
             cout << d[i] << endl;
     }
}

<다익스트라 알고리즘: 간단한 구현 방법 성능 분석>

- 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 함

- 따라서 전체 시간 복잡도는 O(V2)

- 일반적으로 코딩 테스트의 최단 경로 문제에서 전체 노드의 개수가 5000개 이하라면 이 코드로 문제 해결 가능

    : 노드의 개수가 10000개가 넘어간다면???? 1억번 이상의 연산일텐데.....

--> 이를 위해 우선순위 큐 자료구조를 이용한다!

<우선순위 큐(Priority Queue)>

- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

- 예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우 우선순위 큐 이용 가능

<힙(Heap)>

- 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나

- 최소 힙(Min Heap, 값이 낮은 데이터부터 꺼냄)과 최대 힙(Max Heap, 값이 높은 데이터 부터 꺼냄)이 있음

[리스트로 우선순위 큐 구현]

- 삽입 시간 O(1), 삭제 시간 O(N)

[힙으로 우선순위 큐 구현]

- 삽입 시간 O(log N), 삭제 시간 O(log N)

[파이썬 힙 라이브러리]

최악의 경우에도 O(NlogN)보장

# python 최소 힙

import heapq

#오름차순 힙 정렬
def heapsort(iterable):
    h = []
    #모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
        # heapq.heappush(h, -value) #최대 힙
    
    #힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
        # result.append(-heapq.heappop(h)) #최대 힙
    return result


result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조를 이용

- 다익스트라 알고리즘이 동작하는 기본 원리는 동일하다

    : 현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 추가적으로 이용한다는 점이 다름

    : 현재의 최단 거리가 가장 짧은 노드를 선택해야하므로 최소 힙을 사용

[우선순위 큐를 사용한 다익스트라 알고리즘 동작 과정]

<개선된 다익스트라>

#python dijkstra, developed

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split()) # 노드 개수, 간선 개수

start = int(input()) #시작 노드

graph = [[] for i in range(n+1)] #각 노드에 연결 되어 있는 노드에 대한 정보를 담는 리스트
distance = [INF] * (n+1)#최단 거리 테이블을 무한으로 초기화

for _ in range(m): #모든 간선 정보 입력
    a, b, c = map(int, input().split())
    graph[a].append((b, c)) #a->b, 비용 c
    
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) #시작 노드로 가기 위한 최단 거리는 0으로 설정하여, 큐에 삽입
    distance[start] = 0
    while q: #큐가 비어있지 않다면
        dist, now = heapq.heappop(q) #가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        if distance[now] < dist: #현재 노드가 이미 처리된 적 있는 노드라면 무시(방문 테이블을 따로 두지 않음)
            continue
        for i in graph[now]: #현재 노드와 연결된 다른 인접한 노드들 확인
            cost = dist + i[1]
            #현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("infinity")
    else:
        print(distance[i])

//c++ dijkstra, developed
#define INF 1e9

int n, m, start;
vector<pair<int, int>> graph[100001]; //간선 정보
int d[100001]; //최단 거리 테이블

void dijkstra(int start){
    priority_queue<pair<int, int>> pq; //우선순위 큐(최소 비용 값, 노드번호), 최대힙으로 구성되어있음
    
    pq.push({0, start}); //시작 노드로 가기위한 최단 경로는 0으로 설정하여 큐에 삽입
    d[start] = 0;
    while(!pq.empty()){
        //가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        int dist = -pq.top().first; //현재 노드까지의 비용, 최대힙으로 구성되어 있기 때문에 -
        int now = pq.top().second; //현재 노드
        
        pq.pop();
        
        if(d[now] < dist) continue; //현재 노드가 이미 처리된 적 있는 노드라면 무시
        
        //현재 노드와 연결된 다른 인접한 노드들을 확인
        for(int i= 0; i < graph[now].size(); i++){
            int cost = dist + graph[now][i].second;
            //햔재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if( cost < d[graph[now][i].first] ) {
                d[graph[now][i].first] = cost;
                pq.push(make_pair(-cost, graph[now][i].first));//최대힙으로 구성되어 있기 때문
            }
        }
    }
}
                
           
int main(){
    cin >> n >> m >> start;
    //모든 간선 정보 입력
    for(int i=0;i < m; i++){
        int a, b, c;
        cin >> a>> b>> c;
        graph[a].push_back({b,c });   
    }
    
    fill(d, d+100001, INF);
    dijkstra(start);
    
    for(int i =1; i <= n; i++){
        if(d[i] == INF)
            cout << "infinity\n";
        else
            cout << d[i] <<endl;       
    }       
}
                

[개선된 구현 방법 성능 분석]

- 시간복잡도 O(ElogV)

- 노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 V이상의 횟수로는 처리되지 않음

    : 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총횟수는 최대 간선의 개수(E)만큼 연산이 수행될 수 있음

- 직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사

    : 시간복잡도를 O(ElogE)로 판단할 수 있다.

    : 중복 간선을 포함하지 않는 경우에 이를 O(ElogV)로 정리할 수 있음

        : O(ElogE) -> O(ElogV2) -> O(2ElogV) -> O(ElogV)

출처:www.youtube.com/watch?v=5Lu34WIx2Us

<다이나믹 프로그래밍>

- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

- 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(Top-down(하향식), Bottom-up(상향식))으로 구성

- 동적 계획법이라고도 한다.

- Dynamic?

    (자료구조) 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'

    (알고리즘) 의미없음

- 특정 문제가 다음 조건을 만족할 때 사용 가능

    1. 최적 부분 구조(Optimal Substructure)

      : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음

    2. 중복되는 부분 문제 (Overlapping Subproblem)

      : 동일한 작은 문제를 반복적으로 해결해야 함(부분문제가 중첩되어 반복, 동일한 문제를 반복적으로 해결)

- 문제가 위 조건에 맞는지 확인한 다음 dp적용

ex. 피보나치 수열

-> 재귀로 구현할 경우 지수 시간 복잡도를 가지게 됨(중복되는 문제)

점화식: 인접한 항들 사이의 관계식

<메모아이제이션(하향식, Memoization)>

- dp를 구현하는 방법 중 하나

- 한 번 계산한 결과를 메모리 공간에 메모하는 기법

    : 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다

    : 값을 기록(배열 등에)해 놓는다는 점에서 캐싱(Cacheing)이라고도 한다.

<bottom-up>

- 반복문 이용

- dp의 전형적인 형태

<다이나믹 프로그래밍 vs 분할 정복>

- 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있음

    : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황

- 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복

    : 다이나믹  프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨

    : 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음

<다이나믹 프로그래밍 문제에 접근하는 방법>

- 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요

- 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토할 수 있음

    : 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 DP를 고려해보자

- 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있다.

출처: www.youtube.com/watch?v=94RC-DsGMLo

<이진 탐색 알고리즘>

- 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

- 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

    -> 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정

    -> 로그시간의 시간복잡도를 가짐

[이진 탐색의 시간 복잡도]

- 단계마다 탐색 범위를 2로 나누는 것과 동일 => 연산횟수는  log2N에 비례

- 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장

ex. 초기 데이터 개수 32개

-> 1단계 : 16개가량 데이터 남음, 2단계: 8개 가량의 데이터만, 3단계: 4개 가량의 데이터만

# binary search python

def binary_search_recursion(array, target, start, end): #재귀
    if start > end:
        return None
    mid = (start + end) // 2
    
    if array[mid] == traget: # 찾은 경우 중간점 인덱스 반환
        return mid
    elif array[mid] > target: #중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        return binary_search(array, target, start, mid - 1)
    else: # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        return binary_search(array, target, mid+1, end)

def binary_search(array, target, start, end): # 반복문
    while start <= end:
        mid = (start + end) //2 
        if array[mid] == target: # 찾은 경우 중간점 인덱스 반환
            return mid
        elif array[mid] > target: #중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
            end = mid-1
        else: # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
            start = mid + 1
    return None



# n(원소의 개수)과 target(찾고자 하는 값) 을 입력        
n, target = list(map(int, input().split()))
# 전체 원소 입력
array = list(map(int, input().split()))

result1 = binary_search_recursion(arrat, target, 0, n-1)
result2 = binary_search(arrat, target, 0, n-1)
if result1 == None:
    print ("원소 존재x")
else: 
    print(result1 + 1)

// c++ binary search

int binarySearch(vector<int> &arr, int target, int start, int end){
    while (start <=end){
        int mid = (start + end ) /2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] > target) end = mid -1
        else start = mid + 1;
    }
    return -1;
}

[파이썬 이진 탐색 라이브러리]

- bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환

(C++의 lower bound와 유사)

- bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

(C++의 upper bound와 유사)

from bisect import bisect_left, bisect_right

a  = [1, 2, 4, 4, 8]
x = 4

print( bisect_left(a, x)) #4가 들어갈 첫 위치 2
print( bisect_right(a, x)) #4

[파라메트릭 서치(Parametric Search)]

- 최적화 문제를 결정문제('예' 혹은 '아니오') 로 바꾸어 해결하는 기법

    ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

(범위를 좁혀 나가며 조건에 맞는지 예 아니오로 확인)

- 일반적으로 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결 가능

*최적화 문제: 어떤 함수의 값을 최대한 낮추거나 최대한 높이는 등의 문제

※탐색범위가 클때는 항상 이진 탐색을 떠올려야 한다!

출처: www.youtube.com/watch?v=2zjoKjt97vQ

<그리디 알고리즘(탐욕법)>

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법

- 일반적인 그리디 알고리즘을 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구

- 그리디 해법은 그 정당성 분석이 중요

    -> 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토

- 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음

=> 코테에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제됨

=> 즉, 탐욕법을 사용했을 때 해당 해가 최적의 해가 되는 경우가 많이 출제 된다

<구현: 시뮬레이션과 완전 탐색>

- 구현: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

- 알고리즘 대회에서 구현 유형의 문제란??

    -> 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제

(예시)

1. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제

2.  실수 연산들을 다루고, 특정 소수점 자리까지 출력해야하는 문제

3. 문자열을 특정한 기준에 따라서 끊어 처리해야하는 문제

4. 적절한 라이브러리를 찾아서 사용해야하는 문제(모든 순열, 모든  조합)

==> 많은 연습이 필요!! 라이브러리들을 미리 알고 공부해두는 게 좋음

- 일반적으로 2차원 공간(행렬)에서의 처리를 요구함

왼쪽 위 0,0

- 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용

#동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

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

for i in range(4):
    #다음 위치
    nx= x + dx[i]
    ny =y + dy[i]
    print(nx, ny)