Jay's Develop Note

최소힙과 최대힙에 대한 설명

힙(Heap)은 이진 트리 기반의 자료구조로, 특정한 규칙을 따릅니다. 힙에는 두 가지 주요 형태가 있습니다:

1. 최소힙(Min Heap): 부모 노드의 값이 자식 노드보다 항상 작거나 같은 이진 트리입니다. 즉, 가장 작은 값이 루트에 위치하게 됩니다.

2. 최대힙(Max Heap): 부모 노드의 값이 자식 노드보다 항상 크거나 같은 이진 트리입니다. 가장 큰 값이 루트에 위치합니다.

이 두 힙은 주로 우선순위 큐(Priority Queue)로 사용되며, 값을 정렬된 순서대로 유지해야 하는 문제를 해결하는 데 매우 효율적입니다.

최소힙의 특징

• 가장 작은 값을 빠르게 찾고 싶을 때 유용합니다.

• 삽입과 삭제 연산은 O(log n)의 시간 복잡도를 가집니다.

• 파이썬에서는 heapq 라이브러리를 사용해 최소힙을 구현할 수 있습니다.

최대힙의 특징

• 가장 큰 값을 빠르게 찾고 싶을 때 유용합니다.

• 삽입과 삭제 연산은 O(log n)의 시간 복잡도를 가집니다.

• 파이썬의 heapq는 기본적으로 최소힙으로 동작하므로, 최대힙을 구현하려면 음수로 변환해서 사용합니다.

최소힙/최대힙을 사용하는 상황

1. 우선순위가 있는 작업 처리

• 힙은 우선순위 큐(Priority Queue)로 사용되며, 가장 높은(작거나 큰) 우선순위를 가진 요소를 빠르게 처리해야 할 때 매우 유용합니다.

• 예시: 병원 응급실, 작업 스케줄링 등 우선순위가 있는 작업을 먼저 처리할 때.

2. K번째 최소/최대 값을 구할 때

• 힙을 사용하면 K번째로 작은/큰 값을 찾는 연산을 매우 효율적으로 할 수 있습니다.

• 최소/최대 값을 찾아야 하는 문제에서는 힙이 시간 복잡도를 크게 줄여줍니다.

3. 실시간으로 가장 큰 값이나 작은 값을 관리할 때

• 데이터가 계속해서 추가될 때, 매번 최소값이나 최대값을 빠르게 추적해야 할 경우 힙이 유용합니다.

• 예시: 스트리밍 데이터에서 상위 K개의 값을 추적하는 문제.

4. 정렬된 데이터를 유지해야 할 때

• 힙을 사용하면 데이터를 정렬된 상태로 유지하면서도 삽입/삭제가 빠릅니다.

• 예시: 실시간으로 정렬된 데이터를 처리하는 알고리즘.

최소힙/최대힙의 사용 예시

최소힙 예시:

import heapq

h = []

heapq.heappush(h, 5)

heapq.heappush(h, 3)

heapq.heappush(h, 8)

print(heapq.heappop(h))  # 3, 최소값부터 꺼내짐

print(heapq.heappop(h))  # 5

print(heapq.heappop(h))  # 8

최대힙 예시 (음수를 이용):

import heapq

h = []

heapq.heappush(h, -5)  # 음수로 저장하여 최대힙 구현

heapq.heappush(h, -3)

heapq.heappush(h, -8)

print(-heapq.heappop(h))  # 8, 최대값을 꺼내려면 다시 양수로 변환

print(-heapq.heappop(h))  # 5

print(-heapq.heappop(h))  # 3

힙을 사용하면 효율적인 경우

• 데이터가 계속해서 들어오고, 그중 가장 큰 값이나 가장 작은 값을 실시간으로 추적해야 하는 경우.

• 데이터가 계속 추가되지만 매번 전체를 정렬할 필요는 없고, 가장 큰 값이나 작은 값만 찾고 싶을 때.

• K번째로 큰 값/작은 값을 구하는 문제를 효율적으로 해결하고 싶을 때.

비효율적인 경우

• 이미 정렬된 배열이 주어졌을 때 굳이 힙을 사용할 필요가 없습니다.

• 힙의 삽입과 삭제는 O(log n)이므로, 단순 정렬이 더 나은 선택일 수 있는 경우도 있습니다.

최소힙/최대힙의 시간 복잡도

• 삽입 및 삭제: O(log n)

• 최소/최대값 조회: O(1) (루트 노드이기 때문에 바로 조회 가능)

힙은 실시간 데이터 처리나 우선순위가 중요한 문제에서 매우 효율적이므로 이러한 문제를 해결할 때 사용하는 것이 좋습니다.

예시 : 

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.

이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.

명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

제한사항

• 3 ≤ k ≤ 100
• 7 ≤ score의 길이 ≤ 1,000
  • 0 ≤ score[i] ≤ 2,000

---

입출력 예kscoreresult

3	[10, 100, 20, 150, 1, 100, 200]	[10, 10, 10, 20, 20, 100, 100]
4	[0, 300, 40, 300, 20, 70, 150, 50, 500, 1000]	[0, 0, 0, 0, 20, 40, 70, 70, 150, 300]

---

입출력 예 설명

입출력 예 #1

• 문제의 예시와 같습니다.

입출력 예 #2

• 아래와 같이, [0, 0, 0, 0, 20, 40, 70, 70, 150, 300]을 return합니다. 

  

이 문제는 루프를 돌며 매 루프마다 최솟값을 찾아야 한다. 또한, 매번 스택을 업데이트 해줘야 하는데, 최솟값을 배열의 맨 마지막에 넣어야 한다. 힙이 없다면, 매 루프마다 append -> 배열을 정렬해야 한다. 하지만 정렬의 시간 복잡도는 O(n log n)이므로 큰 입력에 대해서는 비효율적이다.

어차피 이 문제에서 우리가 찾아야 하는건 '최솟값' 이다. 

루프가 n번 돌고, 매번마다 리스트를 정렬하고 거기서 최솟값을 찾는건 비효율적이다. 따라서, 힙을 쓰면 실시간으로 따로 정렬이나 min()함수 없이 최솟값을 트래킹 할 수 있다.

import heapq

def solution(k, score):
    answer = []
    h = []
    
    for s in score:
        if len(h) < k:
            heapq.heappush(h, s)  # 힙에 값 추가
        else:
            # 현재 힙의 최솟값보다 큰 경우 힙의 최솟값을 대체
            if h[0] < s:
                heapq.heapreplace(h, s)  # 가장 작은 값을 pop하고 s 삽입
        answer.append(h[0])  # 현재 힙에서 최솟값을 answer에 추가
        
    return answer

질문 1: h[0]이 최솟값인가?

• 최소힙에서 h[0]은 항상 최소값이다. 파이썬의 heapq 라이브러리는 기본적으로 최소힙을 사용하므로, 가장 작은 값이 루트에 위치합니다.

• 따라서 h[0]은 최소값을 의미한다.

질문 2: heapreplace가 뭐냐?

• heapq.heapreplace(h, s)는 최소힙에서 가장 작은 값(루트 노드)을 꺼낸 뒤, 새로운 값을 힙에 추가하는 함수다. 즉, 기존의 최솟값을 삭제하고, 새로운 값을 삽입하는 연산이다.

• 이 함수는 다음과 같은 두 가지 동작을 하나의 연산으로 처리한다:

1. 최소값을 꺼냄 (heappop(h))

