코딩 테스트 수업: 자료구조 및 알고리즘
안녕하세요 여러분! 최근에 '코딩테스트: 자료구조 및 알고리즘 개론' 강의를 들은 후기를 공유하고자 합니다. 이 강의는 정말 유익하고 다양한 자료구조 및 알고리즘 문제를 다루고 있어 코딩 테스트 준비에 큰 도움이 되었어요. 코딩테스트 준비를 위한 다양한 코드에 대해서 그에 대한 코드 구현과 해석을 함께 살펴보겠습니다.
1. Two Sum 문제 (반복문)
Two Sum 문제는 주어진 배열에서 두 개의 숫자를 찾아 그 합이 특정 타겟값이 되는 인덱스를 반환하는 문제입니다. 먼저 반복문을 사용한 솔루션을 살펴보겠습니다.
코드
class Solution:
def twoSum(self, nums, target):
n = len(nums)
for i in range(n):
for j in range(i+1, n):
if nums[i] + nums[j] == target:
return [i, j]코드 해석
이 코드는 이중 반복문을 사용하여 배열의 모든 가능한 두 숫자 조합을 검사합니다. nums[i] + nums[j] == target 조건을 만족하는 인덱스를 찾으면 해당 인덱스를 리스트로 반환합니다.
장단점
- 장점: 구현이 직관적이고 이해하기 쉽습니다.
- 단점: 시간 복잡도가 O(n^2)으로, 입력 배열의 크기가 커질수록 성능이 급격히 저하됩니다.
Two Sum 문제는 주어진 배열에서 두 개의 숫자를 찾아 그 합이 특정 타겟값이 되는 인덱스를 반환하는 문제입니다. 이 문제를 반복문과 재귀를 사용하여 해결하는 방법을 배웠습니다. 반복문을 사용한 방법은 구현이 직관적이고 이해하기 쉬웠지만, 시간 복잡도가 O(n^2)로 비효율적이었습니다. 반면, 재귀를 사용한 방법은 코드가 유연하고 확장 가능하지만, 재귀 호출이 많아질 경우 성능 저하가 발생할 수 있었습니다.
2. Two Sum 문제 (재귀)
이번에는 재귀를 사용하여 Two Sum 문제를 해결하는 방법을 살펴보겠습니다.
코드
def solution(nums, target):
n = len(nums)
def recur(ans, start):
if len(ans) == 2:
if nums[ans[0]] + nums[ans[1]] == target:
return ans
return False
for i in range(start, n):
ans.append(i)
if recur(ans, i + 1):
return ans
ans.pop()
return recur([], 0)
print(solution(nums=[4, 9, 7, 5, 1], target=14))코드 해석
이 코드는 재귀를 통해 모든 가능한 두 숫자 조합을 시도합니다. recur 함수는 인덱스를 누적하여 두 개의 인덱스를 찾으면 검사를 하고, 타겟값과 일치하면 그 인덱스를 반환합니다.
장단점
- 장점: 재귀적으로 문제를 접근하여 코드를 보다 유연하게 확장할 수 있습니다.
- 단점: 재귀 호출이 많아질 경우 스택 오버플로우 위험이 있습니다. 또한, 성능 면에서 반복문보다 효율적이지 않습니다.
Combinations 문제는 주어진 숫자 범위에서 k개의 숫자를 뽑아 가능한 모든 조합을 생성하는 문제입니다. 이 문제는 재귀를 사용하여 해결할 수 있었고, 재귀적으로 접근하여 문제를 명확하고 간결하게 해결할 수 있었습니다. 하지만 호출 스택이 커질 수 있다는 단점이 있었습니다.
피로도 문제, 자물쇠와 열쇠 문제, 올바른 괄호 문제, 그리고 그래프 탐색 (BFS 및 DFS) 문제에 대해 다루겠습니다. 각 문제에 대한 코드 구현과 해석을 통해 여러분의 이해를 도울 수 있기를 바랍니다.
4. 순열 조합 문제: 피로도
피로도 문제는 주어진 던전을 탐험하면서 가능한 최대 던전 수를 찾는 문제입니다. 이 문제는 재귀와 itertools를 사용하여 해결할 수 있습니다.
재귀를 사용한 솔루션
def solution(k, dungeons):
answer = 0
n = len(dungeons)
visited = [0] * n
def backtrack(k, cnt):
nonlocal answer
if cnt > answer:
answer = cnt
for i in range(n):
if k >= dungeons[i][0] and not visited[i]:
visited[i] = True
backtrack(k - dungeons[i][1], cnt + 1)
visited[i] = False
backtrack(k, 0)
return answer코드 해석
- 재귀 함수
backtrack: 현재 피로도k와 탐험한 던전 수cnt를 인자로 받아 던전을 탐험합니다. - 방문 배열
visited: 이미 탐험한 던전을 기록하여 중복 탐험을 방지합니다. - 조건 검사: 현재 피로도가 던전의 최소 필요 피로도 이상일 경우 던전을 탐험합니다.
장단점
- 장점: 재귀적으로 모든 가능한 탐험 경로를 탐색하여 최적의 해를 구할 수 있습니다.
- 단점: 탐색 범위가 클 경우 성능 저하가 발생할 수 있습니다.
itertools를 사용한 솔루션
from itertools import permutations
def solution(k, dungeons):
max_count = 0
for dungeon_order in permutations(dungeons):
curr_stamina = k
count = 0
for req, cost in dungeon_order:
if curr_stamina >= req:
curr_stamina -= cost
count += 1
else:
break
max_count = max(max_count, count)
return max_count코드 해석
- itertools.permutations: 던전의 모든 순열을 생성하여 각 순열에 대해 탐험 경로를 평가합니다.
- 조건 검사: 현재 피로도가 던전의 최소 필요 피로도 이상일 경우 던전을 탐험하고, 그렇지 않으면 탐험을 종료합니다.
장단점
- 장점: 간결하고 이해하기 쉬운 코드로 모든 탐험 경로를 고려합니다.
- 단점: 던전 수가 많을 경우 계산 비용이 증가할 수 있습니다.
피로도 문제는 주어진 던전을 탐험하면서 가능한 최대 던전 수를 찾는 문제입니다. 이 문제는 재귀와 itertools를 사용하여 해결할 수 있었습니다. 재귀를 사용한 방법은 모든 가능한 탐험 경로를 탐색하여 최적의 해를 구할 수 있었고, itertools를 사용한 방법은 간결하고 이해하기 쉬운 코드로 모든 탐험 경로를 고려할 수 있었습니다.
5. 완전 탐색의 또 다른 예시: 자물쇠와 열쇠
자물쇠와 열쇠 문제는 주어진 열쇠를 회전 및 이동하여 자물쇠를 풀 수 있는지 여부를 판단하는 문제입니다.
코드
def solution(key, lock):
m = len(key)
n = len(lock)
keys = [[[0 for _ in range(m+2*n)] for _ in range(m+2*n)] for _ in range(4)]
for i in range(m):
for j in range(m):
keys[0][n+i][n+j] = key[i][j]
keys[1][n+j][m+n-1-i] = key[i][j]
keys[2][m+n-1-i][m+n-1-j] = key[i][j]
keys[3][m+n-1-j][n+i] = key[i][j]
for k in keys:
for i in range(m+n):
for j in range(m+n):
flag = True
for ii in range(n):
for jj in range(n):
if not lock[ii][jj] ^ k[i+ii][j+jj]:
flag = False
if flag:
return True
return False코드 해석
- 열쇠 회전 및 확장: 4가지 회전 방향으로 열쇠를 회전시키고, 자물쇠를 포함할 수 있도록 열쇠 배열을 확장합니다.
- 탐색 및 검사: 모든 가능한 위치에서 열쇠를 자물쇠와 맞추어 봅니다. 일치하는 위치가 있으면
True를 반환합니다.
장단점
- 장점: 모든 회전과 이동을 고려하여 정확한 해를 구할 수 있습니다.
- 단점: 시간 복잡도가 높아 큰 입력에서는 성능 저하가 발생할 수 있습니다.
자물쇠와 열쇠 문제는 주어진 열쇠를 회전 및 이동하여 자물쇠를 풀 수 있는지 여부를 판단하는 문제입니다. 이 문제는 모든 회전과 이동을 고려하여 정확한 해를 구할 수 있었지만, 시간 복잡도가 높아 큰 입력에서는 성능 저하가 발생할 수 있었습니다.
6. 올바른 괄호 문제
올바른 괄호 문제는 주어진 문자열이 올바른 괄호로 구성되어 있는지 확인하는 문제입니다.
코드
def solution(s):
stack = []
for p in s:
if p == '(':
stack.append(p)
else:
if not stack:
return False
stack.pop()
return not stack코드 해석
- 스택 사용: 여는 괄호
(를 스택에 추가하고, 닫는 괄호)를 만나면 스택에서 제거합니다. - 조건 검사: 스택이 비어 있지 않거나 닫는 괄호가 더 많이 나오는 경우
False를 반환합니다.
장단점
- 장점: 간결하고 효율적인 스택 사용으로 괄호의 짝을 검사할 수 있습니다.
- 단점: 코드가 단순해 추가적인 기능이 필요할 경우 확장하기 어렵습니다.
올바른 괄호 문제는 주어진 문자열이 올바른 괄호로 구성되어 있는지 확인하는 문제입니다. 스택을 사용하여 괄호의 짝을 검사하는 방법을 배웠고, 간결하고 효율적인 방법으로 문제를 해결할 수 있었습니다.
7. 그래프 - BFS 구현하기
너비 우선 탐색(BFS)은 그래프 탐색 알고리즘 중 하나로, 주어진 그래프에서 시작 노드부터 모든 인접 노드를 탐색합니다.
코드
from collections import deque
def bfs(graph, start_v):
q = deque()
visited = {}
q.append(start_v)
visited[start_v] = True
while q:
cur_v = q.popleft()
print(cur_v, end=' ')
for next_v in graph[cur_v]:
if next_v not in visited:
q.append(next_v)
visited[next_v] = True
graph = {
0: [1, 3, 6],
1: [0, 3],
2: [3],
3: [0, 1, 2, 7],
4: [5],
5: [4, 6, 7],
6: [0, 5],
7: [3, 5],
}
bfs(graph, start_v=0)코드 해석
- 큐 사용:
deque를 사용하여 현재 노드를 탐색하고, 인접 노드를 큐에 추가합니다. - 방문 표시:
visited딕셔너리를 사용하여 방문한 노드를 기록합니다.
장단점
- 장점: 간결하고 직관적인 코드로 그래프의 모든 노드를 효율적으로 탐색할 수 있습니다.
- 단점: 그래프가 크거나 밀도가 높은 경우 메모리 사용이 증가할 수 있습니다.
8. 그래프 - DFS 구현하기
깊이 우선 탐색(DFS)은 그래프 탐색 알고리즘 중 하나로, 주어진 그래프에서 시작 노드부터 깊이 우선으로 모든 노드를 탐색합니다.
코드
def dfs(cur_v):
visited[cur_v] = True
print(cur_v, end=',')
for next_v in graph[cur_v]:
if next_v not in visited:
dfs(next_v)
graph = {
0: [1, 3, 6],
1: [0, 3],
2: [3],
3: [0, 1, 2, 7],
4: [5],
5: [4, 6, 7],
6: [0, 5],
7: [3, 5],
}
visited = {}
dfs(0)코드 해석
- 재귀 사용: 현재 노드를 방문하고, 인접 노드를 재귀적으로 탐색합니다.
- 방문 표시:
visited딕셔너리를 사용하여 방문한 노드를 기록합니다.
장단점
- 장점: 간결하고 재귀적으로 문제를 해결할 수 있습니다.
- 단점: 재귀 깊이가 깊어질 경우 스택 오버플로우 위험이 있습니다.
그래프 탐색 문제는 BFS와 DFS를 사용하여 그래프를 탐색하는 문제였습니다. BFS는 모든 경로를 동일한 깊이로 탐색하여 최단 경로를 찾기 용이했으며, DFS는 재귀를 사용하여 간결하게 구현할 수 있었습니다. 각각의 장단점을 이해하고, 상황에 맞게 활용하는 방법을 배웠습니다.
Keys and Rooms 문제와 암시적 그래프를 이용한 DFS 문제를 다룰 예정입니다. 각 문제에 대한 코드 구현과 해석을 통해 여러분의 이해를 도울 수 있기를 바랍니다.
9. Keys and Rooms 문제
Keys and Rooms 문제는 주어진 방들에서 시작하여 모든 방을 방문할 수 있는지를 확인하는 문제입니다. 이 문제를 BFS와 DFS를 사용하여 해결할 수 있습니다.
BFS를 사용한 솔루션
from collections import deque
class Solution:
def canVisitAllRooms(self, rooms):
n = len(rooms)
visited = [False] * n
def bfs(graph, start_v):
q = deque([start_v])
visited[start_v] = True
while q:
cur_v = q.popleft()
for next_v in graph[cur_v]:
if not visited[next_v]:
q.append(next_v)
visited[next_v] = True
bfs(rooms, start_v=0)
return all(visited)코드 해석
- 큐 사용:
deque를 사용하여 현재 방을 탐색하고, 열쇠를 통해 접근 가능한 방을 큐에 추가합니다. - 방문 표시:
visited리스트를 사용하여 방문한 방을 기록합니다. - 탐색 완료 검사: 모든 방을 방문했는지 확인하기 위해
all(visited)를 반환합니다.
DFS를 사용한 솔루션
class Solution:
def canVisitAllRooms(self, rooms):
n = len(rooms)
visited = [False] * n
def dfs(cur_v):
visited[cur_v] = True
for next_v in rooms[cur_v]:
if not visited[next_v]:
dfs(next_v)
dfs(cur_v=0)
return all(visited)
s = Solution()
print(s.canVisitAllRooms(rooms=[[1,3], [2,4], [0], [4], [], [3,4]])) 코드 해석
- 재귀 사용: 현재 방을 방문하고, 열쇠를 통해 접근 가능한 방을 재귀적으로 탐색합니다.
- 방문 표시:
visited리스트를 사용하여 방문한 방을 기록합니다. - 탐색 완료 검사: 모든 방을 방문했는지 확인하기 위해
all(visited)를 반환합니다.
장단점 비교
- BFS 장점: 모든 경로를 동일한 깊이로 탐색하기 때문에 최단 경로를 찾기 용이합니다.
- DFS 장점: 재귀를 사용하여 간결하게 구현할 수 있으며, 특정 경로의 깊은 탐색이 필요할 때 유용합니다.
- BFS 단점: 큐 사용으로 인한 메모리 사용량이 증가할 수 있습니다.
- DFS 단점: 재귀 깊이가 깊어질 경우 스택 오버플로우 위험이 있습니다.
Keys and Rooms 문제는 주어진 방들에서 시작하여 모든 방을 방문할 수 있는지를 확인하는 문제였습니다. BFS와 DFS를 사용하여 문제를 해결하는 방법을 배웠고, 각각의 장점을 활용하여 문제를 효과적으로 해결할 수 있었습니다.
10. 암시적 그래프 DFS
암시적 그래프 문제는 주어진 2차원 배열에서 특정 조건을 만족하는 모든 노드를 방문하는 문제입니다. 이 문제는 DFS를 사용하여 해결할 수 있습니다.
코드
def dfs(r, c):
visited[r][c] = True
print((r, c), end=' ')
for i in range(4):
next_r = r + dr[i]
next_c = c + dc[i]
if 0 <= next_r < row_len and 0 <= next_c < col_len:
if grid[next_r][next_c] == 1:
if not visited[next_r][next_c]:
dfs(next_r, next_c)
grid = [
[1, 1, 1, 1],
[0, 1, 0, 1],
[0, 1, 0, 1],
[1, 0, 1, 1],
]
row_len, col_len = len(grid), len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
dfs(0, 0)코드 해석
- 재귀 사용: 현재 노드를 방문하고, 상하좌우 인접한 노드를 재귀적으로 탐색합니다.
- 방문 표시:
visited배열을 사용하여 방문한 노드를 기록합니다. - 인접 노드 탐색:
dr과dc배열을 사용하여 상하좌우 방향으로 이동합니다.
장단점
- 장점: 간결하고 재귀적으로 문제를 해결할 수 있습니다.
- 단점: 재귀 깊이가 깊어질 경우 스택 오버플로우 위험이 있습니다.
암시적 그래프 BFS 문제와 섬의 개수를 구하는 문제를 BFS와 DFS를 사용하여 해결하는 방법을 다루겠습니다. 각 문제에 대한 코드 구현과 해석을 통해 여러분의 이해를 도울 수 있기를 바랍니다.
11. 암시적 그래프 BFS
암시적 그래프 문제는 주어진 2차원 배열에서 특정 조건을 만족하는 모든 노드를 방문하는 문제입니다. 이 문제를 BFS를 사용하여 해결할 수 있습니다.
코드
from collections import deque
def bfs(r, c):
q = deque()
q.append((r, c))
visited[r][c] = True
while q:
cur_r, cur_c = q.popleft()
print((cur_r, cur_c), end='->')
for i in range(8):
next_r = cur_r + dr[i]
next_c = cur_c + dc[i]
if 0 <= next_r < row_len and 0 <= next_c < col_len:
if grid[next_r][next_c] == 1:
if not visited[next_r][next_c]:
q.append((next_r, next_c))
visited[next_r][next_c] = True
grid = [
[1, 1, 1, 1],
[0, 1, 0, 1],
[0, 1, 0, 1],
[1, 0, 1, 1],
]
row_len, col_len = len(grid), len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]
dr = [0, 1, 0, -1, 1, 1, -1, -1]
dc = [1, 0, -1, 0, 1, -1, 1, -1]
bfs(0, 0)코드 해석
- 큐 사용:
deque를 사용하여 현재 노드를 탐색하고, 상하좌우 및 대각선으로 인접한 노드를 큐에 추가합니다. - 방문 표시:
visited배열을 사용하여 방문한 노드를 기록합니다. - 인접 노드 탐색:
dr과dc배열을 사용하여 상하좌우 및 대각선 방향으로 이동합니다.
장단점
- 장점: 간결하고 효율적으로 문제를 해결할 수 있습니다.
- 단점: 큐 사용으로 인한 메모리 사용량이 증가할 수 있습니다.
암시적 그래프 문제는 주어진 2차원 배열에서 특정 조건을 만족하는 모든 노드를 방문하는 문제였습니다. BFS와 DFS를 사용하여 문제를 해결하는 방법을 배웠고, 각 방법의 장단점을 이해할 수 있었습니다.
12. Number of Islands 문제
Number of Islands 문제는 주어진 2차원 배열에서 섬의 개수를 구하는 문제입니다. 이 문제를 BFS와 DFS를 사용하여 해결할 수 있습니다.
BFS를 사용한 솔루션
from collections import deque
class Solution:
def numIslands(self, grid):
row_len, col_len = len(grid), len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]
cnt = 0
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
def bfs(r, c):
q = deque()
q.append((r, c))
visited[r][c] = True
while q:
cur_r, cur_c = q.popleft()
for i in range(4):
next_r = cur_r + dr[i]
next_c = cur_c + dc[i]
if 0 <= next_r < row_len and 0 <= next_c < col_len:
if grid[next_r][next_c] == '1' and not visited[next_r][next_c]:
q.append((next_r, next_c))
visited[next_r][next_c] = True
for i in range(row_len):
for j in range(col_len):
if grid[i][j] == "1" and not visited[i][j]:
bfs(i, j)
cnt += 1
return cnt
grid = [
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "1", "0"],
["0", "0", "0", "1", "1"],
]
s = Solution()
print(s.numIslands(grid))코드 해석
- 큐 사용:
deque를 사용하여 현재 노드를 탐색하고, 상하좌우 인접한 노드를 큐에 추가합니다. - 방문 표시:
visited배열을 사용하여 방문한 노드를 기록합니다. - 섬 개수 증가: 새로운 섬을 발견할 때마다 섬의 개수를 증가시킵니다.
DFS를 사용한 솔루션
class Solution:
def numIslands(self, grid):
row_len, col_len = len(grid), len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]
cnt = 0
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
def dfs(cur_r, cur_c):
visited[cur_r][cur_c] = True
for i in range(4):
next_r = cur_r + dr[i]
next_c = cur_c + dc[i]
if 0 <= next_r < row_len and 0 <= next_c < col_len:
if grid[next_r][next_c] == '1' and not visited[next_r][next_c]:
dfs(next_r, next_c)
for i in range(row_len):
for j in range(col_len):
if grid[i][j] == "1" and not visited[i][j]:
dfs(i, j)
cnt += 1
return cnt
grid = [
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "1", "0"],
["0", "0", "0", "1", "1"],
]
s = Solution()
print(s.numIslands(grid))코드 해석
- 재귀 사용: 현재 노드를 방문하고, 상하좌우 인접한 노드를 재귀적으로 탐색합니다.
- 방문 표시:
visited배열을 사용하여 방문한 노드를 기록합니다. - 섬 개수 증가: 새로운 섬을 발견할 때마다 섬의 개수를 증가시킵니다.
장단점 비교
- BFS 장점: 모든 경로를 동일한 깊이로 탐색하기 때문에 최단 경로를 찾기 용이합니다.
- DFS 장점: 재귀를 사용하여 간결하게 구현할 수 있으며, 특정 경로의 깊은 탐색이 필요할 때 유용합니다.
- BFS 단점: 큐 사용으로 인한 메모리 사용량이 증가할 수 있습니다.
- DFS 단점: 재귀 깊이가 깊어질 경우 스택 오버플로우 위험이 있습니다.
Number of Islands 문제는 주어진 2차원 배열에서 섬의 개수를 구하는 문제였습니다. BFS와 DFS를 사용하여 문제를 해결하였고, 각각의 방법을 통해 문제를 효과적으로 해결할 수 있었습니다.
Shortest Path in Binary Matrix문제와 다익스트라 알고리즘을 사용한 최단 경로 문제를 다루겠습니다. 각 문제에 대한 코드 구현과 해석을 통해 여러분의 이해를 도울 수 있기를 바랍니다.
13. Shortest Path in Binary Matrix
Shortest Path in Binary Matrix 문제는 주어진 2차원 이진 행렬에서 좌상단에서 우하단으로 가는 최단 경로를 찾는 문제입니다. 이 문제는 BFS를 사용하여 해결할 수 있습니다.
코드
from collections import deque
class Solution:
def shortestPathBinaryMatrix(self, grid):
if grid[0][0] == 1:
return -1
row_len, col_len = len(grid), len(grid[0])
q = deque([(0, 0, 1)])
visited = [[False] * col_len for _ in range(row_len)]
visited[0][0] = True
dr = [1, 1, 1, 0, 0, -1, -1, -1]
dc = [0, -1, 1, 1, -1, 1, -1, 0]
while q:
cur_r, cur_c, cur_d = q.popleft()
if cur_r == row_len - 1 and cur_c == col_len - 1:
return cur_d
for i in range(8):
next_r, next_c = cur_r + dr[i], cur_c + dc[i]
if 0 <= next_r < row_len and 0 <= next_c < col_len:
if grid[next_r][next_c] == 0 and not visited[next_r][next_c]:
q.append((next_r, next_c, cur_d + 1))
visited[next_r][next_c] = True
return -1코드 해석
- BFS 초기 설정: 큐를 사용하여 시작 지점에서부터 탐색을 시작합니다.
- 방문 배열:
visited배열을 사용하여 이미 방문한 노드를 기록합니다. - 방향 배열:
dr과dc배열을 사용하여 8방향으로 이동합니다. - 목적지 도달 검사: 현재 위치가 우하단인 경우 현재 거리(
cur_d)를 반환합니다. - 다음 노드 탐색: 인접한 노드 중 방문하지 않은 노드를 큐에 추가하고 방문 처리합니다.
장단점
- 장점: BFS를 사용하여 최단 경로를 효율적으로 찾을 수 있습니다.
- 단점: 큐와 방문 배열로 인한 메모리 사용량이 증가할 수 있습니다.
Shortest Path in Binary Matrix 문제는 주어진 2차원 이진 행렬에서 좌상단에서 우하단으로 가는 최단 경로를 찾는 문제였습니다. BFS를 사용하여 최단 경로를 효율적으로 찾는 방법을 배웠습니다.
14. 다익스트라 알고리즘
다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘입니다. 이 문제를 해결하기 위해 우선순위 큐를 사용합니다.
코드
import heapq
def dijkstra(graph, start_v, dest, n):
INF = float('inf')
distances = [INF] * (n + 1)
distances[start_v] = 0
pq = [(0, start_v)]
while pq:
cur_dist, cur_v = heapq.heappop(pq)
if distances[cur_v] < cur_dist:
continue
for next_v, cost in graph[cur_v]:
next_dist = distances[cur_v] + cost
if next_dist < distances[next_v]:
distances[next_v] = next_dist
heapq.heappush(pq, (next_dist, next_v))
return distances[dest]
graph = {
1: [(2, 2), (3, 5), (4, 1)],
2: [(1, 2), (3, 3), (4, 2)],
3: [(1, 5), (2, 3), (4, 3), (5, 1)],
4: [(1, 1), (2, 2), (3, 3), (5, 1)],
5: [(3, 1), (4, 1)]
}
print(dijkstra(graph, 1, 5, len(graph)))코드 해석
- 초기 설정: 시작 노드의 거리를 0으로 설정하고, 나머지 노드의 거리를 무한대로 설정합니다.
- 우선순위 큐:
heapq를 사용하여 최소 거리를 가진 노드를 우선적으로 처리합니다. - 거리 갱신: 현재 노드에서 인접한 노드로의 거리를 계산하여 최단 거리를 갱신합니다.
- 목적지 거리 반환: 목적지 노드의 최단 거리를 반환합니다.
장단점
- 장점: 가중치가 있는 그래프에서 최단 경로를 효율적으로 찾을 수 있습니다.
- 단점: 우선순위 큐를 사용하므로 추가적인 메모리 사용이 필요합니다.
다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘입니다. 우선순위 큐를 사용하여 효율적으로 최단 경로를 찾는 방법을 배웠고, 이를 통해 다양한 그래프 문제를 해결할 수 있었습니다.
강의 후기
이번 강의를 통해 다양한 자료구조와 알고리즘을 배우고, 이를 기반으로 한 문제들을 해결하는 방법을 익힐 수 있었습니다. 각 문제를 해결하는 과정에서 다양한 접근 방법을 시도해보고, 각 방법의 장단점을 이해하는 것이 큰 도움이 되었습니다. 특히, BFS와 DFS를 사용한 그래프 탐색, 재귀와 반복문을 사용한 문제 해결, 그리고 다익스트라 알고리즘을 통해 최단 경로를 찾는 방법 등은 실제 코딩 테스트에서 매우 유용하게 쓰일 수 있는 기술들입니다.
강의를 통해 배운 내용들을 바탕으로 다양한 문제를 풀어보면서 실력을 향상시킬 수 있었고, 이를 통해 자신감을 얻을 수 있었습니다. 앞으로도 꾸준히 연습하고, 다양한 문제를 풀어보면서 알고리즘 실력을 더욱 향상시켜 나가고자 합니다.
