한빛미디어3 [알고리즘 개념 정리] 다익스트라 최단 경로 알고리즘 (Python) [이것이 코딩 테스트다 with Python] 30강 다익스트라 최단 경로 알고리즘을 듣고 정리한 내용입니다. 최단 경로 알고리즘 - 가장 짧은 경로를 찾는 알고리즘을 의미한다. - 다양한 문제 상황 1. 한 지점에서 다른 한 지점까지의 최단 경로 2. 한 지점에서 다른 모든 지점까지의 최단 경로 3. 모든 지점에서 다른 모든 지점까지의 최단 경로 - 각 지점은 그래프에서 노드로 표현한다. - 지점 간 연결된 도로는 그래프에서 간선으로 표현한다. 다익스트라 최단 경로 알고리즘 - 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. - 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. - 현실 세계의 도로(간선)는 음의 간선으로 표현되지 않는다. .. 2024. 3. 28. [알고리즘 개념 정리] 다이나믹 프로그래밍 (Python) [이것이 코딩 테스트다 with Python] 28강 다이나믹 프로그래밍 개요를 듣고 정리한 내용입니다. 다이나믹 프로그래밍 (= 동적 계획법) - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. - 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 메모이제이션 : 한번 계산한 결과를 메모리 공간에 메모하는 기법이다. 즉, 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다. 값을 기록해 놓는다는 점에서 캐싱이라고도 한다. - 다이나믹 프로그래밍의 구현은 일반적으로 2가지 방식(top-down과 bottom-up)으로 구성된다. top-down(메모이제이션) 방식 (=하향식): 재귀함수를 이용함 bottom-up 방식 (=상향식): 반복문을.. 2024. 3. 27. [알고리즘 개념 정리] 플로이드 워셜 (Python) [이것이 코딩 테스트다 with Python] 31강 플로이드 워셜 알고리즘을 듣고 정리한 내용입니다. 플로이드 워셜 알고리즘 - 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘이다. - (다익스트라 알고리즘과 마찬가지로) 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다만, 다익스트라 알고리즘과 달리 매 단계마다 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾는 과정이 필요하지 않다. - 2차원 테이블에 최단거리 정보를 저장한다. - 다이나믹 프로그래밍 유형에 속하며, 시간 복잡도는 O(n³)이다. - 노드의 갯수가 적은 경우에 사용이 적합하며, 노드와 간선의 갯수가 많은 경우에는 다익스트라 알고리즘을 활용해야하는 경우가 많다. 실제로도 .. 2024. 3. 25. 이전 1 다음
