1️⃣ 자료구조 기초
🐾 탐색 Search
| 많은 양의 데이터 중 원하는 데이터를 찾는 과정
| 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 주로 다룬다.
| 대표적인 탐색 알고리즘 : DFS, BFS
| 탐색 알고리즘 원리를 이해하기 위해 스택, 큐, 재귀함수에 대한 이해가 필요하다.
🐾 자료구조 Data Structure
| 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다.
| 스택과 큐는 자료구조의 기초 개념으로 다음의 두 함수와 두가지 고려 사항으로 구성된다.
• 삽입 Push : 데이터를 삽입한다.
• 삭제 Pop : 데이터를 삭제한다.
• 오버플로 : 자료구조가 수용할 수 있는 데이터의 크기를 초과한 상태에서 삽입 연산을 수용할 때 발생
• 언더플로 : 자료구조에 데이터가 전혀 들어가있지 않은 상태에서 삭제 연산을 수행하는 경우 발생
🐾 스택 stack
| Last in First out 구조
• 박스쌓기에 비유할 수 있다.
• 파이썬에서 append , pop 메서드를 이용하면 스택 자료구조와 동일하게 동작한다.
• append 는 가장 뒤쪽에 데이터를 삽입하고 pop 은 가장 뒤쪽의 데이터를 꺼낸다.
# ✅ 스택
stack = [] #📌 그냥 리스트로 생성해서 append, pop 을 사용하면 됨
stack.append(5)
stack.append(3)
stack.append(1)
stack.pop()
stack.append(1)
stack.append(8)
stack.append(9)
stack.pop()
print(stack) ## 최하단 원소 (처음에 입력했던) 부터 출력
print(stack[::-1]) # 최상단 원소 (나중에 입력했던) 부터 출력
🐾 큐 queue
| First in First out 구조
• 먼저 온 사람이 먼저 들어가는 대기 줄서기에 비유할 수 있다.
• 큐를 파이썬에서 구현하기 위해 collections 에서 deque 라이브러리를 불러와 객체를 정의한다.
• FIFO 구조를 구현하기 위해서 append 와 popleft 함수를 사용한다.
from collections import deque
# 큐 구현을 위해 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) # 먼저 들어온 순서대로 출력
queue.reverse() #📌 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력
* deque 객체를 리스트 자료형으로 변경하고자 한다면 list() 메서드를 이용하면 된다. list(queue)
🐾 재귀함수 Recursive Function
| 자기 자신을 다시 호출하는 함수를 의미한다.
def recursive_function() :
print('재귀함수 호출')
recursive_function()
recursive_function() # 자기 자신을 다시 호출하는 재귀 함수 -> 이 예제에서는 무한히 출력됨
| 수학시간에 배운 '프랙털' 구조와 흡사하다. 프랙털 이미지를 출력하는 프로그램을 작성할 때에 재귀함수를 이용하기도 한다.
| 재귀함수는 반드시 종료조건을 꼭 명시해야 한다.
def recursive_function(i) :
# 100번째 출력했을 때 종료되도록 종료 조건 명시
if i == 100 : # 📌 if 문으로 종료 조건 설정
return
print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출합니다.')
recursive_function(i+1)
print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)
| 재귀함수의 수행은 스택 자료구조를 이용한다.
• 함수를 계속 호출했을 때, 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.
| 재귀 함수를 이용하는 대표적인 예제 : 팩토리얼
• 종료조건 : n 이 1 이하가 되었을 때
def factorial_recursive(n) :
if n<=1 : # 종료조건
return 1
return n*factorial_recursive(n-1)
print(factorial_recursive(5)) # 120
| 재귀함수를 사용하는 것이 더 간결한 이유
• 점화식을 그대로 소스코드로 옮겼기 때문
• 점화식 : 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것 → 다이나믹 프로그래밍으로 이어지므로 중요함!
1. n 이 0 혹은 1일때 : factorial(n) = 1 👉 if 문으로 종료조건
2. n 이 1보다 클때 : factorial(n) = n * factorial(n-1)
2️⃣ 탐색 알고리즘 DFS/BFS
🗨 그래프의 기본 구조
• 노드 Node = 정점 Vertex
• 간선 Edge
• 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다' 라고 표현한다.
🗨 그래프를 표현하는 2가지 방식
• 인접행렬 Adjacency Matrix : 2차원 배열로 그래프의 연결관계를 표현하는 방식으로 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 파이썬 2차원 리스트로 인접행렬을 구현할 수 있다. 보통 연결이 되어있지 않은 노드끼리는 Infinity 의 비용이라고 작성하는 의미에서 999999999, 987654321 등의 값으로 초기화하는 경우가 많다.
| 0 | 1 | 2 | |
| 0 | 0 | 7 | 5 |
| 1 | 7 | 0 | Inf |
| 2 | 5 | Inf | 0 |
INF = 999999999
graph = [
[0,7,5],
[7,0,INF],
[5,INF,0]
]
print(graph)
## [[0,7,5],[7,0,INF],[5,INF,0]]
• 인접 리스트 Adjacency List: 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
# 행이 3개인 2차원 리스트로 인접 리스트 표현
graph = [ [] for _ in range(3) ]
# 노드 0에 연결된 노드 정보 저장 (노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))
# 노드 1에 연결된 노드 정보 저장 (노드, 거리)
graph[1].append((0,7))
# 노드 2에 연결된 노드 정보 저장 (노드, 거리)
graph[2].append((0,5))
print(graph)
• 인접 행렬 방식은 모든 관계를 저장하므로 노드의 관계가 많을수록 메모리가 불필요하게 낭비된다.
• 인접 리스트 방식은 연결된 정보만 저장하므로 메모리를 효율적으로 사용한다. 그러나 두 노드가 연결되어있는지에 대한 정보를 얻는 속도는 느리다. 특정한 노드와 연결된 모든 인접노드를 순회해야 하는 경우 인접 리스트 방식이 행렬 방식에 비해 메모리 공간의 낭비가 적다.
🐾 DFS (Depth - First Search)
| 깊이 우선 탐색
| 스택 자료구조를 사용한다.
| 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가 노드를 방문한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘
1. 탐색 '시작 노드' 를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
* 방문처리 : 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것
* 일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다.
# ✅ 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 = [
[], # 0
[2,3,8], #1
[1,7], #2
[1,4,5], #3
[3,5], #4
[3,4], #5
[7], #6
[2,6,8], #7
[1,7] #8
]
visited = [False]*9
dfs(graph, 1, visited) # 결과적으로 노드의 탐색순서 (스택에 들어간 순서) 가 출력됨
🐾 BFS (Breadth - First Search)
| 너비 우선 탐색
| 가까운 노드부터 탐색하는 알고리즘
| DFS 는 최대한 멀리 있는 노드를 우선적으로 탐색하는 방식이라면, BFS 는 그 반대이다.
| 수행 시간이 DFS 보다 좋다.
| 큐 자료구조를 사용한다. 인접한 노드를 반복적으로 큐에 넣으면 선입선출에 의해 가까운 노드부터 탐색을 진행하게 된다.
1. 탐색 시작 노드를 큐에 삽입하고 방문처리 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
3. 더이상 수행할 수 없을 때까지 2번을 반복
| 결과적으로 노드의 탐색순서 (큐에 들어간 순서) 가 출력됨
# ✅ BFS 너비 우선 탐색
from collections import deque
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 = [
[], # 0
[2,3,8], #1
[1,7], #2
[1,4,5], #3
[3,5], #4
[3,4], #5
[7], #6
[2,6,8], #7
[1,7] #8
]
visited = [False]*9
bfs(graph, 1, visited)
| DFS | BFS | |
| 동작원리 | 스택 | 큐 |
| 구현방법 | 재귀함수이용 | 큐 자료구조 이용 |
• 2차원 배열에서 탐색 문제를 만나면 그래프 형태로 바꿔서 접근하면 방법이 좀 더 쉽다.
🗨 그래프 생성 코드 (in 행렬 기반 문제)
n,m = map(int, input().split())
# 그래프 입력받기
graph = []
for i in range(n) :
graph.append(list(map(int, input())))
'2️⃣ Study > ⚙ 알고리즘' 카테고리의 다른 글
| [자료구조] 이진탐색 (1) | 2024.04.04 |
|---|---|
| [자료구조] 정렬 (1) | 2024.02.25 |
| [자료구조] 구현 (1) | 2022.09.02 |
| [자료구조] 그리디 (0) | 2022.09.02 |
| [자료구조] 필수 파이썬 문법 - 조건문, 반복문, 함수, 입출력, 라이브러리 (0) | 2022.09.02 |
댓글