𝐓𝐨𝐝𝐚𝐲 𝐈 𝐋𝐞𝐚𝐫𝐧 2022.03.31.목

Today I Learn (20220331)

---

오늘은 문제를 하나도 아직 다 못풀었다... 그렇지만 오늘은 어제에 이어 우선 순위 큐와 다익스트라에 대해 배웠다. 알고리즘의 세계는 배우면 배울수록 무궁무진 한거 같다...ㅠㅠ 어제 좀.. 늦게잤더니 컨디션이 매우 저조했지만 적게 잔거 치고 수업 정말 열심히 들었다. 복습만이 살길,, 근데 다음주 과목평가가 매우 걱정된다. 주말에 최대한 문제를 많이 풀어보고 이제까지 배운 알고리즘의 키워드를 되세겨 보는 시간을 갖도록 해야겠다. 다익스트라를 그림으로 그려보니까 조금씩 알 거 같다. 이제 이를 코드와 접목시켜 코드로 구현하고 다음주에 다익스트라 문제들을 여러개 풀어서 내 것으로 만들어야겠다.

우선 순위 큐

---

**큐(Queue)**는 선입선출 형식의 자료구조.

**우선순위 큐(Priority Queue)**는 먼저 들어오는 데이터가 아니라, 우선 순위가 높은 데이터가 먼저 나가는 형태의 자료구조.

이를 우리는 **힙(Heap)**을 이용하여 구현.

Min heap

---

# insert과정 -- headq는 default값이 Min heap이다.
import heapq
arr= []
heapq.heappush(arr,1)
heapq.heappush(arr,3)
heapq.heappush(arr,4)
print(arr)

#top() and pop()과정 -- list에 있는거 보다 많이 실행시 오류
print(heaq.headpop(arr))
print(heaq.headpop(arr))
print(heaq.headpop(arr))

#tuple을 통한 우선순위 지정
import heapq
arr=[]
heapq.heappush(arr,(1,'hi'))
heapq.heappush(arr,(3,'am'))
heapq.heappush(arr,(2,'i'))
heapq.heappush(arr,(4,'iseo'))

for i in range(len(arr)):
    print(heapq.heappop(arr)[1], end=' ')

# 리스트를 heap의 자료용으로 한번에 변환하기
import heapq

arr=[1232,5,3,1,5]
heapq.heapify(arr)
#heap의 자료형이니까 루투노드에 값은 가장 작은 값..... 
#나머지는 걍 정렬 안됨
print(*arr)

for i in range(len(arr)):
    print(heapq.heappop(arr))

Max heap

---

1. 튜플을 이용하는 방법
2. 음수(-)를 이용하는 방법(람다 사용 가능)

1. 튜플을 이용하는 방법

import heapq
#Max heap만들기
arr = []
#튜플에 우선순위를 이용해 출력하는 방법
heapq.heappush(arr,(-1,1))
heapq.heappush(arr,(-3,3))
heapq.heappush(arr,(-8,8))

for i in range(len(arr)):
    print(heapq.heappop(arr)[1])

1. 음수(-)를 이용하는 방법

import heapq
#음수를 이용하는 방법
#우리가 출력할 값에 - 붙여 push
#pop할 때 -를 붙여 다시 양수로 나오게 함.
arr=[]
heapq.heappush(arr,-1)
heapq.heappush(arr,-4)
heapq.heappush(arr,-7) #-7이 가장 먼저 나온다

for i in range(len(arr)):
	print(-heapq.heappop(arr)) #가장 먼저 나오는 -7에 다시 -를 붙여 양수 형태로 출력

priority queue를 이용해 max heap출력하시오.

---

import heapq