2. 새로운 값을 삽입 (heappush(h, s))

이 과정에서 힙은 여전히 최소힙의 조건을 만족하게끔 유지된다.

예시:

import heapq

h = [1, 3, 5, 7, 9]

heapq.heapreplace(h, 4)

print(h)  # 출력: [3, 4, 5, 7, 9]

1. h에서 최소값 1이 삭제되고, 4가 삽입되었다.

2. 결과적으로 힙의 최소값은 3으로 바뀌었고, 힙의 다른 요소들은 최소힙의 조건을 만족하도록 재정렬되었다.

heapreplace()와 heappushpop()의 차이:

• heapreplace()는 값을 무조건 삭제한 후 새로운 값을 삽입.

• 반면에, heappushpop()은 새로운 값을 먼저 힙에 삽입한 뒤, 가장 작은 값(루트 노드)을 제거하는 방식으로 동작. 삽입하는 값이 힙의 최솟값보다 작으면, 그대로 그 값이 빠지고 힙은 그대로 유지.

예시 비교:

import heapq

h = [1, 3, 5, 7, 9]

# heapreplace: 기존 최솟값을 삭제하고 4를 삽입

heapq.heapreplace(h, 4)

print(h)  # 출력: [3, 4, 5, 7, 9]

# heappushpop: 먼저 2를 삽입하고 최솟값을 제거

heapq.heappushpop(h, 2)

print(h)  # 출력: [3, 4, 5, 7, 9] (2는 최솟값이기 때문에 삽입되자마자 빠짐)

따라서, heapreplace()는 값 대체가 필요한 경우 사용되고, heappushpop()은 삽입한 값이 최소값일 때 효율적으로 처리할 수 있는 방법입니다.

오늘 코딩 테스트를 풀며 파이썬의 람다 함수에 대해 쓰다가, 확실히 알고 넘어가는 게 좋을 것 같아 정리하고 넘어가기로 했다!

내가 주로 사용했던 람다 함수는 특정 기준으로 정렬할 때 사용했다. 예를 들어, {'a': 10, 'b': 20, 'c': 30}이라는 딕셔너리가 있다고 해 보자. 이 딕셔너리에서 key나 value를 기준으로 정렬하고 싶을 때 말이다.

어떠한 특정 기준으로 정렬하려면 파이썬의 sorted() 함수를 사용하면 된다.

sorted()는 원본 데이터를 정렬하지 않고, 정렬된 새로운 결과값을 반환하므로 이를 다른 변수에 할당해야 한다.

목표: 딕셔너리의 value를 기준으로 정렬한 후, 다시 딕셔너리 형태로 반환하기

temp = {'a': 30, 'b': 60, 'c': 10}

sorted_dict = dict(sorted(temp.items(), key=lambda x: x[1]))

결과: {'c': 10, 'a': 30, 'b': 60}

여기서 주의할 점은 딕셔너리를 sorted() 함수로 정렬할 때, 기본적으로는 key 값이 기준이 된다는 것이다. 그래서 value를 기준으로 정렬하려면 먼저 temp.items()로 (key, value) 쌍에 접근해야 한다.

또 하나의 예시: 문자열을 특정 문자를 기준으로 정렬하기

문제를 풀다가 sorted() 함수의 또 다른 유용한 기능을 발견했다. 예를 들어, 여러 개의 문자열을 담고 있는 배열이 있고, 이 배열을 특정 인덱스의 문자를 기준으로 정렬한다고 해 보자.

temp = ["abce", "abcd", "cdx"]

이 문자열들에서 3번째 인덱스의 문자를 기준으로 정렬하려면, 각 단어의 3번째 문자는 'c', 'c', 'x'가 된다. 이를 기준으로 정렬하면 다음과 같다.

sorted_arr = list(sorted(temp, key=lambda x: x[3]))

결과는 ['abce', 'abcd', 'cdx']가 된다. 그런데 만약 같은 문자를 가진 경우, 이를 전체 문자열을 기준으로 정렬하고 싶다면 어떻게 할까?

즉, 같은 3번째 문자를 가진 ['abce', 'abcd']가 있을 때, 전체 문자열을 기준으로 ['abcd', 'abce', 'cdx']로 정렬하고 싶은 경우다.

이때는 이렇게 해결할 수 있다:

sorted_arr = list(sorted(temp, key=lambda x: (x[3], x)))

이 코드는 3번째 문자를 기준으로 정렬하되, 3번째 문자가 같은 경우 전체 문자열 x를 기준으로 정렬한다. 이렇게 하면 최종 결과는 ['abcd', 'abce', 'cdx']가 된다.

이 코드는 문자열 배열 temp를 두 가지 기준으로 정렬하는데, 두 번째 기준이 첫 번째 기준과 같을 때만 적용된다. 

코드 설명:

1. sorted() 함수: sorted()는 배열을 정렬하는 함수로, 정렬된 새로운 리스트를 반환한다. 여기서는 temp 리스트를 정렬하고 있다.

2. key=lambda x: (x[3], x):

• key는 정렬할 때 기준이 되는 값을 지정하는 인자다. 여기서는 람다 함수를 사용해서 정렬 기준을 두 가지로 나눈다.

• 첫 번째 기준: x[3]으로, 각 문자열의 3번째 인덱스의 문자를 기준으로 정렬한다.

• 두 번째 기준: x로, 전체 문자열을 기준으로 정렬한다. 이 두 번째 기준은 첫 번째 기준(3번째 문자)이 동일할 때만 적용된다.

작동 원리:

• 파이썬의 sorted() 함수는 튜플로 정렬할 때, 첫 번째 요소를 먼저 비교하고, 첫 번째 요소가 같으면 두 번째 요소를 비교한다.

• lambda x: (x[3], x)는 두 가지 기준을 갖는 튜플 (x[3], x)를 반환한다:

• 첫 번째 기준: x[3]은 각 문자열의 3번째 문자다. 이를 기준으로 정렬한다.

• 두 번째 기준: x는 전체 문자열이다. 만약 3번째 문자가 같다면, 문자열 전체를 기준으로 사전순 정렬한다.

예시로 살펴보기:

temp = ["abce", "abcd", "cdx"]

1. 첫 번째 기준: 각 문자열의 3번째 문자는 다음과 같다:

• 'abce': 3번째 문자 'c'

• 'abcd': 3번째 문자 'c'

• 'cdx': 3번째 문자 'x'

2. 첫 번째 기준으로 정렬:

• 'abce'와 'abcd'는 3번째 문자가 같으므로 같은 그룹으로 묶인다.

• 'cdx'는 3번째 문자가 'x'라서 나중에 온다.

3. 두 번째 기준: 3번째 문자가 같은 **‘abce’**와 **‘abcd’**의 경우, 이제 전체 문자열을 기준으로 사전순으로 정렬된다:

• 'abcd'는 'abce'보다 사전순으로 앞서므로 먼저 위치하게 된다.

최종 결과:

• 결과적으로, 정렬된 리스트는 ['abcd', 'abce', 'cdx']가 된다.

요약:

• sorted(temp, key=lambda x: (x[3], x))는 첫 번째로 3번째 문자를 기준으로, 두 번째로 전체 문자열을 기준으로 정렬하는 방식이다.

• 만약 3번째 문자가 같을 때는 전체 문자열을 사전순으로 정렬해주는 역할을 한다.

🔵 문제 1 : 미래 도시

🔹 문제 해설 :

