'이것이 취업을 위한 코딩 테스트다' 서적 학습노트

2021-05-16

.

[학습시 참고자료]

  • 나동빈 저자 ‘이것이 취업을 위한 코딩테스트다 with 파이썬’ 를 읽고 공부한 내용을 정리

  • 참고 URL

1) https://book.naver.com/bookdb/book_detail.nhn?bid=16439154

2) https://www.youtube.com/c/dongbinna

3) https://github.com/ndb796

[학습내용]

  • 그리디 : 현재상황에서 지금 당장 좋은 것만 고르는 방법

대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 맞는지 검토할 수 있어야 한다.

어떤 코딩테스트 문제를 풀때 곧바로 문제 유형이 파악이 잘 안된다면 그리디 알고리즘을 의심해보는 것이 좋다.

# 92 p, 큰수의 법칙

M=8
K=3
N=5
num_list=[2,4,5,4,6]
def answer(N,M,K,num_list):
    result = 0
    
    num_list.sort()
    max_num=num_list[N-1]
    second_max_num=num_list[N-2]
    temp_count = 1
    
    for num in range(M):    
        if temp_count<= K:
            result += max_num
            temp_count +=1
        else:
            temp_count=1
            result += second_max_num 
    
    return result

print(answer(N,M,K,num_list))

## 위와 같이 단순하게 푸는 방법이 있고, 수열을 파악해서 구현해서 푸는 경우도 있다.

46

# 96p, 숫자 카드 게임

N=2
M=3
card_list=[
    [3,1,2],
    [4,1,4],
    [2,2,2]
]

def answer(N,M,card_list):
    result=0
    
    min_value_of_row=[]
    for row in card_list:
        row.sort()
        min_value_of_row.append(row[0])
        
    result=max(min_value_of_row)
    
    return result
    
print(answer(N,M,card_list))

N=2
M=4
card_list=[
    [7,3,1,8],
    [3,3,3,4]
]

print(answer(N,M,card_list))

2
3

## 리스트에서 최솟값, 최댓값 구하는 함수
test_list = [3,1,2,7,9,6,4,8,5]
print(min(test_list))
print(max(test_list))

1
9

N=25
K=5
N%K

0

# 99p, 1이 될때까지
N=25
K=5

def answer(N,K):
    result=0
    
    while True:
        if N == 1:
            break
        
        if N%K == 0:           
            N=N/K
            result+=1
            
        else :
            N=N-1
            result+=1 

    return result

answer(N,K)

2

  • 완전탐색 : 모든 경우의 수를 주저없이 다 계산하는 해결방법

  • 시뮬레이션 : 문제에서 제시한 알고리즘을 한단계씩 차례대로 직접 수행

# 111P, 상하좌우

import time

start_time = time.time()

N = 5
plan = ['R','R','R','U','D','D']
def answer(N,plan):
    
    result = [1,1]
    
    
    for progress in plan:
        if progress == 'R':            
            if (result[1]+1) > N:
                pass
            else:
                result[1] += 1
                    
        if progress == 'U':
            if (result[0]-1) < 1:
                pass
            else : 
                result[0] -= 1
            
        if progress == 'D':
            if (result[0]+1) > N:
                pass
            else :
                result[0] += 1
        
        if progress == 'L':
            if (result[1]-1) < 1:
                pass
            else :
                result[1] -= 1
                
    x=result[0]
    y=result[1]
    
    return x,y

x,y = answer(N,plan)
print(x,y)

end_time = time.time()
print("run_time : ", end_time - start_time)

3 4
run_time :  0.0006456375122070312

# 112P, 시각

import time

start_time = time.time()

N = 5
def answer(N):
    result = 0  
    for i in range(N+1):
        for j in range(60):
            for k in range(60):
                if '3' in str(i) + str(j) + str(k):
                    result += 1
    return result

result = answer(N)
print(result)

end_time = time.time()
print("run_time : ", end_time - start_time)

11475
run_time :  0.02898550033569336

# 115P, 왕실의 나이트

import time

# 현재 나이트의 위치 받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

start_time = time.time()

def answer(row, column):
    result = 0  
    
    # 나이트가 이동할 수 있는 8가지 방향 정의
    steps = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]
    
    # 8가지 방향에 대하여 각 위치로 이동이 가능한지 풀스캔
    result = 0
    for step in steps:
        # 이동하고자 하는 위치 확인
        next_row = row + step[0]
        next_column = column + step[1]
        # 해당 위치로 이동이 가능하다면 카운트 증가
        if next_row >= 1 and next_row <= 8 and next_column >=1 and next_column <= 8:
            result += 1

    return result

