백트래킹, 최단경로

[jonggking]

백트래킹

• N Queen
• 스도쿠
• 연산자 끼워넣기
• 스타트와 링크

최단경로

• 최단경로
• 숨바꼭질3
• 특별한 최단경로
• 플로이드
• 운동

[jonggking]

다익스트라 최단 경로 알고리즘

: 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로(음의 경로가 없을 때 사용)

'가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복

1. 출발 노드를 설정합니다.
2. 최단 거리 테이블을 초기화합니다.(1차원 리스트로 표현)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택합니다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.
5. 위 과정에서 3과 4번을 반복합니다.

[시간복잡도]
O(V*V) or
우선순위 큐 이용: O(ElogV) => 최단거리가 가장 짧은 노드 선택할 때 힙이용

import heapq

#오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h=[]
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
       # 최대힙으로 사용하고 싶다면
       heapq.heappush(h, -value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        heapq.append(heapq.heapop(h))
    return result