이 문제는 전형적인 플로이드 워셜 알고리즘 문제이다. 현재 문제에서 N의 범위가 100으로 매우 한정적이다. 따라서 플로이드 워셜 알고리즘을 이용해서도 빠르게 풀 수 있기 때문에, 구현이 간단한 플로이드 워셜 알고리즘을 이용하는것이 유리하다. 이 문제의 핵심 아이디어는 1번 노드에서 X를 거쳐 K로 가는 최단 거리는 (1번 노드에서 X까지의 최단 거리 + X에서 K까지의 최단 거리)라는 점이다.

최단 거리 문제는 그림으로 그려 보는것도 좋은 방법이다.

INF = int(1e9) #무한을 의미하는 값으로 10억을 설정

#노드의 수 및 간선의 개수를 입력받기
n, m = map(int, input().split())
#2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] for i in range(n + 1)]

#자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
	for b in range(1, n + 1):
    	if a == b:
        	graph[a][b] = 0

#각 간선에 대한 정보를 입력받아, 그 값으로 초기회
for_ in range(m):
	#A와 B가 서로에게 가는 비용은 1이라고 설정
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1
    
#거쳐 갈 노드 x와 최종 노드 K를 입력받기
x, k = map(int, input().split())

#점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1, n + 1):
	for a in range(1, n + 1):
    	for b in range(1, n + 1):
        	graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
            
#수행된 결과를 출력
distance = graph[1][k] + graph[k][x]

#도달 할 수 없는경우, -1을 출력
if distance >= INF:
	print("-1")
else :
	print(distance)

🔵 문제 2 : 전보

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

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

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    x, y, z = map(int, input().split())
    # x번 노드에서 y번 노드로 가는 비용이 z라는 의미
    graph[x].append((y, z))

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)

# 도달할 수 있는 노드의 개수
count = 0
# 도달할 수 있는 노드 중에서, 가장 멀리 있는 노드와의 최단 거리
max_distance = 0
for d in distance:
    # 도달할 수 있는 노드인 경우
    if d != INF:
        count += 1
        max_distance = max(max_distance, d)

# 시작 노드는 제외해야 하므로 count - 1을 출력
print(count - 1, max_distance)

저번 포스팅에서 살펴봤던 다익스트라 알고리즘은 '한 지점에서 특정 다른 지점까지의 최단 경로를 구해야 하는 경우'에 사용 할 수 있는 최단 경로 알고리즘이다. 이번에 설명하는 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용 할 수 있는 알고리즘이다.

📌 플로이드 워셜 알고리즘

다익스트라 알고리즘은 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작한다. 플로이드 워셜 알고리즘 또한 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드중에서 최단 거리를 찾지 않아도 된다는 점이 다르다. 노드가 N개일때, N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서 플로이드 워셜 알고리즘의 총시간 복잡도는 O(N^3)이다.

다익스트라 알고리즘에서는 출발 노드가 1개이므로 다른 모든 노드까지의 거리를 저장하기 위해 1차원 리스트를 사용했다. 반면, 플로이드 워셜 알고리즘은 2차원 리스트에 '최단 경로'를 저장한다는 차이가 있다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다. 다시 말해 2차원 리스트를 처리해야 하므로 매 단계에서 O(N^2)의 연산이 수행된다.

또한, 다익스트라 알고리즘은 그리디 알고리즘인데, 플로이드 워셜 알고리즘은 DP라는 특징이 있다. 노드의 개수가 N이라고 할때, N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기 때문에 DP로 볼 수 있다.

각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다. 예를 들어 1번 노드에 대해서 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려하면 된다. 정확히는 A -> 1번 노드 ->  B로 가는 비용을 확인한 후에 최단 거리를 갱신한다. 이를테면 현재 최단 거리 테이블에 A번 노드에서 B 노드로 이동하는 비용이 3으로 기록되어 있을때, A번 노드에서 1번 노드를 거쳐 B번 노드로 이동하는것이 2라고 밝혀지면, A번 노드에서 B번 노드로 이동하는 비용을 2로 갱신하는 것이다. 

따라서 알고리즘에서는 현재 확인하고 있는 노드를 기준으로 N - 1개의 노드 중에서 서로 다른 노드 (A, B)쌍을 선택한다. 이후에 A → 1번 노드 → B로 가는 비용을 확인한 뒤에 최단 거리를 갱신한다. 다시 말해 N2N^2N2개의 쌍을 단계마다 반복해서 확인한다. 이때 O(N2)O(N^2)O(N2)이므로 볼 수 있기 때문에, 전체 시간 복잡도는 O(N3)O(N^3)O(N3)이라고 할 수 있다. 구체적인 (K번의 단계에 대한) 점화식은 다음과 같다:

따라서 전체적으로 3중 반복문을 이용하여 이 점화식에 따라 최단 거리 테이블을 갱신하면 된다. 위의 점화식이 의미하는 내용을 말로 풀어 설명하자면, 'A에서 B로 가는 최소 비용'과 'A에서 K를 거쳐 B로 가는 비용'을 비교하여 더 작은 값으로 갱신하겠다는 것이다. 즉, '바로 이동하는 거리'가 '특정 노드를 거쳐서 이동하는 거리'보다 더 많은 비용을 가진다면 이를 더 짧은 것으로 갱신한다는 것이다. 다음 그림을 통해서 구체적인 예시를 확인해보도록 하자.

이런 그래프가 있을 때, 우리는 다음처럼 초기 테이블을 설정할 수 있다. 초기 상태인 [step 0]에서는 '연결된 간선'은 단순히 그 값을 채워 넣고, 연결되지 않은 간선은 '무한'이라는 값을 넣는다. 마찬가지로 실제 구현에서는 10억과 같이 임의의 큰 값을 '무한'이라고 넣는다. 앞서 다익스트라에서와 마찬가지로 파이썬에서는 int(1e9)를 이용하는 것이 일반적이다. 2차원 리스트에서 각 값에 해당하는 DabD_{ab}Dab​는 'a에서 b로 가는 최단 거리'이다.

예를 들어 1번 노드에서 4번 노드로 가는 비용은 6이기 때문에 다음의 2차원 리스트의 첫 번째 행의 네 번째 열의 값이 6인 것을 확인할 수 있다. 그리고 자기 자신에서 자기 자신으로 가는 비용은 0이므로, (1 ≤ i ≤ n)의 범위를 가지는 모든 i에 대하여 DiiD_{ii}Dii​는 0이라는 값으로 초기화한다. 즉, 왼쪽 위에서 오른쪽 아래로 내려가는 대각선에 놓인 모든 원소는 0이다.

# 9-3.py 플로이드 워셜 알고리즘 소스코드

INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

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

# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b
# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    # A에서 B로 가는 비용은 C라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if graph[a][b] == INF:
            print("INFINITY", end=" ")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(graph[a][b], end=" ")
    print()

⚙️ 가장 빠르게 도달하는 방법

최단 경로(Shortest Path) 는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기' 문제 라고도 불리운다. 최단 경로 알고리즘에는 다양한 유형이 존재하는데, 상황에 맞는 알고리즘이 이미 정립 되어 있다.

예를 들어, '한 지점에서 다른 특정 지점 까지의 최단 경로를 구하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등의 다양한 사례가 존재한다. 이런 사례에 맞는 알고리즘을 알고 있다면 문제를 좀 더 쉽게 풀 수 있다.

