사전 필요 지식
스택 자료구조
FILO(First In Last Out) 형태의 자료구조
stack = []
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5) # push
stack.append(2) # push
stack.append(3) # push
stack.append(7) # push
stack.pop() # pop - 7 삭제
stack.append(1) # push
stack.append(4) # push
stack.pop() # pop - 4 삭제
print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력[5, 2, 3, 1].
[1, 3, 2, 5]
큐 자료구조
FIFO = First In First Out
from collections import deque
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5) # enqueue
queue.append(2) # enqueue
queue.append(3) # enqueue
queue.append(7) # enqueue
queue.popleft() # dequeue - 5 삭제
queue.append(1) # enqueue
queue.append(4) # enqueue
queue.popleft() # dequeue - 7 삭제
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력deque([3, 7, 1, 4])
deque([4, 1, 7, 3])
재귀함수
자기 자신을 다시 호출하는 함수
def recursive_function(i):
# 5번째 호출을 했을 때 종료되도록 종료 조건 명시
if i == 5:
return
print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.')
recursive_function(i + 1)
print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)1 번째 재귀함수에서 2 번째 재귀함수를 호출합니다.
2 번째 재귀함수에서 3 번째 재귀함수를 호출합니다.
3 번째 재귀함수에서 4 번째 재귀함수를 호출합니다.
4 번째 재귀함수에서 5 번째 재귀함수를 호출합니다.
4 번째 재귀함수를 종료합니다.
3 번째 재귀함수를 종료합니다.
2 번째 재귀함수를 종료합니다.
1 번째 재귀함수를 종료합니다.
팩토리얼
- n! = n x (n-1) x ... x 2 x 1
- 0! = 1, 1! = 1
# 반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
# 1부터 n까지의 수를 차례대로 곱하기
for i in range(1, n + 1):
result *= i
return result
print('반복적으로 구현:', factorial_iterative(5))
# 재귀적으로 구현한 n!
def factorial_recursive(n):
if n <= 1: # n이 1 이하인 경우 1을 반환
return 1
# n! = n * (n - 1)!를 그대로 코드로 작성하기
return n * factorial_recursive(n - 1)
print('재귀적으로 구현:', factorial_recursive(5))반복적으로 구현: 120
재귀적으로 구현: 120
최대 공약수 계산 (유클리드 호제법)
유클리드 호제법이란 두 자연수에 대한 최대 공약수를 구하는 방법
1. 두 자연수 A, B에 대하여 A를 B로 나눈 나머지를 R이라고 한다. (A > B)
2. 이때 A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다.
GCD(192, 162)
1st 192 % 162 = 30
2nd 162 % 30 = 12
3rd 30 % 12 = 6
4th 12 % 6 = 0
따라서 6이 192와 162의 최대 공약수이다.
def gcd(a, b):
# a > b이여야 하므로
if a <= b:
c = a
a = b
b = c
# 나머지가 0이면 b가 최대 공약수이다.
if a % b == 0:
return b
# b > a % b이므로
else:
return gcd(b, a % b)
print(gcd(192, 162))6
유의 사항
모든 재귀 함수는 반복문을 이용하여 동일하게 구현할 수 있다.
재귀 함수와 반복문 중 어떤 것이 유리한지 판단 해야한다.
DFS (Depth-First Search)
DFS는 깊이 우선 탐색으로 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
DFS는 스택 자료구조(혹은 재귀 함수)를 이용한다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면
그 노드를 스택에 넣고 방문 처리한다. - 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2, 3번 과정을 수행할 수 없을 때까지 반복한다.
# 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 = [
[], # node 0
[2, 3, 8], # node 1
[1, 7], # node 2
[1, 4, 5], # node 3
[3, 5], # node 4
[3, 4], # node 5
[7], # node 6
[2, 6, 8], # node 7
[1, 7] # node 8
]
# 방문 리스트 (1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출 - 1번 노드부터 탐색 시작
dfs(graph, 1, visited)1 2 7 6 8 3 4 5
BFS (Breadth-First Search)
BFS는 너비 우선 탐색으로 그래프에서 가까운 노드부터 우선적으로 탐색한다.
BFS는 큐 자료구조를 이용한다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼낸 뒤, 해당 노드의 인접 노드 중 방문하지 않은 노드를
모두 큐에 삽입하고 방문 처리한다. - 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
from collections import deque
# BFS 함수 정의
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 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
# 인접 리스트 (2차원 리스트)
graph = [
[], # node 0
[2, 3, 8], # node 1
[1, 7], # node 2
[1, 4, 5], # node 3
[3, 5], # node 4
[3, 4], # node 5
[7], # node 6
[2, 6, 8], # node 7
[1, 7] # node 8
]
# 방문 리스트 (1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출 - 1번 노드부터 탐색 시작
bfs(graph, 1, visited)1 2 3 8 7 4 5 6
DFS와 BFS
BFS : 0 1 2 3 4 5 6
DFS : 0 1 3 4 2 5 6
활용 문제
1. 음료수 얼려 먹기
N X M 크기의 얼음 틀이 있다.
구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리는 상하좌우로 붙어 있는 경우 서로 연결되었다고 한다.
이때, 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하라.
(1 <= N, M <= 1,000)
풀이)
모든 0인 점에 대해서 상하좌우로 연결되어 있는 모든 점을 탐색 후
개수를 하나 증가시키고 이를 모든 노드를 탐색할 때까지 반복한다.
아래의 모법 답안에서는 DFS로 문제를 해결하였다.
그 이유는 DFS가 구현하기에 BFS보다 쉽기 때문이다.
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for _ in range(n):
graph.append(list(map(int, input())))
# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
def dfs(x, y):
# 주어진 범위를 벗어나는 경우에는 즉시 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
# 현재 노드를 아직 방문하지 않았다면
if graph[x][y] == 0:
# 해당 노드 방문 처리 -> 1은 갈 수 없는 공간이므로
graph[x][y] = 1
# 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
dfs(x, y - 1) # 상
dfs(x, y + 1) # 하
dfs(x - 1, y) # 좌
dfs(x + 1, y) #우
# 갈 수 있는 최대한으로 탐색 후 True 반환
return True
return False
# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
# 현재 위치에서 DFS 수행
# True가 반환되었다는 것은 최대한의 탐색이 끝났다는 의미
if dfs(i, j) == True:
result += 1
print(result) # 정답 출력3 3
001
010
101
3
상하좌우로 연결된 노드만 탐색하면 되는 문제이므로 BFS로도 구현이 가능하다.
from collections import deque
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for _ in range(n):
graph.append(list(map(int, input())))
def bfs(x, y):
# bfs를 위한 queue 생성
queue = deque()
# enqueue
queue.append((x, y))
# 큐가 빌 때까지 반복하기
while queue:
# dequeue
x, y = queue.popleft()
# 주어진 범위를 벗어나는 경우에는 생략
if x <= -1 or x >= n or y <= -1 or y >= m:
continue
# 현재 노드를 아직 방문하지 않았다면
if graph[x][y] == 0:
# 방문 처리
graph[x][y] = 1
# 상, 하, 좌, 우에 대하여 모든 노드 enqueue
queue.append((x, y - 1)) # 상
queue.append((x, y + 1)) # 하
queue.append((x - 1, y)) # 좌
queue.append((x + 1, y)) # 우
result = 0
# 모든 노드에 대하여
for i in range(n):
for j in range(m):
# 방문하지 않은 노드의 경우에만 bfs 실행 후 개수 증가
if graph[i][j] == 0:
bfs(i, j)
result += 1
print(result) # 정답 출력3 3
001
010
101
3
2. 미로 탈출
N X M 크기의 직사각형 형태의 미로에 갇혔다.
플레이어의 위치는 (1, 1)이며 미로의 출구는 (N, M)이며, 한 번에 한 칸씩 이동한다.
미로는 갈 수 없는 부분은 0으로 갈 수 있는 부분은 1로 표시되어있다.
이때 플레이어가 탈출하기 위해서 움직여야 하는 최소 칸 수를 구하라.
시작 칸과 마지막 칸은 항상 1이며,
시작 칸과 마지막 칸을 모두 포함해서 개수를 계산해야 한다.
(4 <= N, M <= 200)
(풀이)
최단 거리를 구하는 문제는 BFS를 사용하면 된다!
(1, 1)에서부터 인접한 노드에 대해서 이동 횟수를 기록해주면 된다.
from collections import deque
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for _ in range(n):
graph.append(list(map(int, input())))
# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
# BFS 소스코드 구현
def bfs(x, y):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
# enqueue
queue.append((x, y))
# 큐가 빌 때까지 반복하기
while queue:
# dequeue
x, y = queue.popleft()
# 현재 위치에서 4가지 방향으로의 위치 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 미로 찾기 공간을 벗어난 경우 무시
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# 벽인 경우 무시
if graph[nx][ny] == 0:
continue
# 해당 노드를 처음 방문하는 경우
if graph[nx][ny] == 1:
# 이전 노드의 이동거리에 1을 더해준 값을 노드 값을 지정한다.
graph[nx][ny] = graph[x][y] + 1
# enqueue
queue.append((nx, ny))
# 가장 오른쪽 아래까지의 이동거리 반환
return graph[n - 1][m - 1]
# (0, 0) 그래프로 초기화했으므로 (1, 1) 대신 (0, 0)을 대입
print(bfs(0, 0))10
실행 후의 그래프 형태는 아래와 같다.
[3, 0, 5, 0, 7, 0].
[2, 3, 4, 5, 6, 7].
[0, 0, 0, 0, 0, 8].
[14, 13, 12, 11, 10, 9].
[15, 14, 13, 12, 11, 10]
참고 자료
이코테 2021 강의 3편
이것이 코딩 테스트다 교재
