LiJell's 성장기

최단 경로 문제 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미합니다. 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않음 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 다익스트라 알고리즘 동작 과정 출발 노드 설정 최단..

알고리즘 1. 우선순위 큐(Priority Queue) 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용 예. 보석 데이터를 자료구조에 넣었다가 가치가 높은 보석부터 꺼내서 확인해야 하는 경우 자료구조 추출되는 데이터 stack 가장 나중에 삽입된 데이터 queue 가장 먼저 삽입된 데이터 priority queue 가장 우선순위가 높은 데이터 우선순위 큐를 구현하는 방법 1) 단순히 리스트를 이용하여 구현 가능 2) 힙(heap)을 이용하여 구현 가능 데이터의 개수가 N개일 때, 구현 방식에 따라서 시간 복잡도를 비교한 내용은 아래 표와 같다 우선순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(H..