최단 경로 문제는 보통 그래프를 이용해 표현 할 수 있는데, 각 지점은 그래프에서 '노드'로 표현되고, 지점간 연결된 도로는 그래프에서 '간선' 으로 표현된다.

코딩 테스트에서 가장 많이 등장하는 다익스트라 최단 경로와 플로이드 위셜 알고리즘 유형을 다뤄 보도록 하겠다.

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

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.

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

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

다익스트라 알고리즘은 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신 한다는 특징이 있다.(이러한 1차원 리스트를 최단거리 테이블 이라고 한다.) 매번 현재 처리중인 노드를 기준으로 주변 간선을 확인한다. 나중에 현재 처리중인 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 '더 짧은 경로도 있었네? 이제부턴 이 경로가 제일 짧은 경로야' 라고 판단 하는 것이다. 따라서 '방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 확인'해 그 노드에 대하여 4번 과정을 수행 한다는 점에서 그리디 알고리즘으로 볼 수 있다.

다익스트라 알고리즘을 구현하는 방법은 2가지 이다.

1. 구현하기 쉽지만 느리게 동작하는 코드
2. 까다롭지만 빠른 코드

우선, 다익스트라 알고리즘의 동작 원리를 살펴보자. 다음과 같은 그래프가 있을 때 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 문제를 생각해보자.

예시에서 출발 노드를 1이라고 해보자. 1번 노드에서 다른 모든 노드로의 최단 거리를 계산해볼 것이다. 초기 상태에서는 다른 모든 노드로 가는 최단 거리를 '무한'으로 초기화 한다(999,999,999). 앞으로 이런(무한) 값을 대입 할때는 int(e9)를 사용하겠다.

-step 0 : 먼저 방문하지 않는 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는데, 출발 노드에서 출발 노드로의 거리는 0으로 보기 때문에 처음에는 출발 노드가 선택된다.

-step 1 : 이제 1번 노드를 거쳐 다른 노드로 가는 비용을 계산한다. 즉, 1번 노드와 연결된 모든 간선을 하나씩 확인하면 된다. 현재 1번 노드에서 오는 비용은 0이므로, 1번 노드를 거쳐 2번, 3번, 4번 노드로 가는 최소 비용은 차례대로 2(0 + 2), 5(0 + 5), 1(0 + 1) 이다. 현재 2번, 3번, 4번 노드로 가는 비용이 '무한'으로 설정 되어 있는데, 세 노드에 대해 가장 짧은 값을 찾았으므로 각각 새로운 값으로 갱신한다. 처리된 결과는 다음과 같다. 현재 처리중인 노드와 간선은 하늘색으로, 이미 처리한 노드는 회색으로, 이미 처리한 간선은 점선으로 표현했다.

-step 2: 이후의 모든 단계에서도 마찬가지로 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 해야 한다. 따라서 [step 2]에서는 4번 노드가 선택된다. 이어서 4번 노드를 거쳐 갈 수 있는 노드를 확인한다. 4번 노드에서 갈 수 이쓴ㄴ 노드는 3번과 5번이다. 이때, 4번 노드까지의 거리는 1이므로 4번 노드를 거쳐 3번과 5번으로 가는 최소 비용은 차례대로 4(1 + 3), 2(1 + 1)이다. 이 두 값은 기존의 리스트에 담겨 있던 값보다 작으므로 다음처럼 리스트가 갱신된다. 

-step 3: [step 3]에서는 2번 노드가 선택된다. 2번과 5번 노드까지의 거리가 2로 같지만, 보통 이럴때는 숫자가 더 작은 노드를 선택한다. 그리고 2번 노드를 거쳐 도달 할 수 있는 노드 중에서 거리가 더 짧은 경우가 있는지 확인한다. 이번 단계에서 2번 노드를 거쳐서 가는 경우, 현재의 최단 거리를 더 짧게 갱신 할 수 있는 방법은 없다. 예를 들어, 2번 노드를 거쳐 3번 노드로 가는 경우, 5(2 + 3)의 비용이 발생한다. 하지만 현재 이미 최단 거리 테이블에서 3번 노드까지의 최단 거리는 4이므로, 값이 갱신되지 않는다.

-step 4: 이번에는 5번 노드가 선택된다(한번도 방문하지 않은 노드중 값이 가장 작은 노드를 선택). 5번 노드를 거쳐 3번 노드와 6번 노드로 갈 수 있다. 여기서 3번 노드로 가는 길은 3(1+1+1)의 비용이 든다. 하지만 현재 리스트에는 3보다 큰 4의 값이 저장되어 있으므로, 이 값을 최단경로 값인 3으로 업데이트 해 준다. 또, 6은 현재 한번도 방문되지 않아 '무한'으로 설정되어 있으므로, 5를 거쳐 6까지 가는 비용인 4(1+1+2)로 업데이트 해 준다.

-step 5: 현재 방문하지 않은 노드 2개(3, 6)중, 값이 작은 3번 노드를 선택한다. 3번 노드를 통해 방문 할 수 있는 노드는 2번, 6번이다. 하지만 이미 1번 노드에서 2번 노드로 가는 길의 값은 2 이므로(3보다 작으므로), 값을 그대로 둔다. 또한, 3번을 통해 6번으로 가는 경로는 총 8(3 + 5)의 값을 가지므로, 현재 테이블의 값을 그대로 둔다. 

-step 6: 방문하지 않은 마지막 노드는 6이다. 하지만 6번 노드에서 갈 수 있는 노드는 없으므로, 테이블을 그대로 둔다.

최단거리 테이블이 의미하는 바는 1번 노드로부터 출발 했을때 2번, 3번, 4번, 5번, 6번 노드까지 가기 위한 최단 경로가 각각 2,3,1,2,4 라는 의미이다.

이제, 원리를 파악했으니 아까 언급한 방법들에 대해 더 자세히 알아보자. 

🖇️ 방법 1 : 간단한 다익스트라 알고리즘

간단한 다익스트라 알고리즘은 O(v^2)의 시간 복잡도를 가진다. 여기서 V는 노드의 갯수를 의미한다. 이 알고리즘은 직관적이다. 처음에 각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언한다. 이후 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택' 하기 위해 매 단계마다 1차원 리스트의 모든 요소를 확인(순차 탐색) 한다. 

참고로 다음 소스 코드에서는 input()보다 더 빠르게 동작하는 sys.std.readline()을 사용했다. 또한,DFS/BFS와 마찬가지로 모든 리스트는 (노드의 개수  + 1)의 크기로 할당하여, 노드의 번호를 인덱스로 하여 바로 접근 할 수 있도록 했다

import sys
input = sys.stdin.readline
INF = int(e9)

#노드의 개수, 간선의 개수를 입력받기
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 = map(int, input.split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
	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 nad 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):
	#도달할 수 없는 경우, 무한(INFIINITY)라고 출력
    if distance[i] == INF:
    	print("INFINITY")
    #도달할 수 있는 경우 거리를 출력
    else:
    	print(distance[i])

앞서 시간 복잡도는 O(V^2)라고 했다. 왜냐하면 총 O(V)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색 해야하고, 현재 노드와 연결된 노드를 매번 일일히 확인하기 때문이다. 노드의 갯수가 10,000개를 넘어가는 문제라면 이 코드로는 문제를 해결하기 어렵다. 노드의 갯수 및 간선의 갸수가 많을때는 이어서 설명할 '개선된 다익스트라 알고리즘'을 이용해야 한다.

🖇️ 방법 2 : 개선된 다익스트라 알고리즘

