최단 경로 구하기

❓ 다익스트라 알고리즘 풀이방법 정리

1️⃣ 우선순위 큐 구현을 위해 heapq 가져오기

import sys
import heapq

2️⃣ 빠른 입력받기와 최대값 저장을 위해 sys 가져오기

input = sys.stdin.readline
INF = sys.maxsize

3️⃣ 그래프 배열 선언, 입력받기

graph[현재노드] = (거리, 다음노드)

graph = [[] for _ in range(n+1)]
for i in range(e):
    a, b, w = map(int, input().split())
    graph[a].append((w, b))
    graph[b].append((w, a))

4️⃣ 최소 거리 값을 저장하는 memo 배열 선언, heap 배열 선언

def dij(start, end):
    memo = [INF] * (n + 1)
    heap = []

5️⃣ 시작점에서의 memo 배열 저장 & heap에 (0, start) 즉 시작노드 넣기

    memo[start] = 0
    heapq.heappush(heap, (0, start))

6️⃣ heap 배열이 비지 않는 동안 배열에서 (예전거리, 현재노드) 노드 하나씩 꺼내서 각각 저장하기

    while heap:
        prev_weigh, cur_node = heapq.heappop(heap)

7️⃣ 만약 저장되어 있는 memo 배열 현재 노드의 거리가 예전 거리보다 짧다면 밑에 건너뛰기 continue

        if memo[cur_node] < prev_weigh:
            continue

8️⃣ 현재 노드와 연결되어 있는 노드들 순회 (현재거리, 다음노드) 다음거리 = 이전거리 + 현재거리

        for cur_weigh, next_node in graph[cur_node]:
            next_weigh = prev_weigh + cur_weigh

9️⃣ 만약 저장되어 있는 memo 배열 다음 노드의 거리가 다음거리보다 길다면 거리 갱신 memo[다음노드] = 다음거리 heap 배열에 (다음노드, 다음거리) push

            if next_weigh < memo[next_node]:
                memo[next_node] = next_weigh
                heapq.heappush(heap, (next_node, next_weigh))

    return memo[end]

while True:
    mid = (left+right)//2

3️⃣ mid 값을 이용하여 주어진 조건에 만족하는지 체크하기 위한 값 구하기

    count = 0
    for line in lines:
        count += line//mid

4️⃣ left > right 면 반복 끝내고 값 출력

    if left > right:
        print(mid)
        break

5️⃣ 주어진 조건 만족에 따라 left와 right 값을 조절한다

    if count < n:
        right = mid - 1

    else:
        left = mid + 1

예시 문제 BOJ 1654

*📝 임의의 여러 줄 입력받기 * 1️⃣ while True 로 계속 입력받기 2️⃣ try exept 문을 while 문 안에 넣어 예외처리

DP 문제에서 memoziation 배열의 크기를 동적으로 (n) 할당하면 미리 할당해 두는 memo의 경우 (n=2) 에러가 발생한다!

DP에서 memo 배열의 크기는 n의 최댓값으로 설정하자

C++ STL(표준 라이브러리)에 있는 자료구조 컨테이너

1️⃣ 크기가 자동으로 늘어난다 2️⃣ 맨 마지막 위치 이외의 데이터의 삽입, 삭제는 배열과 같은 메커니즘 3️⃣ 인덱스로 각 데이터에 접근 가능

선언

vector<int> A;

// 0이라는 값으로 N개의 원소 할당
vector<int> A(N, 0);

삽입

// push
A.push_back(1);

// 특정 위치 추가
A.insert(A.begin(), 7);
A.insert(A.begin() + 2, 10);

삭제

// pop
A.pop_back()

// 특정 위치 삭제
A.erase(A.begin() + 3);

// 모든 값 삭제
A.clear

// 데이터 개수
A.size()

// 처음, 마지막, 특정 위치 값
A.front()
A.back()
A[3]
A.at(5)

// 데이터의 위치
A.begin()
A.end()

회전

rotate(start, mid, end)
왼쪽으로 2칸씩 회전시키기 위해서는 2번째 인수로 벡터.begin() + 2
오른쪽으로 3칸씩 회전시키기 위해서는 2번째 인수로 벡터.end() - 3

시간복잡도 O(N)

list 에서의 x in s 연산의 평균 시간 복잡도 : O(n) set 에서의 x in s 연산의 평균 시간 복잡도 : O(1)

set 을 사용하자!