result = answer(row, column)
print(result)

end_time = time.time()
print("run_time : ", end_time - start_time)

a1
2
run_time :  0.0016281604766845703

# 큐예제

from collections import deque

queue = deque()

queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.popleft()

print(queue)
queue.reverse()
print(queue)

deque([2, 3, 4])
deque([4, 3, 2])

# factorial 구현

# 반복문으로 구현한 팩토리얼
def factorial_iterative(n):
    result = 1
    # 1부터 n까지 수를 차례대로 곱하기
    for i in range(1, n+1):
        result *= i
    return result

# 재귀적으로 구현한 팩토리얼
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n-1)

print(factorial_iterative(5))
print(factorial_recursive(5))

120
120
  • 프로그래밍에서 그래프를 표현하는 방식

1) 인접행렬 : 2차원 배열로 그래프의 연결관계를 표현하는 방식

2) 인접리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식

# p134, 인접행렬 예시

#       0
#   7/    \ 5
#  1       2


INF = 9999999999999999

graph_01 = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph_01)

# p136, 인접리스트 예시
# 행이 3개인 2차원 이르스토 인접 리스트를 표현
graph_02 = [[] for _ in range(3)]

# 0번 노드에 연결된 노드정보 저장(노드, 거리)
graph_02[0].append((1,7))
graph_02[0].append((2,5))

# 1번 노드에 연결된 노드정보 저장(노드, 거리)
graph_02[1].append((0,7))

# 2번 노드에 연결된 노드정보 저장(노드, 거리)
graph_02[2].append((0,5))

print(graph_02)

# 인접행렬 : 모든 관계를 저장하기 때문에 노드가 증가할수록 불필요한 메모리 낭비
# 인접리스트 : 연결정보만 저장하기 때문에 메모리를 효율적으로 활용 가능

[[0, 7, 5], [7, 0, 9999999999999999], [5, 9999999999999999, 0]]
[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]
  • DFS : 깊이 우선탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
# DFS 예제
def dfs(graph, v, visited):
    # 현재 노드를 방문처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
# visited = [False, False, False, False, False, False, False, False, False]
visited = [False] * 9

# 정의한 DFS 함수를 호출
dfs(graph, 1, visited)

1 2 7 6 8 3 4 5 

# p.149 음료수 얼려먹기

# N,M을 공백으로 구분하여 입력받기
n,m = map(int,input().split())

# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
    
def dfs(x,y):
    if x <= -1 or x >=n or y <= -1 or y>=m:
        return False
    if graph[x][y] == 0:
        graph[x][y]=1
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False
        
# 모든 노드에 대해서 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        if dfs(i,j)==True:
            result+=1
            
print(result)
  • BFS : 너비우선 탐색, 가까운 노드부터 탐색하는 알고리즘
# BFS 예제
from collections import deque

# BFS 정의
def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리를 사용
    queue = deque([start])
    # 현재 노드를 방문처리
    visited[start] = True
    # 큐가 빌때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아서 출력
        v = queue.popleft()
        print(v, end=' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
# visited = [False, False, False, False, False, False, False, False, False]
visited = [False] * 9

# 정의한 DFS 함수를 호출
bfs(graph, 1, visited)

1 2 3 8 7 4 5 6 

# p153, 미로탈출

# BFS 문제 예시

from collections import deque

# N,M을 공백으로 구분하여 입력받기
n,m = map(int,input().split())

# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
    graph.append(list(map(int,input())))
    
# 이동할 네 방향 정의(상,하,좌,우)
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# BFS 소스코드 구현
def bfs(x,y):
    queue=deque()
    queue.append((x,y))
    
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or ny < 0 or nx >= n or ny >=m :
                continue
                
            if graph[nx][ny] == 0:
                continue
                
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx,ny))
                
    return graph[n-1][m-1]

print(bfs(0,0))

3 3
110
010
011
5

# 선택정렬 : 157p 예시)가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고,
# 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
    # 가장 작은 원소의 인덱스
    min_index = i
    for j in range(i+1,len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i],array[min_index] = array[min_index], array[i]
    
print(array)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 파이썬 스와프 예시
array = [3,5]
array[0],array[1] = array[1], array[0]
print(array)

[5, 3]

# 삽입정렬 : 특정한 데이터를 적절한 위치에 삽입
array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1,len(array)):
    # 인덱스 i부터  1까지 감소하며 반복하는 문법
    for j in range(i,0,-1):
        if array[j] < array[j-1]:
            #한칸씩 왼쪽으로 이동
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break

