"Do it! 알고리즘 코딩 테스트 파이썬 편 [개정판]"을 기반으로 공부한 내용을 정리한 포스팅입니다 📚
❗️탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘입니다. 주어진 데이터의 성질(정렬 or 비정렬)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요합니다. 탐색 알고리즘과 함께 탐색 영역에서 그래프를 자주 이용합니다.
1️⃣ 깊이 우선 탐색(DFS)
그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
[특징] 1) 재귀 함수로 구현 (스택 오버플로우 유의) 2) 스택 자료구조 이용 3) 응용하여 풀 수 있는 문제 : 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등
[시간 복잡도(V:노드 수, E:엣지 수] O(V + E)
[재귀 호출을 이용한 DFS 동작 과정] 1) 초기 상태 : 시작 노드 선택 - 탐색을 시작하기 전, 그래프와 인접 리스트, 방문 여부를 체크할 배열, 그리고 재귀 호출을 관리할 스택의 초기 상태 만들기 - 노드 A를 시작점으로 선택
- Graph : 노드 A, B, C, D, E와 엣지 - 인접 리스트 : 각 노드와 연결된 이웃 노드들의 목록. A의 이웃은 B와 C - Visited : 모든 노드의 방문 상태는 처음에 False. 만약에 시작 노드를 스택에 append하면 방문 리스트에 True로 체크 - Stack : 처음에는 비어 있음
2) 첫 번째 탐색 : A 방문 후 B로 이동 - 시작 노드 A를 방문하고, A의 인접 리스트에 있는 첫 번째 이웃 노드인 B로 이동. A는 방문 처리되고 스택에 추가
- Graph : A는 방문됨(초록색)으로 표시되고, 현재 위치는 B(노란색) - Visited : A의 값이 True로 변경 - Stack: A가 스택에 append - Adjacency list : A의 이웃 중 B가 선택되었음을 보여줌
3) 깊이 탐색 진행 : B 방문 후 D로 이동 - 현재 노드 B를 방문 처리하고, B의 인접 리스트에서 방문하지 않은 첫 번째 이웃 노드인 D로 더 깊이 이동. B도 스택에 추가 이미지 Visited 리스트 안에 B : True가 맞음 (Gemini 오류..)
- Graph : A와 B는 방문됨, 현재 위치는 D - Visited : A와 B의 값이 True - Stack : B가 A 위에 append - Adjacency list : B의 이웃 중 D가 선택됨
4) 백트래킹(Backtracking) : D에서 B로 복귀 - 현재 노드 D의 유일한 이웃인 B는 이미 방문함. 더 이상 갈 곳이 없으므로 D에서의 탐색을 마치고, 스택에서 D를 제거(pop)하여 이전 노드인 B로 돌아옴 이미지 Visited 리스트 안에 B,D : True가 맞음 (Gemini 오류..)
- Graph : A, B, D는 방문됨. 현재 위치는 다시 B - Visited : A, B, D가 True - Stack : D가 스택에 들어갔다가 바로 pop되어 스택 상단은 다시 B가 됨 - Adjacency list : B의 인접 리스트에서 D 다음 이웃인 E를 탐색할 준비를 함
5) 이후 과정은 B에서 E로 이동하고, E에서 다시 B로 백트래킹한 뒤, 스택에서 B를 pop하고 A로 돌아와서 A의 다음 이웃인 C를 탐색하는 식으로 진행. 이처럼 DFS는 스택(또는 재귀 호출)을 활용하여 깊이 들어갔다가 막히면 다시 돌아오는 방식으로 그래프를 탐색
# 편의를 위해 숫자를 문자로 다시 바꿔줄 리스트 (출력용)
nodes = ['A', 'B', 'C', 'D', 'E']
# 1. 그래프 정의 (인접 리스트를 2차원 리스트로 표현)
# 인덱스: 0(A), 1(B), 2(C), 3(D), 4(E)
graph = [
[1, 2], # 0번 노드(A)의 이웃: B(1), C(2)
[0, 3, 4], # 1번 노드(B)의 이웃: A(0), D(3), E(4)
[0], # 2번 노드(C)의 이웃: A(0)
[1], # 3번 노드(D)의 이웃: B(1)
[1] # 4번 노드(E)의 이웃: B(1)
]
# 2. 방문 여부를 기록할 리스트 (초기값 전부 False)
# 노드 개수(5개)만큼 생성
visited = [False] * 5
# 3. DFS 재귀 함수 정의
def dfs(node_idx):
# (1) 현재 노드(인덱스)를 방문 처리 (True로 변경)
visited[node_idx] = True
# (2) 현재 노드와 연결된 이웃 노드들을 리스트에서 가져옴
for neighbor_idx in graph[node_idx]:
# (3) 아직 방문하지 않은(False인) 이웃이라면 재귀 호출
if not visited[neighbor_idx]:
dfs(neighbor_idx)
# 실행 (0번 노드인 A부터 시작)
print("DFS 방문 순서:")
dfs(0)
# 추가적으로 자릿수가 증가할 때, 소수인지 탐색하는 문제를 풀어보자!
# 백준 2023번
# 생각할 부분--------------------------
# 1) 소수 판별 함수 구현
# 2) 재귀적으로 자릿수 증가시 탐색하는 DFS 구현
# 풀이-------------------------------
# 1) 자릿수 N이 주어짐
N = int(input())
# 2) 소수 판별 함수(√x까지만 보자) / 만약 √x까지의 수들을 나눴을 때 0이 나온다면 합성수 즉, 소수가 아니다
def is_prime(num):
# i) 0,1은 소수가 아니다
if num < 2:
return False
# ii) 2는 소수이다
if num == 2:
return True
# iii) 짝수는 소수가 아니다
if num % 2 == 0:
return False
# iv) 홀수의 약수만 검사하자
# 소수가 아니면 (합성수)x = a * b 형태로 약수가 있는데, 만약 a와 b가 둘 다 √x보다 크면 a*b > √x * √x = x 가 되어버려서 모순
# 즉, 합성수라면 약수 중 하나는 반드시 √x 이하에 있음. 그래서 d를 √x까지만 확인하면 충분
# d * d <= x 는 d <= √x 와 똑같은 의미
d = 3 # 홀수 중 가장 작은 수부터 시작
while d * d <= num:
if num % d == 0:
return False
d += 2
return True
# 3) dfs 탐색
def dfs(num):
if len(str(num)) == N:
print(num)
# 어짜피 자릿수가 증가할 때마다 붙는 수들은 홀수 / 짝수가 붙으면 소수가 안됨
else:
for i in range(1,10,2):
# 자릿수 증가시키면서 홀수 붙이기 / num = 2이라면 21/23/25/27/29들을 소수인지 판별 진행
if is_prime(num*10 + i):
# True(소수라면) 재귀적으로 돌기
dfs(num*10 + i)
# 초기값인 소수인 일의 자리 수는 2,3,5,7이므로 이 수부터 시작
dfs(2)
dfs(3)
dfs(5)
dfs(7)
2️⃣ 백트래킹
문제를 해결하는 탐색 기법. 문제를 해결할 수 있는 모든 경로를 탐색하면서 선택한 경로가 유효하지 않거나 조건에 만족하는 해를 찾지 못할 경우, 이전 단계로 되돌아가 다른 경로를 시도하는 알고리즘
[특징] - 재귀 함수로 구현 - 가지치기로 성능 향상(DFS와 개념과 구현 방식이 매우 유사하고 가장 큰 특징은 가지치기로 유효하지 않는 경로를 조기에 배제하여 탐색 범위를 줄이고 성능을 높일 수 있다는 점) - 대표적인 문제 : 조합, 순열, N-Queens etc..
[시간 복잡도] - O(N^d) : N은 분기 수, d는 탐색 깊이
[핵심 이론] 1) 가능한 선택지 탐색하기 - 현재 상태에서 가능한 선택지를 모두 탐색
2) 유효성 검사 및 가지치기 - 각 선택지가 문제의 조건을 만족하는지 검사. 만약 조건을 만족하지 않으면, 해당 경로는 더 이상 탐색하지 않고 즉시 이전 단계로 돌아감
3) 해답 도출하기 - 백트래킹으로 조건을 만족하는 해답을 찾으면 이를 기록하고, 필요에 따라 다른 경로도 계속 탐색
# 백준 15649번
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
visited = [False] * (N + 1) # visited[i] = True면 숫자 i는 이미 수열에 사용중
s = [] # 현재까지 만든 수열(경로)
# 백트래킹으로 1~N 중에서 중복 없이 M개를 뽑아 순서 있게 나열(순열)
def backtrack():
# 종료 조건: 길이가 M이 되면(= M칸을 다 채우면) 출력하고 돌아감
if len(s) == M:
print(*s) # *s는 리스트를 언패킹해서 공백으로 출력
return # 여기서 현재 backtrack() 호출이 끝나고 "호출한 곳"으로 복귀
# 현재 자리(다음 칸)에 1~N 중 어떤 숫자를 넣을지 시도
for i in range(1,N+1):
if not visited[i]:
# [1] 선택(Choose)
visited[i] = True # i를 지금 수열에 쓰기로 했으니 사용 표시
s.append(i) # 수열에 i 추가 (현재 자리 채움)
# [2] 다음 자리로 내려감(Explore / Recursive call)
# 여기서 backtrack()을 호출하면,
# "지금 backtrack() 함수는 끝나는 게 아니라"
# 이 줄에서 잠깐 멈춘 상태로(대기) 아래 단계(더 깊은 호출)로 내려감
backtrack()
# [3] 되돌리기(Un-choose / Backtrack)
# 위의 재귀 호출이 return으로 끝나서 돌아오면, 이 줄부터 이어서 실행됨
# 즉, i를 선택했던 상태를 원래대로 되돌려서
# 같은 깊이에서 다음 i(예: i=2, i=3 ...)를 시도할 수 있게 함
s.pop() # 방금 넣었던 i를 제거 (항상 마지막 원소)
visited[i] = False # i를 다시 사용할 수 있게 사용 표시 해제
# 이제 for문은 "다음 i"로 계속 진행됨
# 예: i=1을 다 탐색했으면 i=2로 넘어감
# 시작: 빈 수열에서 첫 자리부터 채우기
backtrack()
3️⃣ 너비 우선 탐색(BFS)
시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘
[특징] - FIFO 탐색 (선입선출) - Queue 자료구조 이용 (재귀 함수로 구현 ❌ / deque로 반복문 구현) - 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장
[시간 복잡도(V:노드 수, E:엣지 수] O(V + E)
[BFS 동작 과정] 1) BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 출처 : https://takeuforward.org/graph/breadth-first-search-bfs-level-order-traversal - DFS와 동일하게 그래프를 인접 리스트로 표시하고 방문 리스트 또한 준비. 그러나 탐색에 있어서는 큐 사용 - 먼저, 1번 노드를 큐에 넣고 방문 처리(True)
2) 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기 - 1번 노드를 큐에서 꺼내면서 인접 노드인 2,5 노드를 큐에 삽입하고 방문 리스트에 체크(True)
3) 큐 자료구조에 값이 없을 때까지 반복하기
- 2번 노드를 큐에서 꺼내면서 인접 노드인 3번 노드 큐에 삽입하고 방문 처리(5번 노드도 2번 노드의 인접 노드 중 하나지만 이미 방문 처리가 되어 있으므로 여기선 3번 노드만 삽입)
- 5번 노드를 큐에서 꺼내면서 인접 노드인 4번 노드 큐에 삽입하고 방문 처리(위 설명과 동일하게 3번 노드는 이미 방문 처리가 되어 있으므로 여기서도 마찬가지로 4번 노드만 삽입)
- 이젠 큐에서 3번 노드와 4번 노드를 빼기 ❗️최종 탐색 순서는 1,2,5,3,4 - 선입선출 방식으로 탐색하므로 탐색 순서가 DFS와 다름을 확인
# DFS 구현
from collections import deque
visited = [False] * (N+1)
def bfs(start):
queue = deque()
queue.append(start)
visited[start] = True
while queue:
now_node = queue.popleft()
print(now_node, end = ' ')
for i in A[now_node]:
if not visited[i]:
visited[i] = True
queue.append(i)
# 백준 2178번 미로 탐색하기
import sys
from collections import deque
input = sys.stdin.readline
N,M = map(int,input().split())
A = [[0]*M for _ in range(N)]
visited = [[False]*M for _ in range(N)]
# 데이터 삽입
for i in range(N):
numbers = list(input().strip())
for j in range(M):
A[i][j] = int(numbers[j])
# 미로를 탐색할 때는 현재 좌표를 기준으로 상,하,좌,우 순서로 인접 노드들을 큐에 삽입하며 방문 체크
# 이때 사용할 상,하,좌,우 계산 리스트
dx = [-1,1,0,0]
dy = [0,0,-1,1]
# 전형적인 미로 최단거리(가중치 1)라서 BFS(너비우선탐색)로 풀기
def bfs(i,j):
queue = deque()
# 시작 좌표 큐에 삽입
queue.append((i,j))
visited[i][j] = True
while queue:
now = queue.popleft() # (i,j) 튜플
# 상하좌우 좌표 살피기
for k in range(4):
x = now[0] + dx[k]
y = now[1] + dy[k]
# 좌표가 미로 범위 안에 있어야됨
if x >= 0 and y >= 0 and x < N and y < M:
# 해당 좌표 값이 1이거나(이동 가능) 아직 미방문이면 이동
if A[x][y] == 1 and not visited[x][y]:
visited[x][y] = True
# 이때 방문한 데이터의 값을 depth의 값으로 저장하기 위해 이전 데이터의 값+1로 업데이트
A[x][y] = A[now[0]][now[1]] + 1
queue.append((x,y))
bfs(0,0)
print(A[N-1][M-1])
4️⃣ 이진 탐색
데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다
[특징] - 중앙값 비교를 이용한 대상 축소 방식
[시간 복잡도] - O(logN)
[탐색 과정] 이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복(내림차순이라면 반대로 수행) 1) 현재 데이터셋의 중앙값을 선택 2) 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택 3) 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택 4) 과정 1)~3)을 반복하다가 중앙값 == 타깃 데이터일 때 탐색 종 출처 : https://devlog-wjdrbs96.tistory.com/106
# 백준 1920번
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
M = int(input())
target_nums = list(map(int,input().split()))
# 이진 탐색을 위한 정렬
A.sort()
for i in range(M):
target_num = target_nums[i]
find = False
# 이진 탐색 시작
start_idx = 0
end_idx = len(A)-1
while start_idx <= end_idx:
# 중앙값 찾고
mid_idx = int((start_idx + end_idx) / 2)
mid = A[mid_idx]
# 중앙값과 타깃값 계속 비교하면서 범위 줄이기
if mid < target_num:
start_idx = mid_idx + 1
elif mid > target_num:
end_idx = mid_idx - 1
else:
find = True
break
if find:
print(1)
else:
print(0)
