글 작성 제목과 내용을 간결하게 정리해 주세요. 제목 내용 <h2>사전 지식 정리</h2><h3>힙 (Heap)</h3><p>우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조</p><ul><li>우선순위가 가장 높은 데이터를 가장 먼저 삭제</li></ul><p>대부분의 프로그래밍 언어에서 우선순위 큐 라이브러리를 지원</p><p>→ 일반적으로 코딩 테스트 환경에서 직접 힙 자료구조부터 작성해서 우선순위 큐를 구현할 일은 없음</p><p>종류</p><ul><li>최소힙<ul><li>값이 낮은 데이터가 먼저 삭제</li></ul></li><li>최대힙<ul><li>값이 큰 데이터가 먼저 삭제</li></ul></li></ul><p>파이썬 라이브러리</p><ul><li>PriorityQueue</li><li>heapq (권장)</li></ul><p><aside> 💡 <strong>최소힙 ←→ 최대힙 변환 사용 팁</strong></p><p><code>-</code> 부호를 이용해 넣고, 빼고 나서 다시 <code>-</code> 적용</p><p></aside></p><h2>최단 경로 (Shortest Path) 알고리즘</h2><h3>정의</h3><ul><li>가장 짧은 경로를 찾는 알고리즘</li><li>‘<strong>길찾기</strong>’ 알고리즘이라고도 불림</li><li>다양한 상황에 맞는 효율적인 알고리즘들이 이미 정립되어 있음</li><li>최단 거리 주요 알고리즘들은 앞서 공부한 <strong>그리디 알고리즘</strong>과 <strong>다이나믹 프로그래밍 알고리즘</strong>이 적용됨<ul><li><strong>최적 부분 구조</strong>를 가짐을 의미</li></ul></li></ul><h3>표현 방법</h3><ul><li>그래프<ul><li>각 지점 : 노드</li><li>각 지점간 연결된 길 : 간선</li></ul></li></ul><h3>대표적 최단 거리 알고리즘 3가지</h3><ul><li><strong>벨만 포드</strong><ul><li>한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 사용</li></ul></li><li><strong>다익스트라</strong> (출제 우세)<ul><li>한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 사용</li><li>그리디 알고리즘</li></ul></li><li><strong>플로이드 워셜</strong> (출제 우세)<ul><li>모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용</li><li>다이나믹 프로그래밍 알고리즘</li></ul></li></ul><h2>다익스트라(Dijkstra) 최단 경로 알고리즘</h2><h3>정의</h3><ul><li>그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘</li></ul><h3>특징</h3><ul><li>최단 경로를 구하는 과정에서 ‘각 노드에 대한 현재까지의 최단 거리’ 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신함<ul><li>이러한 리스트를 <strong>최단 거리 테이블</strong>이라고 함</li></ul></li><li>매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인</li><li>나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 더 짧은 경로로 판단</li><li>따라서 ‘방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 확인’해 그 노드에 대해 최단거리 테이블 갱신을 수행한다는 점에서 <strong>그리디 알고리즘</strong>으로 볼 수 있음<ul><li><strong>가장 짧은 노드를 확인 방법</strong><ul><li>간단한 알고리즘 : <strong>순차 탐색</strong></li><li>개선된 알고리즘 : <strong>우선순위 큐 (최소힙)</strong></li></ul></li><li><strong>시간 복잡도</strong><ul><li>간단한 알고리즘 : <strong>$O(V^2)$</strong> - V:정점 수</li><li>개선된 알고리즘 : <strong>$O(ElogV)$</strong> - E:간선 수, V:정점 수</li></ul></li></ul></li><li>제약 사항</li></ul><p><strong>음의 간선</strong>이 없어야 함 → 현실 세계 길에는 존재 하지 않음</p><p>→ 그럼 어디에? → 예) 연료의 소비</p><h3>동작 과정</h3><ol><li>출발 노드를 설정</li><li>최단 거리 테이블을 초기화</li><li>방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택</li><li>해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신</li><li>위 과정에서 3~4 반복</li></ol><h3>동작 원리 예시</h3><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/ae5eb3db-fef9-4ee8-98b0-f2b20a03a8e3/Untitled.png" alt="Untitled"></p><p><strong>1번 노드에서 다른 노드로 가는 최단 경로는 구하는 경우</strong></p><p>초기 테이블 상태 : 다른 노드로 가는 최단 거리는 ‘무한’, 시작 노드는 0으로 설정</p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/319cca4f-705c-40fa-9728-c0424c747edb/Untitled.png" alt="Untitled"></p><ul><li>파이썬 지수 표기법 무한 사용 : <code>int(1e9)</code></li></ul><p>먼저 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택</p><p>→ 처음에는 시작 노드가 0이므로 시작 노드가 선택됨</p><p>이제 1번 노드를 거쳐 다른 노드로 가는 비용 계산</p><p>→ 1번 노드와 연결된 간선들을 하나씩 확인</p><ul><li>2로가는 비용 : 0 + 2</li><li>3으로 가는 비용 : 0 + 5</li><li>4로 가는 비용 : 0 + 1</li></ul><p>이후의 모든 단계에서도 마찬가지로 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해야 함. 따라서 4번 노드 선택</p><p>→ 4번 노드를 거쳐서 3번과 5번 노드로 가는 최소 비용 계산</p><ul><li>3으로 가는 비용 : 1 + 3</li><li>5로 가는 비용 : 1 + 1</li></ul><p>2번 노드가 선택됨 (2, 5중 번호가 작은 2 선택)</p><p>→ 2번 노드를 거쳐 갈 수 있는 노드는 3번 노드 하나</p><ul><li>3으로 가는 비용 : 2 + 3</li></ul><p>5번 노드 선택</p><p>→ 거쳐 갈 수 있는 노드 : 3, 6</p><ul><li>3으로 가는 비용 : 2 + 1</li><li>6으로 가는 비용 : 2 + 2</li></ul><p>3번 노드 선택</p><p>→ 거쳐 갈 수 있는 노드 : 2, 6</p><ul><li>2로 가는 비용 : 3 + 3</li><li>6으로 가는 비용 : 3 + 5</li></ul><p>6번 노드 선택</p><p>→ 거쳐 갈 수 있는 노드 없음</p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/615157a9-8eaf-4f0e-965e-e5b3c0ce7d1a/Untitled.png" alt="Untitled"></p><p>→ 이렇게 완성된 최단 거리 테이블이 의미하는 것은 1번 노드로 부터 각 노드까지의 최단 거리임</p><p>→ ‘방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택’</p><p>→ 이렇게 선택된 노드는 ‘최단 거리’가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않음</p><p>→ <strong>한 단계당 하나의 최단 거리를 반드시 찾음</strong></p><h3>구현 방법</h3><p>구현하기 쉽지만 느리게 동작하는 코드</p><p>간단한 다익스트라 알고리즘</p><ul><li>시간 복잡도 : $O(V^2)$<ul><li>전체 노드의 수가 5000개 이하 정도의 문제에 적용 가능</li></ul></li><li>구현 방식<ul><li>최단 거리 테이블 : 1차원 배열</li><li>가장 짧은 노드 선택 : <strong>순차 탐색</strong></li></ul></li></ul><p>구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드</p><p>개선된 다익스트라 알고리즘</p><ul><li>시간 복잡도 : $O(ElogV)$</li><li>구현 방식<ul><li>최단 거리 테이블 : 우선순위 큐 (<code>heapq</code>)</li><li>가장 짧은 노드 선택 : <strong>우선순위 큐 이용</strong></li></ul></li></ul><h2>플로이드 워셜(Floyd-Warshall) 알고리즘</h2><h3>정의</h3><ul><li>모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘</li></ul><h3>특징</h3><ul><li>소스코드가 매우 짧아서 다익스트라 알고리즘과 비교해 구현 과정이 어렵진 않음<ul><li>다만, 핵심 아이디어 이해 필요</li></ul></li><li>다익스트라 알고리즘과 같이 단계마다 ‘거쳐 가는 노드’를 기준으로 알고리즘을 수행</li><li>하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요는 없음</li><li>노드의 개수가 N개일 때 알고리즘 상으로 N번의 단계를 수행, 단계마다 O(N^2)의 연산을 통해 ‘현재 노드를 거쳐 가는’ 모든 경로를 고려<ul><li><strong>시간 복잡도</strong> : <strong>$O(N^3)$</strong><ul><li>2차원 리스트를 이용 → <strong>$O(N^2)$</strong></li><li>$O(N^2)$의 과정을 ****N번 수행 → <strong>$O(N^3)$</strong></li></ul></li></ul></li><li>최단 거리 테이블 : <strong>2차원 리스트 이용</strong><ul><li>모든 노드에 대해 다른 모든 노드로가는 최단 거리 정보를 담아야 하기 때문</li></ul></li><li>노드의 개수가 N일 때, N번 만큼의 단계를 반복하며 ‘점화식에 맞게’ 2차원 리스트를 갱신하므로 <strong>다이나믹 프로그래밍</strong>으로 볼 수 있음</li></ul><h3>동작 과정</h3><ul><li>각 단계에서는 해당 노드를 거쳐 가는 모든 경우를 고려</li><li>만약, 1번 노드에 대해서 확인 시 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려<ul><li>정확히는 A → 1번 노드 → B로 가는 비용을 확인한 후에 최단 거리를 갱신</li><li>예)<ul><li>현재 최단 거리 테이블에 <strong>A번 노드에서 B번 노드로 이동하는 비용이 3</strong>으로 기록되어 있을 때, <strong>A번 노드에서 1번 노드를 거쳐 B번 노드로 이동하는 비용이 2</strong>라는 것이 밝혀지면, A번 노드에서 B번 노드로 이동하는 <strong>비용을 2로 갱신</strong></li></ul></li></ul></li></ul><ol><li>알고리즘에서는 <strong>현재 확인하고 있는 노드를 제외</strong>하고, N - 1개의 노드 중에서 <strong>서로 다른 노드 (A, B)쌍을 선택</strong></li><li>A → 1번 노드 → B로 가는 비용을 확인한 후 최단 거리를 갱신</li><li>$_{N-1}P_2$ 개의 쌍을 단계마다 반복해서 확인<ul><li>이 때 $O(_{N-1}P_2)$는 $O(N^2)$이라고 볼 수 있음</li></ul></li></ol><ul><li>점화식 : <code><strong>$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$</strong></code><ul><li>‘<strong>A에서 B로 가는 최소 비용</strong>’과 ‘<strong>A에서 K를 거쳐 B로 가는 비용</strong>’을 비교해 더 작은 값으로 갱신 의미</li></ul></li></ul><h3>동작 원리 예제</h3><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/27146b34-ca48-47ab-9665-7e5d526b3ea5/Untitled.png" alt="Untitled"></p><p>초기 테이블 상태</p><ul><li>연결된 간선 : 해당 값으로 채움</li><li>연결되지 않은 간선 : 무한 (<code>int(1e9)</code>)</li><li>자기 자신 : 0</li></ul><p>단순히 1번 노드를 거쳐가는 경우 고려</p><p>$_3P_2 = 6$ 의 경우에 대해서 고려</p><ul><li>$D_{23} = min(D_{23}, D_{21} + D_{13})$</li><li>$D_{24} = min(D_{24}, D_{21} + D_{14})$</li><li>$D_{32} = min(D_{32}, D_{31} + D_{12})$</li><li>$D_{34} = min(D_{34}, D_{31} + D_{14})$</li><li>$D_{42} = min(D_{42}, D_{41} + D_{12})$</li><li>$D_{43} = min(D_{43}, D_{41} + D_{13})$</li></ul><p>위와 같은 방법으로 2번 노드를 거쳐 가는 경우 고려 계산</p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/8c5ae317-ee12-4dfb-9779-b3baf0eb1dd6/Untitled.png" alt="Untitled"></p><p>3번 노드에 대해 반복</p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/2eb08eab-2f97-4d3c-9bd0-82b682436121/Untitled.png" alt="Untitled"></p><p>4번 노드에 대해 반복</p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/7cea27bc-0bb0-4c61-8f9c-ed6befb5ed4c/Untitled.png" alt="Untitled"></p><p>모든 노드에 대해 반복하였으므로 위의 결과가 모든 노드에 대한 최단 경로 테이블임</p><ul><li><code>$D_{13} = 8$</code> : 1번 노드에서 3번 노드로 가는 최단 거리가 8임을 의미</li></ul><h3>구현</h3><pre><code class="language-python">import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억 설정 # 노드의 개수 및 간선의 개수 입력 n = int(input()) m = int(input()) # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 for a in range(1, n + 1): graph[a][a] = 0 # 각 간선에 대한 정보를 입력받아, 그 값으로 초기화 for _ in range(m): # A에서 B로 가는 비용은 C라고 설정 a, b, c = map(int, input().split()) graph[a][b] = c # 점화식에 따라 플로이드 워셜 알고리즘을 수행 for k in range(1, n + 1): for a in range(1, n + 1): for b in range(1, n + 1): graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) # 수행된 결과를 출력 for a in range(1, n + 1): for b in range(1, n + 1): # 도달할 수 없는 경우, 무한(INFINITY)으로 출력 if graph[a][b] == INF: print("INFINITY", end=" ") # 도달할 수 있는 경우 거리를 출력 else: print(graph[a][b], end=" ") print() </code></pre><h2>그 외 최단 거리 알고리즘</h2><h3>벨만-포드 (Bellman-Ford)</h3><p>가중치 계산과 변경을 모든 간선에 대해 반복 실행</p><p>간선의 가중치가 음수여도 해결 가능</p><p>음의 폐로가 존재 유무 확인 가능</p><ul><li>해당 경로 가중치가 계속 작아지므로 변화가 N회 이상 계속 발생하는 것으로 감지</li></ul><p>방향성 그래프와 비방향성 그래프에 모두 적용 가능</p><p>N회 수행 시점에 N번 이하 이동할 경우의 최단 거리를 구할 수 있음</p><ul><li>N-1회 작업을 수행하면 모든 정점에 대한 최단 경로를 구할 수 있음</li><li>모든 정점 테이블의 값이 변경이 없는 경우도 탐색이 끝난 것임</li></ul><p>파이썬 의사 코드</p><pre><code class="language-python">def bellman_ford(g, w, s): INITIALIZE_SINGLE_SOURCE(g, s) for i in range(1, |g.v| - 1) for 각 간선 (u, v) in g.e: RELAX(u, v, w) for 각 간선 (u, v) in g.e: if v.d > u.d + w(u.v): return False return True </code></pre><p>수행 과정 예시</p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/3e1fd399-ca33-4cc7-a8e9-64dbf883a57f/Untitled.png" alt="Untitled"></p><h3>A* (에이 스타)</h3><ul><li>다익스트라 방법을 발전시킨 알고리즘</li><li>시작점부터의 가중치 뿐만 아니라 현 시점에서 목표까지의 추정 가중치도 함께 고려<ul><li>대략적은 목표 지점의 위치를 알고 있어야 함</li><li>이 추정 가중치를 <strong>발견적 가중치</strong>라고 함</li></ul></li><li>추정 가중치를 통해 목표 지점에서 멀어지는 탐색을 최소화 할 수 있음</li><li>현실에서 최단 가중치를 알고 있는 경우는 없음 → 탐색의 필요가 없음</li><li>게임 프로그래밍에서 적이 플레이어의 움직임을 쫓는 계산 등에 사용</li></ul><h3>존슨 알고리즘</h3><p>모든 쌍 최단 경로를 구함</p><p>벨만-포드와 다익스트라의 서브 루틴을 이용</p><p>가중치 조정 기술 사용</p><p>의사 코드</p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/1d55620a-5e4d-422e-9384-ec6216e46d7a/Untitled.png" alt="Untitled"></p><h2>정리</h2><h3>단일 쌍의 최단 경로 알고리즘</h3><ul><li>벨만-포드<ul><li>음의 가중치도 가능</li><li>음의 폐로 존재 확인 가능</li></ul></li><li><strong>다익스트라</strong><ul><li>그리디를 활용해 벨만-포드보다 효율적</li><li>음의 가중치, 음의 폐로 확인 불가</li></ul></li><li>에이스타<ul><li>다익스트라 방법을 발전시킨 알고리즘 → 현실적 사용 불가</li><li>시작점부터의 가중치 뿐만 아니라 현 시점에서 목표까지의 추정 가중치도 함께 고려</li></ul></li></ul><h3>모든 쌍의 최단 경로 알고리즘</h3><ul><li><strong>플로이드 워셜</strong><ul><li>다이나믹 프로그래밍 활용</li></ul></li><li>존슨<ul><li>플로이드 워셜보다 점근적으로 더 빠름</li><li>정점의 모든 쌍의 최소 경로 가중치의 행렬을 리턴하거나 입력 그래프가 음의 가중치를 가지는 순환을 포함함을 알려줌</li></ul></li></ul><h2>문제 풀이</h2><h2>금주의 문제</h2><p><a href="https://www.acmicpc.net/problem/11404">11404번: 플로이드</a></p> 글 종류 이론 정리 알고리즘 이론에 대한 정리글입니다. 문제 풀이 알고리즘 문제 풀이입니다. 알고리즘 분류 수정 취소