print(array)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 퀵정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의
# 위치를 바꾸면 어떨까. 보통 리스트에서 첫번쨰 데이터를 피벗으로 정한다.

# 직관적인 퀵정렬 형태
array = [7,5,9,0,3,1,6,2,4,8]

def quick_sort(array, start, end):
    if start >= end:
        return
    pivot = start
    left = start +1
    right = end
    while left <= right:
        
        # 피벗보다 큰 데이터를 찾을때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
            
        # 피벗보다 작은데이터를 찾을때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        
        # 엇갈렸다면 작은 데이터와 피벗을 교체
        if left > right :
            array[right], array[pivot] = array[pivot], array[right]
        # 엇갈리지 않았다면 작은데이터와 큰 데이터를 교체
        else:
            array[left], array[right] = array[right], array[left]
    
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬수행
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)
    
quick_sort(array,0,len(array)-1)
print(array)

# 파이썬의 장점을 살린 퀵 정렬
array = [7,5,9,0,3,1,6,2,4,8]

def quick_sort(array):
    if len(array) <=1:
        return array
    
    pivot = array[0] # 피벗은 첫번째 원소
    tail = array[1:] # 피벗을 제외한 리스트
    
    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분
    
    # 분할이후 왼쪽부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 계수정렬 : 특정한 조건이 부합할때만 사용할 수 있지만 매우 빠른 정렬알고리즘
# 계수정렬이 심각한 비효율성을 보여주는 예시 : 0과 999999 단 두개만 존재할때

# 모든 원소의 값이 0보다 같거나 크다고 가정
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]

# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array)+1)

for i in range(len(array)):
    count[array[i]]+=1
    
for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')

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

# 정렬 라이브러리에서 key를 활용한 소스코드
array = [('banana',2),('apple',5),('carrot',3)]

def setting(data):
    return data[1]

result = sorted(array, key=setting)
print(result)

[('banana', 2), ('carrot', 3), ('apple', 5)]

# p178, 위에서 아래로
input_value = int(input())

array = []
for i in range(input_value):
    array.append(int(input()))
    
array = sorted(array, reverse=True)

for i in array:
    print(i, end=' ')

3
4
1
8
8 4 1
  • 힙큐

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다.

1) 힙 특성 : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다

2) 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙

3) 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
heapq.heappush(heap, 40)
heapq.heappush(heap, 30)

print(heap)
print(heapq.heappop(heap))

[10, 30, 20, 50, 40]
10

heap2 = [50 ,10, 20]
heapq.heapify(heap2)

print(heap2)

[10, 50, 20]

result2 = heap[0]

print(result2)
print(heap)

10
[10, 50, 20]

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
    heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

# while heap:
    # print(heapq.heappop(heap)[1])  # index 1
    
print(heap)

[(-8, 8), (-7, 7), (-5, 5), (-1, 1), (-3, 3), (-4, 4)]

## 이진탐색 소스코드는 외우자

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start+end)//2
        
        if array[mid] == target:
            return mid
        
        elif array[mid] > target:
            end = mid -1
            
        else : 
            start = mid + 1
            
    return None

n, target = list(map(int, input().split()))

array = list(map(int, input().split()))

result = binary_search(array, target, 0 , n-1)
if result == None:
    print("원소가 존재하지 않습니다.")
else : 
    print(result + 1)

10 7
1 3 5 7 9 11 13 15 17 19
4

import sys

input_data = sys.stdin.readline().rstrip()
print(input_data)

import time

start_time = time.time()

# 피보나치 함수
def fibo(x):
    if x ==1 or x ==2:
        return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(35))

end_time = time.time()

print("running time : ", end_time-start_time)
# 이런식으로 소스코드를 작성하면 심각한 문제가 생길 수 있다.
# n이 커지면 커질수록 연산하는 시간이 엄청나게 커질것이다.
# 무려 빅오가 2에 n승이다.

9227465
running time :  6.34865140914917

# 다이나믹 프로그래밍 사용조건
# 1) 큰 문제를 작은문제로 나눌 수 있다.
# 2) 작은문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

# 그러면 Memorization을 적용해서 피보나치 수열을 구현해보자
# Memorization : 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면
# 메모한 결과를 그대로 가져오는 기법. 캐싱이라고 부르기도 한다.

# 재귀함수를 이용한 다이나믹 프로그래밍 방식 : 탑다운 방식

import time

start_time = time.time()

# 한번 계산된 결과를 Memorization 하기 위한 리스트 초기화
d = [0] * 100

