728x90
[주의] 개인 공부를 위해 쓴 글이기 때문에 주관적인 내용은 물론, 쓰여진 정보가 틀린 것일 수도 있습니다!
피드백 부탁드립니다. (- -)(_ _) 꾸벅
1. Stack & Queue 자료구조
Stack: FILO (First In Last Out)
Queue: FIFO (First In First Out)
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.popleft()
queue.append(3)
queue.popleft()
print(queue) # deque([3])
###
stack = deque()
stack.append(1)
stack.append(2)
stack.pop()
print(stack) # deque([1])리스트 자료형 이용할 수 있지만 시간복잡도가 더 효율적인 deque 이용
2. Recursive Function (재귀함수)
자기 자신을 다시 호출하는 함수.
실제로 컴퓨터 메모리 스택 상에 이러한 함수가 반복적으로 담겨서 처리함. → 스택 객체로도 표현 가능
반드시 재귀함수 종료 조건을 명시해야 함
def recursive_function(i):
if i == 100:
return
print(i, "번째 함수에서 ", i+1, "번째 재귀함수를 호출합니다.")
recursive_function(i+1)
print(i, "번째 재귀함수를 종료합니다.")
recursive_function(0)
1) 팩토리얼 함수
- 팩토리얼(!) 구현을 재귀함수를 통해 구현
def factorial(i):
if i == 1:
return 1
return i * factorial(i-1)
print(factorial(5)) # 120
2) 최대공약수 계산 (유클리드 호제법)
- 두 자연수 A, B에 대해 (A > B) A를 B로 나눈 나머지를 R
- 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같음
| 단계 | A | B |
| 1 | 192 | 162 |
| 2 | 162 | 30 |
| 3 | 30 | 12 |
| 4 | 12 | 6 |
def greatest_common_multiple(A, B):
if A % B == 0:
return B
return greatest_common_multiple(B, A % B)
print(greatest_common_multiple(192, 162))3. DFS (Depth-First Search) & BFS (Breadth-First Search)
- 대표적인 그래프 탐색 알고리즘
DFS: 깊이 우선 탐색이라고 부르며, 깊은 부분을 우선적으로 탐색하는 알고리즘
BFS: 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
| DFS(깊이우선탐색) | BFS(너비우선탐색) |
| 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 | 현재 정점에 연결된 가까운 점들부터 탐색 |
| 스택 또는 재귀함수로 구현 | 큐를 이용해서 구현 |
다음은 아래에 그래프 자료구조를 DFS & BFS로 구현하는 방식이다
1) DFS
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
def bfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i] :
bfs(graph, i, visited)
bfs(graph, 1, visited)탐색 순서: 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5
재귀함수는 앞서 설명과 같이 컴퓨터 메모리에 스택 상에 저장하여 동작하는 방식이므로 DFS에서 사용하는 스택 자료구조를 재귀함수로도 표현이 가능하다. (재귀함수가 더 간결하게 코드를 짤 수 있다,) 스택은 아래를 참조
더보기
- Stack을 이용하여 DFS 구현
visited = [False] * 9
def dfs_stack(graph, v, visited):
stack = deque([v])
#visited[v] = True
while stack:
print(list(stack))
e = stack.pop()
if not visited[e]:
print(e, end=' ')
visited[e] = True
stack.extend(graph[e][::-1])
# 원래 일일이 append 하는걸 extend로 뒤집어서 붙인다는 마인드
dfs_stack(graph, 1, visited)탐색 순서: 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5
2) BFS
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에는 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
from collections import deque
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
def bfs(graph, v, visited):
Queue = deque([v])
visited[v] = True
while Queue:
e = Queue.popleft()
print(e, end=' ')
for i in graph[e]:
if not visited[i]:
Queue.append(i)
visited[i] = True
bfs(graph, 1, visited)탐색 순서: 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6
3) 예제문제
1) 음료수 얼려먹기 문제
n, m = map(int, input().split(' '))
pan = list()
for _ in range(n):
pan.append(list(map(int, input())))
def dfs(x, y):
global pan
find = False
if x<0 or x>=n or y<0 or y>=m: pass
elif pan[x][y] == 0:
find = True
pan[x][y] = 1
dfs(x+1, y)
dfs(x, y+1)
dfs(x-1, y)
dfs(x, y-1)
return find
cnt=0
for dx in range(n):
for dy in range(m):
if dfs(dx,dy) : cnt += 1
print(cnt)
2) 미로탈출 문제
from collections import deque
n, m = map(int, input().split(' '))
pan = list()
for _ in range(n):
pan.append(list(map(int, input())))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
def print_pan():
for i in range(n):
for j in range(m):
print(pan[i][j], " ", end='')
print()
print("---")
def bfs(x, y):
queue = deque()
queue.append((x,y))
while queue:
x, y = queue.popleft()
print_pan()
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
elif pan[nx][ny] == 0: continue
elif pan[nx][ny] == 1 and not (nx==0 and ny==0):
pan[nx][ny] = pan[x][y] + 1
queue.append((nx,ny))
print(pan[n-1][m-1])
bfs(0,0)
728x90
'프로그래밍 언어 > 자료구조 & 알고리즘' 카테고리의 다른 글
| [알고리즘 기초] 2. 정렬 알고리즘 (0) | 2022.12.02 |
|---|