arr=[11,12,6,8,10,4]
maxheap=[]
for i in range(len(arr)):
    heapq.heappush((maxheap,(-arr[i],arr[i]))
                   
for i in range(len(arr)):
	print(heapq.heappop(maxheap)[1])

람다식 이용

---

import heapq
arr=[11,12,6,8,10,4]
rev=lambda x:x*-1
#arr값에 음수를 붙여서 maxheap 리스트 만든 후
maxheap = list(map(rev,arr))
#heap의 자료형으로 바꾸고
heapq.heapify(maxheap)

#음수 붙여서 출력하기
for i in range(len(maxheap)):
    print(-heapq.heappop(maxheap))

연습문제

카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.


입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.


출력
첫째 줄에 최소 비교 횟수를 출력한다.

입력
4
50
20
70
30

출력
320


입력
3
10
20
40

출력
100

import heapq

n=int(input())
card=[]

#입력 받은 카드 insert
for i in range(n):
    heapq.heappush(card,int(input()))
    
answer = 0
while len(card)>1: #카드 묶음의 개수가 1개가 될 때까지 반복
    
    #가장 작은 묶음 카드 빼오고
    temp1=heapq.heappop(card)
    #그다음 작은 카드 묶음 빼오기
    temp2=heapq.heappop(card)
    #두개를 합한 것이 비교 횟수. 총 비교횟수를 구하는 answer변수
    answer+=(temp1+temp2)
    #다시 한 묶음이 된 카드 push하기
    heapq.heappush(card,temp1+temp2)
print(answer)
    
    

다익스트라(Dijkstra) 알고리즘

---

1. 한 정점에서 다른 모든 도착점까지 드는 최소 비용 또는 최단 거리 구할 때 이용! - 효율성 높여주고 빠른 속도.
2. 간선의 정보는 모두 양수여야함(가중치가 양수여야 함)
3. ※ 음수가 있다면 bellman -ford알고리즘 이용
4. 양방향, 단방향 가능

※ Floyd washall은 모든 정점에서 다른 모든 정점까지의 최단 거리 구할 때 사용

이용 방법

---

원리는 간단하다.

시작-> 도착 vs 시작점->경유지->도착 이 둘 중 작은 값으로 result를 갱신

1. 이중 for문을 이용 (O(n^2)) - 인접 행렬 이용
2. Priority Queue 이용 (O(nlogn)) - 인접 리스트 이용

이중 for문을 이용 (O(n^2)) - 인접 행렬 이용

다익스트라 인접행렬 이용 시 로직

name='ABCDE'
inf=99999
arr=[
    [0, 3, inf, 9, 5],
    [inf, 0, 7, inf, 1],
    [inf, inf, 0, 1, inf],
    [inf, inf, inf, 0, inf],
    [inf, inf, 1, inf, 0]]

used=[0]*5
used[0]=1  # 시작점 A에 해당하는 used배열에 1 체크
result=[0, 3, inf, 9, 5]

def select_ky():
    minn=99999
    minindex=0
    for i in range(5): # result 배열을 탐색하는데
        if used[i]==0 and result[i]<minn:  # 값이 가장 작고
            minn=result[i]                 # 경유지로 택한적이 없는 정점이라면
            minindex=i
    return minindex


def dijk():
    for i in range(4):
        via=select_ky() # 경유지를 정해서 반환하는 함수
        used[via]=1 # 경유지로 택한 곳의 used배열값을 1로 체크

        for j in range(5):
            baro=result[j] # 시작점->다른정점(도착지)
            kyung=result[via]+arr[via][j] # (시작->경유) + (경유->다른정점(도착지))
            if baro>kyung: # 경유지 들렸다 가는것이 더 저렴하면
                result[j]=kyung # result 배열 갱신

dijk()

print(*result)

---

Priority Queue 이용 (O(nlogn)) - 인접 리스트 이용

다익스트라 인접리스트 이용 시 로직

#입력예제 입니다

5
7
0 1 3
0 3 9
0 4 5
1 2 7
1 4 1
2 3 1
4 2 1
0 2

출력예제 입니다.
5

5 # 정점의 개수
7 # 간선의 정보
0 1 3
0 3 9 # 시작지 도착지 비용
0 4 5
1 2 7
1 4 1
2 3 1
4 2 1
0 3 # 시작지 도착지


import heapq
n = int(input()) # 정점의 개수
m = int(input()) # 간선의 정보
graph = [[] for _ in range(n)]

for _ in range(m):
    a, b, c = map(int, input().split()) # 시작점 # 도착점 # 비용
    graph[a].append((b, c))

start, target = map(int, input().split())  # 시작점(start) 으로 부터 도착점(target) 까지 최소 비용 구하기
inf = int(21e8)
result = [inf] * n




def dijkstra(start):
    result[start] = 0   # 시작점 start 에 해당하는 result 값을 0   A 를 경유지로 처음에 셋팅
    heap = []
    heapq.heappush(heap, (0, start))

    while heap:
        si_ky_cost, kyungyou = heapq.heappop(heap)


        if si_ky_cost > result[kyungyou]: # 앞 과정에서 갱신된 시작점에서 경유지 까지의 result 값보다
            continue                      # 방금 뽑아낸 시작점에서 경유지 까지의 비용이 더 크면
                                          # 넘겨라 이미 경유지로 택해서 업뎃된 곳이다


        #si_ky_do_cost ( 시작->경유 + 경유-> 도착 )   vs    result[i[0]]  (시작점 -> 도착) 할 것이다.
        for i in graph[kyungyou]:
            si_ky_do_cost = si_ky_cost + i[1]  # 시작점에서 경유지 갔다가 도착점 가는 비용부터 구함.

            if si_ky_do_cost < result[i[0]]:     #  비교후 경유지 들렸다 가는것이 더 저렴하면
                result[i[0]] = si_ky_do_cost     #  result 배열 갱신
                heapq.heappush(heap, (si_ky_do_cost, i[0])) # heap에 갱신된!! 내용 push 하기

dijkstra(start)
print(result[target])