지금 배울 방법의 시간 복잡도는 O(ElogV)이다. 여기서 V는 노드의 갯수이고, E는 간선의 개수를 의미한다. 간단한 다익스트라 알고리즘은 '최단 거리가 가장 짧은 노드'를 찾기 위해서, 매번 최단 거리 테이블을 선형적으로(모든 원소를 앞에서부터 하나씩) 탐색해야 했다.

개선된 다익스트라 알고리즘에서는 힙 자료구조를 사용한다. 힙 자료구조를 이용하게 되면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다. 이 과정에서 선형 시간이 아닌 로그 시간이 걸린다. N = 1,000,000 일때, logN이 20인것을 감안하면 속도가 획기적으로 빨라지는 것임을 이해할 수 있다.

🔌 힙 설명

힙 자료구제에 대해서 간단히 알아보자. 힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조중 하나이다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는점이 특징이다. 다음은 스택, 큐, 우선순위 큐를 비교한 테이블은 다음과 같다.

이러한 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내 확인해야 하는 경우를 가정해보자. 이런 경우에 우선순위 큐 자료구조를 이용하면 효과적이다.

파이썬에서는 우선순위 큐가  필요할 때 PriorityQueue혹은 heapq를 사용 할 수 있는데, 이 두 라이브러리는 모두 우선순위 큐 기능을 지원한다. heapq가 더 빠르기 때문에 시행 수간이 제한된 상황에서는 heapq를 사용하는것을 권장한다. 우선순위 값을 표현할때는 일반적으로 정수형 자료형의 변수가 사용된다. 예를 들어 물건 정보가 있고, 이 물건 정보는 물건의 가치와 물건의 무게로만 구성된다고 가정해보자. 그러면 모든 물건 데이터를 (가치, 물건)으로 묶어서 우선순위 큐 자료구조에 넣을 수 있다. 이후에 우선순위 큐에서 물건을 꺼내게 되면, 항상 가치가 높은 물건이 먼저 나오게 된다. 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫 번째 원소를 기준으로 우선순위를 설정한다. 따라서 데이터가 (가치, 물건)으로 구성된다면 '가치'값이 우선순위 값이 되는 것이다. 

또한 우선순위 큐를 구현할때는 내부적으로 최소 힙 혹은 최대 힙을 이용한다. 최소 힙을 사용하는 경우 '값이 낮은 데이터가 먼저 삭제'되며, 최대 힙을 이용하는 경우 '값이 큰 데이터가 먼저 삭제'된다. 파이썬에서는 기본적으로 최소 힙 구조를 사용하는데, 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선하여 방문하므로 최소 힙 구조를 기반으로 하는 파이썬의 우선순위 큐 라이브러리를 그대로 사용하면 적합하다.

또한 최소 힙을 최대 힙처럼 사용하기 위해서 일부러 우선순위에 해당하는 값에 음수 부호(-)를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음에 다시 음수 부호(-)를 붙여서 원래의 값으로 돌리는 방식을 사용 할 수 있다.

앞서 우선순위 큐를 구현할 때는 힙 자료구조를 이용한다고 했는데, 사실 우선순위 큐를 구현하는 방법은 다양하다. 단순히 리스트를 이용해서 구현 할 수 도있다. 

최소 힙을 이용하는 경우 힙에서 원소를 꺼내면 '가장 값이 작은 원소'가 추출되는 특징이 있으며, 파이썬의 우선순위 큐 라이브러리는 최소 힙에 기반한다는 점을 기억하자. 단순히 우선순위 큐를 이용해서 시작 노드로부터 '거리'가 짧은 노드 순서대로 큐에서 나올 수 있도록 다익스트라 알고리즘을 작성하면 된다.

이번엔 단계별로 우선순위 큐가 어떻게 변하는지를 중심으로 살펴보자. 우선순위 큐 그림에서는 각 원소를 거리가 짧은 순서대로 왼쪽부터 나열하겠다. 우선순위 큐를 적용하여도 다익스트라 알고리즘이 동작하는 기본 원리는 동일하다. 최단 거리를 저장하기 위한 1차원 리스트(최단 거리 테이블)는 아까와 같이 그대로 이용하고, 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용한다고 보면 된다.

- step 0 : 역시 1번 노드가 출발 노드인 경우를 고려해보자. 여기서는 다음과 같이 출발 노드를 제외한 모든 노드의 최단 거리를 무한으로 설정한다. 이후에 우선순위 큐에 1번 노드를 넣는다. 이때, 1번 노드로 가는 거리는 자기 자신까지 도달하는 거리이기 때문에 0이다. 즉, (거리:0, 노드 :1)의 정보를 가지는 객체를 우선순위 큐에 넣으면 된다.

파이썬에서는 간단히 튜플 (0, 1)을 우선순위 큐에 넣는다. 파이썬의 heapq 라이브러리는 원소로 튜플을 입력받으면 튜플의 첫번째 원소를 기준으로 우선순위 큐를 구성한다. 따라서 (거리, 노드 번호) 순서대로 튜플 데이터를 구성해 우선순위 큐에 넣으면 거리순으로 정렬된다.

-step 1 : 우리는 우선순위큐를 이용하고 있으므로 거리가 가장 짧은 노드를 선택하기 위해서는 우선순위 큐에서 그냥 노드를 꺼내면 된다. 기본적으로 거리가 짧은 원소가 우선순위 큐의 최상위 원소로 위치해 있다. 따라서 우선순위 큐에서 노드를 꺼낸 뒤에 해당 노드를 이미 처리한 적이 있다면 무시하면 되고, 아직 처리하지 않은 노드에 대해서만 처리하면 된다. 

따라서 [step 1]의 우선순위 큐에서 원소를 꺼내면 (0, 1)이 나온다. 이는 1번 노드까지 가는 최단 거리가 0이라는 의미이므로, 1번 노드를 거쳐 2번, 3번, 4번 노드로 가는 최소 비용을 계산한다. 차례대로 2(0 + 2), 5(0 + 5), 1(0 + 1)이다. 현재 2번, 3번, 4번 노드로 가는 비용이 '무한'으로 설정되어 있는데, 더 짧은 경로를 찾았으므로 각각 갱신하면 된다. 이렇게 더 짧은 경로를 찾은 노드 정보들은 다시 우선순위 큐에 넣는다. 현재 처리 중인 노드와 간선은 하늘색으로, 이전 단계에서 처리한 노드는 회색, 간선은 점선으로 표시했다.

- step 2 : 이어서 다시 우선순위 큐에서 원소를 꺼내어 동일한 과정을 반복한다. 이번에는 (1, 4)의 값을 갖는 원소가 추출된다. 아직 노드 4를 방문하지 않았으며, 현재 최단 거리가 가장 짧은 노드가 4이다. 따라서 노드 4를 기준으로 노드 4와 연결된 간선들을 확인한다. 이때 4번 노드 까지의 최단 거리는 1 이므로 4번 노드를 거쳐 3번과 5번 노드로 가는 최소 비용은 차례대로 4(1 + 3), 2(1 + 1) 이다. 이는 기존에 담겨있던 값보다 작기 때문에 리스트의 값이 갱신되고, 우선순위 큐에는 (4, 3), (2, 5)라는 두 원소가 추가로 들어가게 된다. 

