- Search : 많은양의 데이터 중 원하는 데이터 찾는 과정
- 반드시 숙지해야하는 유형
Stack
- First In Last Out
Queue
- First In First Out
Example
from collections import deque
q = deque()
x = 5
q.append(x) # push_back
q.popleft() # pop_left
q.reverse() # 역순 바꾸기- python에서 deque을 이용한 queue 구현이 더 빠르게 동작
재귀 함수 (Recursive Function)
- 자기 자신을 다시 호출하는 함수
- 최대 재귀 깊이 초과 시 Error Message 발생
- stack 방식으로 fucntion이 할당되어 처리됨
- while, for 없이도 반복이 가능
- 종료 조건
- 반드시 재귀 함수의 종료 조건을 명시해야된다.
- 종료 조건을 제대로 명시하지 않을 시 무한히 호출될 수 있다.
Example - Factorial
def factorial_recursive(n):
if n <= 1:
return
return n * factorial_recursive(n - 1)- 연산이 수학적으로 정의된 경우 코드가 더 간결해진다.
Example - 유클리드 호제법
- 두 개 자연수에 대한 최대 공약수를 구하는 대표적 알고리즘
- 두 자연수 A, B에 대해(A>B) A를 B로 나눈 나머지를 R이라고하면 A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다.
- GCD(192 , 162)
- 162 , 30 의 최대 공약수를 구하는 문제로 변경
- 30, 12 의 최대 공약수를 구하는 문제로 변경
- 12, 6 의 최대 공약수를 구하는 문제로 변경
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)- 재귀 함수 잘 활용 시 복잡한 알고리즘을 간결하게 작성 가능
- 컴퓨터 함수를 연속적으로 호출 시 메모리 내부 스택 프레임에 쌓이므로 스택을 사용해야할 때 재귀함수를 이용하는 경우가 많다.
- 반복문보다 불리한 경우도 있다.
DFS (Depth-First Search)
- 깊이 우선 탐색
- Stack 자료 구조 또는 재귀함수를 이용한다.
- 탐색 시작 노드를 스택에 삽입 후 방문 처리
- 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리, 방문하지 않은 인접 노드가 없으면 최상단 노드를 꺼낸다.
- 2 번째 과정을 수행할 수 없을 때 까지 반복
# 각 index노드와 연결된 index노드를 저장해준다.
graph = [
[],
[2, 3, 8],
...
]
# 방문 정보 표현 list
visited = [False] * 9
def dfs(graph, v, visited):
visited[v] = True # 현재 노드 방문 처리
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)BFS (Breadth-First Search)
- 너비 우선 탐색
- 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 큐 자료 구조 이용
- 탐색 시작 노드를 큐에 삽입 후 방문 처리
- 큐에서 시작 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 2 번째 과정 수행할 수 없을 때까지 반복
- 각 간선의 비용이 동일한 상황에서 최단거리를 구할 때, 유용한 알고리즘
graph = [
[],
[2, 3, 8]
...
]
visited = [False] * 9
from collections import deque
def bfs(graph, start, visited):
q = deque([start])
visited[start] = True
whlie q:
v = q.popleft()
for i in graph[v]:
if not visited[i]:
q.append(i)
vsitied[i] = True음료수 얼려먹기
dfs
n, m = map(int, inpiut().split())
graph = []
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
result = 0
for i in range(n):
for j in range(m):
if dfs(i, j) == True:
result += 1미로 탈출
bfs
- bfs는 간선의 비용이 모두 같을 때, 최단거리를 탐색하기 위해 사용하기 유용하다.
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
q = deque()
q.append((x, y))
while q:
x, y = q.popleft()
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:
graph[nx][ny] = graph[x][y] + 1
q.append((nx, ny))
return graph[n-1][m-1]
print(dfs(0, 0))
OnePunchLotto