1. 꼭 필요한 자료구조 기초
- 탐색(search): 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다.
- 대표적 알고리즘 : DFS, BFS
-
자료구조(Data Structure): 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 그중 스택과 큐는 자료구조의 기초 개념이다.
-
스택 : 선입후출 구조
-
큐 : 선입선출
-
오버플로 : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할때 발생. 즉, 저장 공간을 벗어나 데이터가 넘처 흐를 때 발생
-
언더플로: 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할때 발생
-
- 큐 (queue)
collections 모듈에서 제공하는 deque 자료구조를 활용 할 수 있다.
from collections import deque
queue = deque()
queue.append(5)
queue.popleft()
queue.reverse()
list(queue)
-
재귀 함수(Recursive Function) : 자기자신을 다시 호출하는 함수
재귀함수 문제풀이 과정에서는 종료조건이 중요하다. 종료조건을 명시하지 않으면 함수가 무한 호출 될 수 있다.
#반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
for i in range(1, n+1):
result *= i
return result
print(factorial_iterative(5))#재귀적으로 구현한 n!
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n-1)
print(factorial_recursive(5))반복문 대신에 재귀함수를 사용했을 때 더욱 간결한 코드를 작성할 수 있다.
2. 탐색 알고리즘 DFS/BFS
1. DFS(Depth-First Search)
: 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 인접행렬 : 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식. 파이썬에서는 2차원 리스트로 구현할 수 있다. 연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성한다.
INF = 99999999 graph = [ [0,7,5], [7,0,INF], [5,INF,0] ] print(graph) - 인접리스트 : 모든 노트에 연결된 노드에 대한 정보를 차례대로 연결하여 저장하는 방식.
graph=[[] for _ in rnage(3)] graph[0].append((1,7)) graph[0].append((2,5)) graph[1].append((0,7)) graph[2].append((0,5))
메모리 측면에서 인접행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다. 반면에 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.
하지만 이와 같은 속성때문에 인접리스트 방식은 인접행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.
<동작방식>
1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.
2.BFS(Breadth First Search)
: 너비 우선 탐색. 가까운 노드부터 탐색하는 알고리즘
<동작방식>
1. 탐색 시작노드를 큐에 삽입하고 방문처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문을 처리한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
실제로 구현함에 있어 deque라이브러리를 사용하는 것이 좋다.
참고) 보통 DFS보다 BFS구현이 조금 더 빠르게 동작한다.
- DFS : 스택, 재귀함수
- BFS : 큐 , 큐 자료구조
dfs: 영역개수
bfs: 영역크기, 이동횟수
실전문제
1. 음료수 얼려 먹기
n, m = map(int,input().split())
graph=[]
for i in range(n):
graph.append(list(map(int,input())))
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
print(result)
2. 미로탈출
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]
from collections import deque
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 ny<0 or nx>=n or ny>=m:
continue
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx,ny))
return graph[n-1][m-1]
print(bfs(0,0))