- step 3 : 마찬가지로 step 3에서는 노드 2에 대해 처리한다(거리가 가장 짧고, 노드 번호가 낮은 순서대로, 우선순위 큐의 특징 활용). 마찬가지로 2번 노드를 거쳐 도달 할 수 있는 노드 중에서 거리가 더 짧은 노드가 있는지 확인한다. 2번 노드에서 갈 수 있는 노드는 총 2개, 각각 3번과 4번 노드이다. 2번 노드를 거쳐 3번과 4번으로 가는 각각의 비용은 5(2 + 3), 4(2+2)이다. 하지만 이미 리스트에서 3번과 4번의 비용은 각각 4, 1이므로, 업데이트를 해주지 않아도 된다. 따라서 우선순위 큐에는 어떠한 원소도 들어가지 않고, 다만 방금 검사한 노드를 빼줘야 한다.

- step 4 : 이번 단계에서는 노드 5에 대해 처리한다. 노드 5에서 갈 수 있는 노드는 3, 6이고, 각각의 비용은 3(2 + 1), 4(2 + 2) 이다.

이 값들은 현재 테이블에 있는 값들보다 작으므로, 현재 테이블의 3번, 6번 노드의 거리를 3, 4로 각각 업데이트 해주고, (3,3)과 (4, 6)을 우선순위 큐에 넣어준다.

- step 5 :  마찬가지로 이번에는 우선순위 큐에서 (3,3)을 꺼내 처리한다. 노드 3에서 갈 수 있는 노드는 2, 6이고, 각각의 비용은 6(3 + 3), 8(3 + 5) 이다. 이는 현재 값보다 크므로, 리스트를 업데이트 하지 않아도 된다. 

- step 6 : 이어서 원소 (4, 3)을 꺼내어 처리해보자. 다만 3번 노드는 이전에 처리 된 적이 있다. 하지만 현재 최단거리 테이블에서 3번 노드까지의 최단거리는 3이다. 따라서 현재 노드인 3번에 대해서는 이미 처리된 것으로 볼 수 있으므로 현재 우선순위 큐에서 꺼낸 4, 3 이라는 원소는 무시하면 된다.

- step 7 : 이어서 원소 (4, 6)이 꺼내진다. 따라서 6번 노드에 대해 처리하자. 하지만 6번 노드에서 뻗어 나갈 수 있는 노드는 존재하지 않으므로 그냥 우선순위 큐에서 방금 처리한 (4, 6)만 빼준다.

- step 8 : 마지막으로 남은 원소를 꺼내지만, 마찬가지로 아까 처리된 노드이므로 무시한다.

이와 같이 모든 단계를 거친 후에 최단 거리 테이블에 남아있는 0 2 3 1 2 4가 각 노드로의 최단 거리이다. 위의 방법에서는 최단 거리가 가장 짧은 노드를 찾기 위해 우선순위 큐를 이용했으며, 앞서 본 방법 1보다 훨씬 더 빠르게 동작한다. 파이썬에서 표준 라이브러리로 제공하는 PriorityQueue와 heapq는 데이터의 갯수가 N일때, 하나의 데이터를 삽입 및 삭제하는데 걸리는 시간은 O(logN) 이다. 다음은 소스 코드이다.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
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 = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    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):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

앞의 코드와 비교했을때 get_smallest_node()라는 함수를 작성 할 필요가 없다. '최단거리가 가장 짧은 노드'를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용 할 수 있다.  

아직도 기억이 선명하다. 2000번대 자료구조, 알고리즘 수업을 들었을 당시 호기롭게 Leetcode를 결제하여 DP문제를 푸는데 아무것도 이해가 가지 않았다. 너무 답답한 마음에 집에 가는길에 노래 대신 DP 알고리즘이 어떤 내용인지 들으면서 갔던 기억이 난다. 그렇다면, 이 DP알고리즘은 왜 사용할까?

🔊반복되는 연산을 줄이자

알겠지만, 컴퓨터의 메모리와 연산 속도에는 한계가 있다. DP는 메모리 공간을 조금 더 사용해 실행 시간을 비약적으로 감소 시킬 수 있는 알고리즘이다. 이해가 잘 가지 않을테니 DP를 활용해 어떤 문제를 풀 수 있을지 보자.

DP의 가장 대표적인 예는 피보나치 수열이다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있다.

수학자들은 점화식을 이용해 이 피보나치 수열의 관계식을 표현한다. 피보나치 수열의 점화식은 너무 유명한 존재이니 따로 설명하진 않겠다. 피보나치 수열은 다음 두가지의 특징을 가진다

• n번째 피보나치 수 = (n-1) + (n-2)번째 피보나치 수
• 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1

그렇다면, 이 점화식을 이용해 피보나치 수열을 어떻게 풀 수 있을까? 예를들어 f(4)를 계산 한다고 해 보자. 

이렇게 보면 아직까진 그렇게 연산 횟수가 많아 보이진 않는다. f(4)의 연산 횟수는 5회이다. 하지만 f(6)일때를 생각 해보자.

f(4)보다 단지 2번째 뒤의 계산(f(6))을 하려고 했지만 15회의 연산을 한다. 결국, N이 늘어날수록, 이 방법은 연산 횟수가 기하급수적으로 늘어난다.

그림을 보면 동일한 연산들이 여러번 수행 되는것을 볼 수 있다. 그림에서 f(3)은 3번 호출되었다. 여기서의 '호출'이란 단순히 O(1)의 호출을 의미 하는것이 아니라, 피호출자의 연산 속도가 O(N)이라면, 호출을 할때마다 O(N)의 시간이 소요 되는것이다.

이때, 동적 프로그래밍을 이용하면 이 문제를 해결 할 수 있다. 다만, 항상 DP를 사용할 순 없으며, 다음 조건을 만족할때 사용 할 수 있다.

• 큰 문제를 작은 문제로 나눌 수 있다.
• 작은 문제에서 구한 정답은 그것을 푸는 큰 문제에서도 동일하다.

피보나치 수열은 위 조건들을 만족하는 가장 대표적인 문제이다. 이제 피보나치 수열 문제를 메모제이션(Memozation)을 활용해 풀어보자. 여기서 메모제이션이란, DP를 구현하는 방법중 하나로, 한번 구현한 결과를 별도의 메모리에 저장하여 같은 식을 호출하면 메모리에 메모된 결과를 그대로 가져오는 기법이다. 메모제이션이 이해가 안간다면, 캐싱(Caching)을 생각해보면 된다. 다음 소스코드를 살펴보자. 다음과 같이 피보나치 수열을 DP를 이용해 풀면 O(N)의 수행시간이 소요된다.

#한번 계산된 결과를 저장하기 위한 테이블 선언, 초기화
d = [0] * 100

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

정리하자면 큰 문제를 작게 나누고, 같은 문제라면 한번씩만 풀어 효율적으로 계산을 하는 것이다. 여기서 분할 정복이 떠오른다. 분할-정복 알고리즘이란 큰 문제를 작은 문제들로 나누어 문제를 해결 하는것이다. DP와 분할-정복의 가장 큰 차이점은 DP는 분할된 작은 문제들이 서로 영향을 끼치고 있음을 나타낸다.

재귀 함수를 사용하면 운영체제 에서는 함수를 다시 호출했을때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생 할 수 있다. 따라서 재귀함수 대신 반복문을 사용하여 DP를 구현하는것이 더 효율적이다.

위 트리에서 볼 수 있듯, 실제 호출되는 함수는 파란색 부분이다. 위에서 단순 재귀 함수와 점화식을 썼을때와 비교하면 훨씬 더 적은 연산으로 수행 할 수 있다.

