* 해당 포스팅은 아래 알고리즘 강의를 듣고 정리한 내용입니다.
https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3
이번 주차 개요
탐색: 많은 양의 데이터 중 원하는 데이터를 찾는 과정
→ 특정 조건에 맞는 데이터가 존재하는지, 존재한다면 어떤 위치에 존재하는지..
ex. DFS, BFS: ⭐ 매우 자주 등장하는 유형 ⭐
스택
먼저 들어온 데이터가 나중에 나가는 형식 (선입후출): 먼저 입력되는 데이터가 나중에 출력
→ 입구와 출구가 동일한 형태 ex. 박스 쌓기
→ 다양한 알고리즘에서 사용되기 때문에 스택의 동작 방법과 사용 방법에 대해 꼭 숙지하기!
동작) 삽입(원소) + 삭제()
stack = [] #list 자료형은 가장 오른쪽에 원소 넣는 append, 오른쪽에 원소 빼는 pop
# append와 pop 함수의 시간 복잡도 = O(1)
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append()
stack.append()
stack.pop()
print(stack[::-1]) # 최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력
큐
먼저 들어온 데이터가 먼저 나가는 형식 (선입선출)
→ 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화할 수 있음
일종의 대기열
from collections import deque #deque: 스택, 큐의 장점만 합친 것
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue) #먼저 들어온 순서대로 출력 deque([3, 7, 1, 4])
queue.reverse() # 역순으로 바꾸기
print(queue) #나중에 들어온 원소부터 출력 deque([4, 1, 7, 3])재귀 함수
자기 자신을 다시 호출하는 함수
ex. 단순한 형태의 재귀 함수 예제
- ‘재귀 함수를 호출합니다.’라는 문자열을 무한히 출력
- 어느 정도 출력하다가 최대 재귀 깊이 초과 메세지 출력
def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_function()
recursive_function()⇒ 스택과 같은 형태로 동작 (스택 자료구조 안에 함수에 대한 정보가 차례대로 담겨서 컴퓨터 메모리에 올라가는 것, 메모리는 한정적이기 때문에 재귀 깊이 제한을 걸어두는 것): 마지막에 호출한 것부터 종료
+ 제한 없이 재귀함수 호출하고 싶다면 재귀 제한 느슨하게 or 스택 자료구조를 이용하여 스택 객체 따로 만들어 이용
종료 조건
- 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야함
- 의도적으로 무한 루프 사용하는 것이 아니라면!
- 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출됨
ex. 종료 조건을 포함한 재귀 함수 예제
def recursive_function():
# 100번째 호출을 했을 때 종료되도록 종료 조건 명시
if i == 100:
return
print(i, "번째 재귀함수에서", i+1, "번째 재귀함수를 호출합니다.")
recursive_function(i+1)
print(i, "번째 재귀함수를 종료합니다.")
recursive_function(1)
ex. 팩토리얼 구현 예제
n! = 1 * 2 * 3 * (n-1) * n
수학적으로 0! & 1! = 1
# 반복적으로 구현한 n!
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 n <= 1:
return
return n * factorial_recursive(n-1)
ex. 최대공약수 계산 (유클리드 호제법)
- 두 개의 자연수에 대한 최대공약수를 구하는 알고리즘 “유클리드 호제법”
유클리드 호제법
- 두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 하자
- 이때 A와 B의 최대 공약수는 B와 R의 최대공약수와 같다.
def gcd(a, b):
if a % b = 0:
return b
else:
return gcd(b, a%b)사용 시 유의 사항
→ 점화식을 코드로 구현할 수 있음
- 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성 가능
- 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있음
- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음
- 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있음
- 특정 문제에 따라 재귀를 쓸지, 반복문을 쓸지 먼저 생각해봐야함
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임
- 스택을 사용해야 할 때 구현상 스택 라이브러리 대신 재귀 함수 이용하는 경우가 많음
ex. DFS 간결하게 사용할 때 재귀 함수 사용
DFS (Depth-First-Search) 깊이 우선 탐색
그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘
스택 자료구조 (or 재귀 함수) 이용
- 탐색 시작 노드를 스택에 삽입, 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리, 방문하지 않은 인접 노드가 없으면 스택의 최상단에서 노드 꺼냄
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
+ 인접한 노드가 여러 개면 어떤 노드부터 방문할지 기준이 있다면 기준에 따라, 없으면 기준을 만들어 풀이
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 = [
[], # 1번 인덱스부터 시작하는 경우가 많으니 0은 제외
[2, 3, 8], # 1번 노드랑 연결된 번호
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9 # 인덱스 0을 사용하지 않기 때문에 하나 값 더 크게 설정
dfs(graph, 1, visited)
BFS (Breadth-First-Search) 너비 우선 탐색
시작 노드부터 출발하여 가까운 노드부터 우선적으로 탐색하는 알고리즘
큐 자료구조 이용
- 탐색 시작 노드를 큐에 삽입하고 방문처리
- 큐에서 노드를 꺼낸 뒤, 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두(한 번에) 큐에 삽입하고 방문 처리 ↔ DFS는 인접하지 않은 노드를 다시 한 번씩 스택에 넣어 방문 수행
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
+ 코테 빈출!! 특정 조건에서의 최단 경로(간선의 비용이 동일할 때) 구할 때 사용하기도 함!!
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
# queue가 빌 때까지
while queue:
v = queue.popleft()
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
graph = [
[], # 1번 인덱스부터 시작하는 경우가 많으니 0은 제외
[2, 3, 8], # 1번 노드랑 연결된 번호
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9 # 인덱스 0을 사용하지 않기 때문에 하나 값 더 크게 설정
bfs(graph, 1, visited)
예제 1) 음료수 얼려 먹기
# N * M 크기의 얼음 틀
# 구멍 뚫린 부분 = 0, 칸막이 존재 = 1
# 구멍 뚫린 부분끼리 상, 하, 좌, 우 붙어 있는 경우 서로 연결된 것으로 간주
# 얼음 틀 모양 주어졌을 때 생성되는 총 아이스크림의 개수
# 연결 요소 찾기 = connected component 찾기
import sys
# DFS 풀이
# 1. 특정 지점의 주변 상, 하, 좌, 우를 살펴본 뒤, 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문
# 2. 방문한 지점에 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정 반복 -> 연결된 모든 지점 방문 가능
# 3. 모든 노드에 대하여 1~2번 과정 반복하며, 방문하지 않은 지점 수 카운트
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+1, y)
dfs(x, y-1)
dfs(x, y+1)
return True
return False
N, M = map(int, sys.stdin.readline().split())
graph = list()
for i in range(N):
graph.append(list(map(int, input())))
result = 0
for i in range(N):
for j in range(M):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
result += 1
print(result)
예제 2) 미로 탈출
# N * M 크기의 직사각형 형태 미로에 갇혔다.
# 동빈이의 위치는 (1, 1)이며 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동 가능
# 괴물이 있는 부분은 0으로, 없는 부분은 1로 표시
# 탈출하기 위해 움직여야 하는 최소 칸 개수 (시작과 마지막 칸 모두 포함)
import sys
from collections import deque
# BFS(간선 비용이 모두 같을 때 최단거리 구하기)는 시작 지점에서 가까운 노드부터 차례대로 그패르의 모든 노드 탐색
# 상, 하, 좌, 우로 연결된 모든 노드로의 거리가 1로 동일 = BFS 최단거리!!
# (1, 1) 지점부터 BFS 수행하여 모든 노드의 최단 거리 값 기록 시, 해결
def bfs(x, y):
queue = deque()
queue.append((x, y))
# 큐가 빌 때까지 반복
while queue:
x, y = queue.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
queue.append((nx, ny))
# 가장 오른쪽 아래까지의 최단 거리 반환
return graph[N-1][M-1]
N, M = map(int, sys.stdin.readline().split())
graph = list()
for i in range(N):
graph.append(list(map(int, input())))
dx = [-1, 1, 0, 0] # 상 하 좌 우
dy = [0, 0, -1, 1]
print(bfs(0, 0))'코딩테스트 > 스터디' 카테고리의 다른 글
| [코테 스터디] 리스트의 모든 원소에서 같은 값 빼기 (0) | 2024.03.23 |
|---|---|
| [코테 스터디] sys.stdin.readline()으로 입력 받기 (0) | 2024.03.23 |
| [코테 스터디] Week4 이진 탐색 개념 정리 (1) | 2024.03.23 |
| [코테 스터디] Week3 정렬 개념 정리 (0) | 2024.03.23 |
| [코테 스터디] Week1 그리디 & 구현 개념 정리 (3) | 2024.03.09 |
