*나동빈님의 이코테 2021강의 정리
그래프 탐색 알고리즘
- 탐색이란 데이터 중에서 원하는 데이터를 찾는 과정.
- 대표적으로 DFS/BFS. 코딩테스트에 자주 등장.
Stack
- 먼저 들어온 데이터가 나중에 나가는 선입후출방식. FILO(First In, Last Out).
- 입구와 출구가 동일한 형태. i.e. 프링글스통
- i.e. 박스 쌓기, 책 쌓기 등.
- 삽입과 삭제로 이루어짐.
- python에서 list 자료구조형으로 Stack 이용가능
- 가장 오른 쪽에 원소를 삽입 : append()
- 가장 오른 쪽에 원소를 삭제 : pop()
- 시간복잡도 : O(1), 상수시간
Stack 구현 예제 (Python)
stack = []
stack.append(4)
stack.append(1)
stack.append(2)
stack.pop()
stack.append(8)
stack.pop()
print(stack[::-1])
print(stack)
[1,4]
[4,1]
Stack 구현 예제 (Java)
Stack<Integer> s = new Stack<>();
// 삽입(4) - 삽입(1) - 삽입(2) - 삭제()- 삽입(8) - 삭제
s.push(4);
s.push(1);
s.push(2);
s.pop();
s.push(8);
s.pop();
// stack의 최상단 원소부터 출력
while(!s.empty()){
System.out.print(s.peek()+ " ");
s.pop();
1,4
Queue
- 먼저 들어온 데이터가 먼저 나가는 선입선출 형식. FIFO(First In, First Out).
- 입구와 출구가 모두 뚫려있는 터널 형태.
- Python에서 queue 구현 할때, deque 라이브러리 사용.
- list로도 구현가능하지만, 시간복잡도가 더 높기 때문에 효율성 떨어지기 때문에 deque사용.
- python에서 list로 queue구현하고 pop으로 원소를 꺼내면, 원소의 위치를 조정해야하기때문에 원소를 꺼내는 것 만으로도 시간복잡도 O(N) 요구. 그래서 deque 사용.
- deque: Stack과 queue 자료구조형의 장점을 합친 형태의 자료구조라고 볼 수 있음.
Queue 구현 예제 (Python)
from collections import deque
queue = deque()
queue.append(4)
queue.append(1)
queue.append(2)
queue.popleft()
queue.append(8)
queue.popleft()
print(queue)
queue.reverse()
pirnt(queue)
deque([2,8])
deque([8,2])
Queue 구현 예제 (Java)
Queue<Integer> q = new Queue<>();
// 삽입(4) - 삽입(1) - 삽입(2) - 삭제()- 삽입(8) - 삭제
q.offer(4);
q.offer(1);
q.offer(2);
q.poll();
q.offer(8);
q.poll();
// 먼저 들어온 원소부터 추출
while(!q.empty()){
System.out.print(q.poll()+ " ");
2,8
Recursive Function(재귀 함수)
- 자기 자신을 다시 호출하는 함수.
- DFS를 구현할 때 자주 사용.
- python에서는 어느 정도 출력 후 최대 재귀 깊이 초과 메세지가 출력.
- stack frame에 함수가 반복적으로 쌓여서 마지막 호출된 함수를 처리하고, 그 함수를 불렀던 함수까지 처리되는 방식. stack 자료구조 안에 함수의 정보가 차례대로 담겨서 컴퓨터 메모리에 올라간다고 이해할 수 있음. 메모리는 한정된 크기만큼의 자원을 가지고 있기때문에 함수가 종료되지않고 계속 쌓여서 호출만 되면 메모리가 가득 차서 문제가 생길 수있음. 그래서 재귀 깊이 제한을 걸어놓음. 제한없이 사용하려면 재귀깊이제한을 느슨하게 만들거나 별도의 stack객체를 만들어서 사용.
def recursive_function():
print('hi')
recursive_function()
recursive_function()
종료조건
- 재귀함수의 종료조건을 반드시 명시해야함. 제대로 명시하지 않으면 함수 무한히 호출.
def recursive_function(i):
if i == 100:
return
print(i,'번째 재귀함수에서',i+1, '번째 재귀함수를 호출합니다.')
recursive_function(i+1)
print(i,'번째 재귀함수를 종료합니다.')
recursive_function(1)
팩토리얼 구현예제
- n! = 123...(n-1)*n.
- 0!과 1!의 값은 1.
def factorial_iterative(n):
result = 1
for i in range(1,n+1):
result *= i
return result
def factorial_recursive(n):
if n<= 1:
return 1
return n*factorial_recursive(n-1)
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))
반복적으로 구현: 120
재귀적으로 구현: 120
최대공약수 계산(유클리드 호제법) 예제
- 두 개의 자연수에 대한 최대공약수를 구하는 대표적 알고리즘 -> 유클리드 호제법.
유클리드 호제법
- 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R.
- 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
- i.e. GCD(192,162)
| A | B | |
|---|
| 192 | 162 | 192를 162로 나누면 나머지 30 |
| 162 | 30 | 162를 30으로 나누면 나머지 12 |
| 30 | 12 | 30을 12로 나누면 나머지 6 |
| 12 | 6 | 최대공약수는 6 |
def gcd(a,b):
if a%b == 0:
return b
else
return gcd(b, a%b)
유의사항
- 코드를 간결하게 작성가능하지만, 이해하기 어려운 형태의 코드가 될 수 있음.
- 재귀함수는 반복문을 이용하여 동일한 기능 구현가능.
- 재귀함수가 반복문보다 유리한 경우가 있고 불리한 경우도 있음.
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임.
- 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우 많음. 대표적으로 dfs를 재귀함수로 구현하고함.
DFS(Depth-First Search)
- 깊이 우선 탐색. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
- Stack 자료구조(혹은 재귀함수)를 이용.
- 탐색 시작 노드를 스택에 삽입혹 방문 처리를 함. (주로 번호가 낮은 인접노드부터 시작)
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.
- 2번의 과정을 수행할 수 없을 때까지 반복.
DFS 소스코드 예제 (Python)
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 = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]]
visited = [False] * 9
dfs(graph,1,visited)
1 2 7 6 8 3 4 5
DFS 소스코드 예제 (Java)
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static void dfs(int x) {
visited[x] = true;
System.out.print(x+" ");
for (int i=0; i<graph.get(x).size(); i++){
int y = graph.get(x).get(i);
if(!visited[y]) dfs(y);
}
}
BFS (Breadth-First Search)
- 너비 우선 탐색. 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘.
- Queue 자료구조를 이용.
- 탐색 시작 노드를 큐에 삽입하고 방문처리.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 큐에 삽입하고 방문처리. (번호가 낮은 인접노드부터), 인접한 노드를 한번엔 큐에 삽입.
- 2번의 과정을 수행할 수 없을 때까지 반복.
- 특정 조건에서의 최단경로구하기에서 자주 사용.
BFS 소스코드 예제 (Python)
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visitedp[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 = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]]
visited = [False] * 9
bfs(graph,1,visited)
1 2 7 6 8 3 4 5
BFS 소스코드 예제 (Java)
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
visited[start] = true;
while(!q.isEmpty()){
int x = q.poll();
System.out.print(x+" ");
for(int i=0; i<graph.get(x).size(); i++){
int y = graph.get(x).get(i)
if(!visited[y]) {
q.offer(y);
visited[y] = true;
}
}
문제 1: 음료수 얼려먹기
- N*M 크기의 얼음틀. 구멍이 뚤려있으면 0, 칸막이 부분은 1.
- 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램 작성.
| 입력 | 출력 |
|---|
| 4 5 | |
| 00110 | |
| 00011 | 3 |
| 11111 | |
| 00000 | |
문제해결방법
DFS 활용 알고리즘
- 특정한 지점의 주변 상,하,좌,우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있으면 방문.
- 방문한 지점에서 다시 상,하,좌,우를 살펴보면서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점 방문 가능.
- 모든 노드에 대해서 1~2번 과정을 반복하며, 방문하지 않은 지점의 수를 카운트.
답안 (Python)
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
n, m = map(int,input().split())
graph = []
for i in range(n):
graph.append(list(map(int,input())))
result = 0
for i in range(n):
for j in range(m):
if dfs(i,j) == True:
result +=1
print(result)
답안 (Java)
자바소스코드
문제 2: 미로 탈출
- N*M 크기의 미로. 시작 위치는 (1,1)이며 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 하한 칸씩 이동가능. 괴물이 있는 부분은 0, 괴물이 없는 부분은 1.
- 탈출하기 위해 움직여야하는 최소 칸의 개수를 구하기. 칸을 셀 때는 시작 칸과 마지막 칸도 포함.
| 입력 | 출력 |
|---|
| 5 6 | |
| 101010 | |
| 111111 | 10 |
| 000001 | |
| 111111 | |
| 111111 | |
문제해결방법
- BFS는 시작지점에거 가까운 노드부터 차레대로 연결된 모든 노드를 탐색.
- 상,하,좌,우로 연결된 모든 노드로의 거리가 1로 동일.
- 따라서 (1,1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록.
- (1,1)의 위치에서 시작.
- (1,1) 죄표에서 상,하,좌,우로 탐색하며 값이 1인 노드를 방문하여 방문하는 노드의 값을 2로 바꾼다.(시작 칸과 마지막칸을 포함해서 칸을 세기 때문에). 매번 새로운 노드를 방문할 때 그 이전 까지의 최단 거리에 1을 더해줌.
답안 (Python)
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]
print(bfs(0,0))
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]
답안 (Java)
자바소스코드