이처럼 재귀 함수를 사용하여 DP를 구현한 방법을, 큰 문제를 풀기 위해 작은 문제를 호출 한다고 하여 탑다운 방식(Topdown) 이라고 한다. 반면, 단순 반복문을 이용하여 소스코드를 작성하는 방식은 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업(BottomUp) 이라고 한다. 피보나치 수열을 보텀업 방식으로 해결한 소스 코드는 다음과 같다. 동일한 원리를 적용하되, 단순히 반복문을 이용해 문제를 해결하면 된다. 다음은 보텀업 방식의 피보나치 수열 소스코드이다.

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

#첫번째 피보나치 수와 두번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

#피보나치 함수를 반복문으로 구현(보텀업 DP)
for i in range(3, n + 1):
	d[i] = d[i - 1] + d[i - 2]
    
return d[n]

DP의 전형적인 형태는 보텀업 방식이다. 보텀업 방식에서 사용되는 저장소는 'DP 테이블'이라 불리우며, 메모제이션은 탑다운 방식에 국한되어 사용되는 단어이다.

DP문제를 푸는 첫번째 단계는 주어진 문제가 DP유형인지 확인 하는것이다. 특정한 문제를 완전 탐색으로 수행했을때 시간이 오래 걸린다면 DP를 적용할 수 있는지 확인 해보자.

🧷 실전 문제

이제 실전 문제를 풀어 보도록 하자.

문제 1: 

이 문제는 잘 알려진 다이나믹 프로그래밍 문제이다. 피보나치 수열 문제를 다뤄보았던 것처럼 문제를 풀기 전의 함수가 호출되는 과정을 그림으로 그려보면 이해하는 데 도움이 된다. 이 문제에서 동일한 함수에서 구하는 값들은 동일하게 하므로 다이나믹 프로그래밍을 효과적으로 사용할 수 있다.

# 정수 X를 입력받기
x = int(input())

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
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])

문제 2:

이 문제를 어떻게 동적 프로그래밍으로 구현 할 수 있을까? 동적 프로그래밍의 두가지 조건을 다시 떠올려 보자.

1. 큰 문제를 작은 하위 문제들로 나눌 수 있어야 한다.

2. 나누어진 작은 문제들의 답은 큰 문제의 답과 일치한다.

일단, 이 문제를 그림으로 도식화를 하면 다음과 같은 케이스들이 나온다.

[1,3,1,5]의 리스트가 주어질때, 위와 같은 8가지 케이스중 최댓값(8)을 리턴하면 된다. 

그럼 이 문제의 점화식은 어떻게 세울까? 왼쪽부터 차례로 식량 창고를 턴다고 가정을 해 보자. 우리는 단 2가지 경우만 생각해보면 된다.

따라서 a와 b중에서 더 큰 값을 선택하면 된다. 여기서 알아둘 점은 i - 3번째 이하의 식량창고에 대해서는 고려할 필요가 없다. 왜냐하면 한칸 이상 떨어진 식량 창고는 항상 털 수 있기 때문이다. 따라서 i번째 식량창고에 있는 식량의 양이 k 라고 했을때 점화식은 다음과 같다.

다음은 보텀업 방식으로 풀이를 한 소스코드이다.

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

#보텀업 방식의 dp구현
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
	d[i] = max(d[i - 1], d[i - 2] + array[i])

return (d[n-1])

이진 탐색(Binary Search)은 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘이다. 이진 탐색을 공부하기 전에 선형 탐색(Linear Search)에 대해 먼저 알아야 한다. 

선형 탐색은 리스트 내의 특정 요소를 찾기 위해 리스트의 처음부터 요소를 찾을때까지 순서대로 리스트를 탐색 하는것이다. 보통 정렬되지 않은 리스트에서 요소를 찾을때 사용된다. 선형 탐색은 정말 자주 사용되는데, 리스트에 특정 값이 있는지 체크할 때도 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 갯수를 셀 수 있는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다.

다음은 선형 탐색을 소스 코드로 구현한 것이다. 입력값 s는 문자열들을 담은 리스트라고 가정하자.

for i in s:
	if i == '구름'
    	return i

이 코드는 여러개의 문자열이 담긴 리스트 s를 for문을 통해 순회하며, 만약 현재 검사중인 리스트의 요소가 '구름'이라면, 그 문자열을 리턴하는 코드이다. 

따라서 데이터의 갯수가 N개일때 N번의 검색을 하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이다.

📎 이진 탐색 : 반으로 쪼개면서 탐색하기

이진 탐색은 배열의 내부가 정렬이 되어 있어야만 수행 할 수 있는 알고리즘이다. 데이터가 무작위 상태일땐 사용 할 수 없지만, 정렬이 되어있다면 이진 탐색을 수행 할 수 있다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다.

이진 탐색은 위치를 나타내는 변수 3개를 사용하는데, 탐색하고자 하는 범위의 시작점, 끝점, 중간점이다. 

아래 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 보자.

전체 데이터의 갯수는 10개이지만, 이진 탐색을 이용해 총 3번의 탐색으로 원소를 찾을 수 있었다. 이진 탐색은 한번 확인 할때마다 확인하는 원소의 갯수가 반으로 줄어든다는 점에서 시간 복잡도가 O(logN)이다.

다음은 반복문으로 쓰여진 재귀함수 코드이다.

def bSearch(arr, target, start, end):
	while start <= end:
    	mid = (start + end) // 2
        # 찾은 경우 중간 인덱스 반환
        if arr[mid] == target
        	return mid
        # 중간값이 target보다 큰 경우 왼쪽 부분 탐색
        elif arr[mid] > target:
        	end = mid - 1
        #중간값이 target보다 작은 경우 오른쪽 부분 탐색
		else:
        	start = mid + 1
        return None

📌 트리 자료구조

트리 자료구조를 간단히 알아보자. 트리는 노드와 간선의 연결로 표현되며, 여기에서 노드는 어떤 정보를 담고 있는 객체 정도로 이해 할 수 있다. 트리 자료구조는 그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위해 사용된다. 트리 자료구조는 몇가지 중요한 특징이 있다.

• 트리는 부모-자식 노드간의 관계로 표현된다.
• 트리의 최상단 노드를 루트 노드라고 한다.
• 트리의 최하단 노드를 단말 노드(leaf node)라고 한다.
• 트리에서 일부를 떼어내도 트리 구조이며 이를 서브트리 라고 한다.
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.

정리하면 큰 데이터베이스를 다루는 소프트웨어는 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능하다. 그렇다면 이런 트리 구조를 이용하면 어떤 방식으로 이진 탐색이 가능할까?

📌이진 탐색 트리(Binary Search Tree)

트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리이다. 이진 탐색 트리란 이진 탐색이 동작 할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다. 

이진 탐색 트리는 다음과 같은 특징을 가진다.

• 부모 노드보다 왼쪽 자식노드가 작다.
• 부모 노드보다 오른쪽 자식 노드가 더 크다.

좀 더 간단하게 표현하면 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 

이처럼 이진 탐색 트리가 이미 구현되어 있다고 가정하고 다음 그림과 같은 이진 탐색 트리에서 데이터를 조회하는 과정만 살펴 보겠다. 다음은 찾는 원소가 37일때 동작하는 과정이다. 

