Date | 2021.07.13~14
Review | 자료구조 시간이나 컴퓨터개론 시간에 배웠던 내용을 스스로 정리하고 코딩테스트에 어떻게 활용하는 방법을 익힐 수 있는 시간이라 유익했다. / DFS BFS를 어떤식으로 실전 알고리즘을 작성하는데 쓰는지 실전문제 코드로 보았는데 너무 신기한데 너무 어렵다,, 여기는 수시로 보면서 익혀야 할 것 같다 꿱
1️⃣ 꼭 필요한 자료 구조 기초
#탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터만 찾는 과정 - DFS / BFS
#자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조 - Stack / Que
## 1) 스택 Stack
바닥에 상자를 아래에서 위로 차곡차곡 쌓는 것에 비유
_
별도의 라이브러리 사용하지 않고, 기본 리스트 메소드 활용한다.
append() : 리스트의 가장 뒤쪽에 데이터 삽입
pop() : 리스트의 가장 뒤쪽에 데이터 삭제
### 5-1.py ###
### 스택 예제 ###
stack = [] # 기본 리스트의 메소드 활용
# 삽입(5)-삽입(2)-삽입(3)-삽입(7)-삭제()-삽입(1)-삽입(4)-삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack) #최하단 원소부터 출력
stack.reverse()
print(stack) #최상단 원소부터 출력
## 2) 큐 Queue
놀이공원 입장하기 위해 줄을 서는 것에 비유
_
from collections import deque 라이브러리 활용해 deque()로 객체 생성한다.
append()
popleft()
### 5-2.py ###
### 큐 예제 ###
# deque 라이브러리 활용
from collections import deque
queue = deque()
# 삽입(5)-삽입(2)-삽입(3)-삽입(7)-삭제()-삽입(1)-삽입(4)-삭제()
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) #최상단 원소부터 출력
## 3) 재귀함수
자기 자신을 다시 호출하는 함수
종료조건을 꼭 명시해야 무한루프에 빠지지 않는다
-
def A():
실행내용
A()
A()
### 5-3.py ###
### 재귀함수 예제 ###
#재귀함수정의
def recursive_function():
print('재귀함수를 호출합니다')
recursive_function() #재귀호출
recursive_function()### 5-4.py ###
### 재귀함수 <종료> 예제 ###
#재귀함수정의
def recursive_function(i):
if i == 100:
return
print(i, '번째 재귀함수에서', i+1, '번째 재귀 함수를 호출합니다')
recursive_function(i+1) #재귀호출
print(i, '번째 재귀 함수를 종료합니다')
recursive_function(1)### 5-5.py ###
### 재귀함수를 활용한 팩토리얼 예제 ###
#반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
for i in range(1,n+1): # 1부터 n까지 반복
result *= i
return result
#재귀함수로 구현한 n!
def factorial_recursive(n):
if n <= 1: # n이 1이하면 1 반환
return 1
return n*factorial_recursive(n-1)
print('반복적으로 구현 : ',factorial_iterative(5))
print('재귀적으로 구현 : ',factorial_recursive(5))
2️⃣ 참색 알고리즘 DFS/BFS
### 5-6.py ###
### 인접 행렬 방식 예제 ###
INF = 999999999 # 무한의 비용 선언
# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
[0,7,5],
[7,0,INF],
[5,INF,0]
]
print(graph)### 5-7.py ###
### 인접 리스트 방식 예제 ###
# 행이 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)
## 인접행렬 방식에 비해 인접 리스트 방식이 메모리 공간 낭비 적다.
## 1) DFS stack
깊이우선탐색
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
### 5-8.py ###
### DFS 예제 ###
## (1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
## (2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문 처리를 한다.
## 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
## (3) (2)번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
# DFS 메서드 정의
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]: # graph[v] = v노드 인접 노드 리스트
if not visited[i]: # 인접 노드 중 방문하지 않은 노드 방문
dfs(graph, i, visited)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 DFs 함수 호출
dfs(graph, 1, visited)
## 2) BFS queue
너비우선탐색
가까운 노드부터 탐색하는 알고리즘
### 5-9.py ###
### BFS 예제 ###
## (1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
## (2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
## (3) (2)번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
from collections import deque
# BFS 메서드 정의
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]: # graph[v] = v노드 인접 노드 리스트
if not visited[i]: # 인접 노드 중 방문하지 않은 노드 방문
queue.append(i)
visited[i] = True
# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)
탐색 문제를 보면 그래프 형태로 표현한 다음 풀이법을 고민하자.
3️⃣ [실전문제] 음료수 얼려 먹기
### 5-10.py ###
### [실전문제] 음료수 얼려 먹기 ###
### DFS 활용 ###
# n, m을 공백으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
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):
# 현재 위치에섯 DFS 수행
if dfs(i,j) == True:
result += 1
print(result) #정답출력
4️⃣ [실전문제] 미로 탈출
### 5-11.py ###
### [실전문제] 미로 탙출 ###
### BFS 활용 ###
### 오류 해결 X
from collections import deque
#n, m을 공백으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 이동할 네 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# BFS 소스코드 구현
def bfs(x,y):
# 큐 구현을 윙해 deque 라이브러리 사용
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]==0:
continue
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny]==1:
graph[nx][ny] = graph[x][y]+1
queue.append((nx,ny))
# 가장 오른쪽 아래까지 최단 거리 반환
return graph[n-1][m-1]
# BFS를 수행한 결과 출력
print(bfs(0,0))
'🌞코딩테스트 > 💜이것이코딩테스트다 [part2]' 카테고리의 다른 글
| 이것이코딩테스트다 | Ch08 다이나믹 프로그래밍 (0) | 2021.07.18 |
|---|---|
| 이것이코딩테스트다 | Ch07 이진 탐색 (0) | 2021.07.17 |
| 이것이코딩테스트다 | Ch06 정렬 (0) | 2021.07.16 |
| 이것이코딩테스트다 | Ch04 구현 (0) | 2021.05.20 |
| 이것이코딩테스트다 | Ch03 그리디 (0) | 2021.05.19 |