def fibo(x):
    # 종료조건(1 혹은 2일때 1을 반환)
    if x ==1 or x ==2:
        return 1
    
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]
    
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x-1)+fibo(x-2)
    return d[x]

print(fibo(35))

end_time = time.time()

print("running time : ", end_time-start_time)


start_time = time.time()

# 반복문을 이용하여 소스코드를 작성하는 방법 바텀업
d = [0] * 100

d[1] = 1
d[2] = 1
n = 35

for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]
    
print(d[n])

end_time = time.time()

print("running time : ", end_time-start_time)

9227465
running time :  0.0
9227465
running time :  0.0

# p.217, 1로 만들기

# 정수 x 입력
x = int(input())

import time

start_time = time.time()

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001

# 다이나믹 프로그래밍 (바텀업)

for i in range(2,x+1):
    
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i-1]+1
    
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i%2==0:
        d[i] = min(d[i],d[i//2]+1)
    
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i%3==0:
        d[i] = min(d[i],d[i//3]+1)
        
    # 현재의 수가 5으로 나누어 떨어지는 경우
    if i%5==0:
        d[i] = min(d[i],d[i//5]+1)
        
print(d[x])

end_time = time.time()

print("running time : ", end_time-start_time)

26
3
running time :  0.0

#p.220, 개미전사

chang_go=5
chang_go_list=[1,3,1,5,8]

def answer(chang_go,chang_go_list):
    result = 0
    cache=[0]*100
    
    cache[0]=chang_go_list[0]
    cache[1]=max(chang_go_list[0],chang_go_list[1])
    for i in range(2,chang_go):
        cache[i]=max(cache[i-1],cache[i-2]+chang_go_list[i])
        
    result=cache[chang_go-1]
    
    return result

answer(chang_go,chang_go_list)

11
  • 다익스트라 알고리즘

그래프에서 여러개의 노드가 있을때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

다익스트라 최단경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문이다.

# 간단한 형태의 다익스트라 알고리즘
# 시간복잡도가 v의 2제곱승이다

import sys
#input = sys.stdin.readline

INF = int(1e9)

# 노드의 개수, 간선의 개수를 입력받기
n,m = map(int,input().split())

# 시작노드 번호를 입력받기
start = int(input())

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n+1)]

# 방문한 적이 있는지 체크하는 목적의 리스트
visited = [False]*(n+1)

# 최단거리 테이블을 모두 무한으로 초기화
distance = [INF]*(n+1)

# 모든 간선정보를 입력받기
for _ in range(m):
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    a,b,c = map(int,input().split())
    graph[a].append((b,c))
    
# 방문하지 않은 노드중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
    min_value = INF
    index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
    for i in range(1,n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    # 시작노드에 대해서 초기화
    distance[start]=0
    visited[start]=True
    for j in graph[start]:
        distance[j[0]] = j[1]
    # 시작노드를 제외한 전체 n-1개의 노드에 대해 반복
    for i in range(n-1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문처리
        now = get_smallest_node()
        visited[now]=True
        # 현재노드의 연결된 다른 노드를 확인
        for j in graph[now]:
            cost=distance[now]+j[1]
            # 원래 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[j[0]]:
                distance[j[0]] = cost

# 다익스트라 알고리즘 실행
dijkstra(start)
        
# 모든 노드로 가기위한 최단 거리를 출력
for i in range(1,n+1):
    # 도달할 수 없는 경우, 무한(INF)라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3 
4 5 1
5 3 1
5 6 2
0
2
3
1
2
4

# 개선된 다익스트라 알고리즘
# 시간복잡도가 log v를 보장한다.
# 암기할것

import heapq

INF = int(1e9)

# 노드의 갯수, 간선의 갯수를 입력받기
n,m = map(int,input().split())

# 시작노드 번호 입력받기
start = int(input())

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기
graph = [[] for i in range(n+1)]

# 최단거리 테이블을 모두 무한으로 초기화
distance = [INF]*(n+1)

# 모든 간선의 정보를 입력받기
for _ in range(m):
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    a,b,c = map(int,input().split())
    graph[a].append((b,c))
    
def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정되며, 큐에 삽입
    heapq.heappush(q,(0,start))
    distance[start]=0
    
    # 큐가 비어있지 않으면
    while q:
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[now]<dist:
            continue
            
        # 현재노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist+i[1]
            # 현재 노드를 꺼내서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))
                
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1,n+1):
    # 도달할 수 없는 경우, 무한이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else : 
        print(distance[i])

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
0
2
3
1
2
4