스택(Stack) 자료구조
큐(Queue) 자료구조
재귀 함수
재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수
단순한 재귀 함수 예제
def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_function()
recursive_function()
def recursive_function(i):
#100번째 호출을 했을 때 종료되도록 종료 조건 명시
if i == 100:
return
print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출합니다.')
recursive_function(i+1)
print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)
팩토리얼 구현 예제
def factorial_iterative(n):
result = 1
# 1부터 n까지의 수를 차례대로 곱하기
for i in range(1, n+1):
result *= i
return result
#재귀적으로 구현한 n!
def factorial_recursive(n):
if <= 1: #n이 1이하인 경우 1을 반환
return 1
#n! = n * (n-1)!를 그대로 코드로 작성하기
return n * factorial_recursive(n-1)
최대공약수 계산(유클리드 호제법) 예제
def gcd(a,b):
if a % b == 0:
return b
else
return gcd(b, a%b)
print(gcd(192, 162))
재귀 함수 사용의 유의사항
DFS(Depth-First Search, 깊이 우선 탐색)
# 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)
# 각 노드가 연결된 정보 표현
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현
visited = [False] * 9
# 정의된 dfs 함수 호출
dfs(graph, 1, visited)
BFS(Breadth-First Search, 너비 우선 탐색)
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]
]
#각 노드가 방문된 정보를 리스트 자료형으로 표현
visited = [False] * 9
bfs(graph, q, visited)
문제 1
# 입력 받음
N, M = map(int, input().split())
graph = [list(map(int, input())) for _ in range(N)]
count = 0
# DFS로 특정 노드를 방문하고 연결된 노드들 방문
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
for i in range(N):
for j in range(M):
if dfs(i, j) == True:
count += 1
print(count)
문제 2
예시 답안)
어렵다...
참고 : https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3