이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편이다. 예를들어 데이터의 갯수가 1,000개를 넘어 가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심 해보자. 하지만 이렇게 입력 데이터의 갯수가 많은 문제에 input()함수를 사용하면 동작 속도가 느려 시간 초과로 오답 판정을 받을 수 있다. 이처럼 입력 데이터가 많은 문제는 sys 라이브러리의 readline()함수를 이용하면 시간 초과를 피할 수 있다.

import sys
# 하나의 문자열 데이터를 입력받기
input_data = sys.stdin.readline().rstrip()

# 입력받은 문자열 그대로 출력
print(input_data)

sys 라이브러리를 사용할 때는 한 줄 입력받고 나서 rstrip() 함수를 꼭 호출해야 한다. 소스코드에 readline()으로 입력하면 입력 후 엔터Enter가 줄 바꿈 기호로 입력되는데, 이 공백 문자를 제거하려면 rstrip() 함수를 사용해야 한다. 코드가 짧으니, 관행적으로 외워서 사용하자. 

저번 포스팅에서 다루었던 삽입, 선택 정렬에 이어 이번에는 퀵, 계수 정렬을 공부하고 넘어가 보자.

2024.07.09 - [LeetCode + 알고리즘] - [Algorithm]정렬(1) - 선택, 삽입 정렬

📍퀵 정렬(Quick Sort)

퀵 정렬은 지금까지 사용되는 모든 정렬 알고리즘중 가장 많이 사용되는 알고리즘이다. 이름에서 부터 알 수 있듯이 실행 시간이 빠른, 효율적인 정렬 알고리즘이다. 그렇다면 퀵 정렬은 어떠한 방식으로 동작될까?

'기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?'

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환 후 리스트를 나누는 방식으로 동작한다. 여기서 이 기준을 '피벗(pivot)' 이라 부른다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗이라 표현한다. 이 피벗을 어떻게 설정 하느냐에 따라 알고리즘의 효율이 달라지는데, 여기서는 가장 대표적인 분할 방식인 호어 분할 방식을 기준으로 퀵 정렬을 설명 하겠다. 호어 분할 방식에서의 피벗은 항상 리스트의 첫번째 요소를 피벗으로 삼는다. 이와 같이 피벗을 설정한 후에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부턴 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환 해준다. 이러한 과정을 반복하면 '피벗'에 대해 정렬이 수행된다. 다음과 같이 초기 데이터가 구성되어 있다고 해 보자.

퀵 정렬은 전체를 3개의 파트로 나눠서 보는게 편하다.

다음은 퀵 정렬의 소스 코드이다.

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

def quick_sort(array, start, end):
    if start >= end:  # 원소가 1개인 경우 종료
        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)

📚 퀵 정렬의 시간 복잡도

퀵 정렬은 평균적으로 O(n log N)의 시간 복잡도를 가진다. 이는 O(N^2)를 가지던 삽입, 선택 정렬에 비해 매우 빠른 정렬 알고리즘이다. 일반적으로 cs에서의 log는 밑이 2인 로그를 의미한다. 즉, 데이터의 갯수가 1,000일때 밑이 2인 로그를 취하면 대략 10이다. 이는 O(N^2)일때는 1,000,000에 비해 10은 매우 작은 숫자이다.

데이터의 갯수가 많을수록 차이는 극명하게 드러난다. 다음 표를 보면 데이터의 갯수가 많을수록 퀵 정렬은 앞서 다루었던 선택 정렬, 삽입 정렬에 비해 압도적으로 빠르게 동작한다고 추측 할 수 있다. BUT, 퀵 정렬에 대해 한가지 명심 해야 할 것이 있다. 퀵 정렬의 평균 시간 복잡도는 O(n log N)이지만, 최악의 경우에는 O(n^2)이다. 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다. 하지만 데이터가 미리 정렬이 어느정도 되어있는 데이터에 대해서는 매우 느리게 동작한다. 이전에 다룬 삽입 정렬은 이미 데이터가 정렬된 상태에서 빠르게 동작한다고 했는데, 퀵 정렬은 그와 반대라고 이해하면 될것 같다. 하지만 파이썬의 .sort()정렬 메서드도 이미 정렬이 된 데이터에 대해 최적화가 되어있기 때문에, 큰 걱정은 하지 않아도 된다.

📍계수 정렬(Count Sort)

계수 정렬 알고리즘은 특정 조건이 부합 할때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 이 정렬 알고리즘은 최악의 경우에도 수행시간 O(N + K)를 보장하지만, 데이터의 크기 범위가 제한되어 정수 형태로 표현 할 수 있을때만 사용 할 수 있다. 예를들어 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다.

📦 파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted()는 퀵 정렬과 비슷한 방식인 병합 정렬을 베이스로 구현되었는데, 이는 최악의 경우에도 O(n log n)을 보장한다. 이러한 sorted()함수는 리스트, 딕셔너리 자료형을 입력받아 정렬된 결과를 출력한다. 집합 자료형이나 딕셔너리 자료형을 입력 받아도 반환되는 결과는 리스트 자료형이다.

• sorted()를 이용한 정렬

arr = [7,5,4,1,0,9,8,2,3,6]
result = sorted(arr)

#결과 : result = [0,1,2,3,4,5,6,7,8,9]

• sort()를 이용한 정렬

arr = [7,5,4,1,0,9,8,2,3,6]
arr.sort()

#결과 : result = [0,1,2,3,4,5,6,7,8,9]

이는 별도의 정렬된 리스트를 반환하지 않고, 내부 원소가 바로 정렬된다. 또한 sort()나 sorted()를 이용할땐 key 파라미터를 입력으로 받을 수 있다. key값으로는 하나의 함수가 들어가야 하며, 이를 기준으로 정렬된다. 예를들어, 리스트의 데이터가 튜플로 구성되어 있을때, 각 데이터의 두 번째 원소를 기준으로 정렬을 원하는 경우 다음과 같이 소스 코드를 작성 할 수 있다.

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
    return data[1]

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

파이썬의 `sorted` 함수와 `list.sort` 메서드에서 `key` 매개변수에는 반드시 함수 또는 람다 표현식이 들어가야 한다. `data[1]`과 같은 직접적인 표현식을 사용할 수는 없다. 대신 `key` 매개변수에 함수를 전달하거나, 람다 표현식을 사용하여 원하는 기준으로 정렬할 수 있다.

다음은 예제를 통해 `key` 매개변수에 함수를 직접 전달하거나 람다 표현식을 사용하는 방법이다.

함수를 사용하는 방법

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

# 함수 정의
def setting(data):
    return data[1]

# 함수를 key 매개변수에 전달
result = sorted(array, key=setting)
print(result)  # 출력: [('바나나', 2), ('당근', 3), ('사과', 5)]

람다 표현식을 사용하는 방법

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

# 람다 표현식을 key 매개변수에 전달
result = sorted(array, key=lambda data: data[1])
print(result)  # 출력: [('바나나', 2), ('당근', 3), ('사과', 5)]

설명

- 함수 사용: `key` 매개변수에 `setting`이라는 함수를 전달하여, 각 튜플의 두 번째 요소를 기준으로 정렬한다.
- 람다 표현식 사용: 람다 표현식을 사용하여 `key` 매개변수에 간단한 함수를 직접 전달한다. `lambda data: data[1]`는 익명 함수로, 각 튜플의 두 번째 요소를 반환한다.

`key` 매개변수에는 함수 또는 람다 표현식만을 사용할 수 있다. 따라서 `data[1]`과 같은 표현식은 직접 사용할 수 없고, 이를 포함하는 함수나 람다 표현식을 사용해야 한다.