최단거리2 우선순위 큐(최대힙, 최소힙), 다익스트라 알고리즘 1. 최소 힙, 최대 힙 (우선 순위 큐)우선순위 큐 : 들어온 순서와 상관없이 정해진 기준에 따라 값이 먼저 나간다.1-1. 사용법최대 힙 - priority_queue pq;최소 힙 - priority_queue, greater> pq;맨 앞 - pq.top()1-2. 사용 예시최대값 또는 최소값의 빠른 접근 및 삭제가 필요한 경우예를 들어, 데이터 스트림에서 현재까지 입력된 값 중 최대값 또는 최소값을 실시간으로 추적해야 할 때 유용합니다.예시: 주어진 데이터에서 k번째로 큰 요소를 찾아야 하는 경우.동적으로 데이터의 정렬이 필요한 경우리스트나 배열에 요소를 삽입하면서 정렬된 상태를 유지해야 하는 경우에 우선순위 큐가 유리합니다.예시: 정렬된 데이터 스트림에서 새로운 데이터가 추가될 때마다 정렬을 .. 2024. 7. 29. 플로이드 와샬(Floyd-Warshall)알고리즘 최단 거리를 구하는 다양한 알고리즘이 있지만 오늘은 플로이드 와샬의 개념과 구현에 대해서 한번 포스팅 해보려고 한다. 1. 플로이드 와샬 알고리즘 개념플로이드 와샬 알고리즘과 다른 최단 경로를 찾는 알고리즘의 차이점은 플로이드 와샬의 경우 모든 정점에서 모든 정점으로의 최단 경로를 한번에 구한다. 즉 정점과 정점, 모든 쌍의 최단 경로를 구하는 것이다. 방법은 먼저 가능한 모든 쌍을 표현하는 행렬(이차원 배열)을 선언하고 다이나믹 프로그래밍(dp)의 방식으로 각각의 원소들(각 쌍의 최단거리)을 업데이트 해나간다.업데이트 기준를 행하는 기준은 현재 거쳐가는 정점이다거쳐가는 정점을 기준으로 알고리즘을 수행한다.i 에서 j 로 가는데 해당 정점을 경유해서 가는 것이 더 빠르다면 그 정점을 거쳐서 가는걸로 업데.. 2023. 10. 2. 이전 1 다음
