728x90
자료구조(Implementation)
- 데이터를 표현하고 관리하고 처리하기 위한 구조
- 대표적인 자료구조로는 스택과 큐가 있다.
- 이는 오버플로와 언더플로를 유의하며 사용해야한다.
- 오버플로(Overflow)
- 수용가능 데이터 범위를 벗어나, 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생
- 언더플로(Underflow)
- 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산 수행할 때 발생
스택(Stack)
- 선입후출(First In Last Out) or 후입선출(Last In First Out)
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[::-1])
print(stack)# 실행 결과
>> [5, 2, 3, 1]
>> [1, 3, 2, 5]큐(Queue)
- 선입선출(First In First Out)
from collections import deque
# 큐(Queue) 구현을 위해 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) # 나중에 들어온 원소부터 출력# 실행 결과
>> deque([3, 7, 1, 4])
>> deque([4, 1, 7, 3])- deque 라이브러리의 속도가 리스트 자료형의 속도보다 더 효율적이며 queue 라이브러리보다 간단하다.
재귀 함수(Recursive Function)
- 자기 자신을 다시 호출하는 함수
def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_function()# 실행 결과
> > 재귀 함수를 호출합니다.
> > 재귀 함수를 호출합니다.
> > 재귀 함수를 호출합니다.
...
> > 재귀 함수를 호출합니다.- 팩토리얼 구현 하기
반복🆚재귀 - 반복
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)- 재귀의 경우가 더 간결하게 표현가능
- 점화식(재귀식)
- 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현
DFS(Depth-First Search) - ⭐ 재귀!
- 깊이 우선 탐색
- 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조(혹은 재귀함수)를 이용
가장 깊게 들어갔다가 다시 방문
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더 이상 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)
# 각 정보가 연결된 정보를 표현(2차원 리스트 형태)
graph = [
[], # 0 인덱스는 사용하지 않으므로 비워둠
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현(1차원 리스트) - 처음엔 모두 방문하지 않았으므로 False 초기화
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
- 🔑 DFS에서는 우선 인접노드을 하나만 스택에 넣고 더 이상 넣을 인접노드가 없으면 시작 노드를 스택에서 뺀다!
BFS(Breadth-First Search)
- 너비 우선 탐색
- 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 큐 자료구조
- 일반적인 경우 실제 수행 시간이 DFS보다 좋은 편이다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque([start]) # 노드 넣고 빼는 큐 생성
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력하기
v = queue.popleft() # 큐에서 빼고 해당 노드를 기점으로 인접노드 검사하기 위해 새로운 v값 할당
print(v, end = ' ')
# 아직 방문하지 않은 인접한 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]: # 인접노드중에 방문처리를 안한 노드가 있으면 큐에 넣고 방문처리
queue.append(i)
visited[i] = True
# 각 정보가 연결된 정보를 표현(2차원 리스트 형태)
graph = [
[], # 0 인덱스는 사용하지 않으므로 비워둠
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현(1차원 리스트) - 처음엔 모두 방문하지 않았으므로 False 초기화
visited = [False] * 9
# 정의된 DFS 함수 호출
bfs(graph, 1, visited)
- 🔑 BFS에서는 인접노드들을 모두 큐에 넣고 더 이상 넣을 노드가 없으면 시작 노드를 큐에서 뺀다!
Q1. 음료수 얼려 먹기
문제 설명
N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
입력 조건
- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다.(1 ≤ N, M ≤ 1,000)
- 두 번째 줄부터 N + 1번째 줄까지 얼음 틀의 형태가 주어진다.
- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
출력 조건
- 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.
풀이
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
'''
현재 지점으로 부터의 상하좌우를 살펴보고 값이 '0'이면서
아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
(재귀적 호출)
따로 리턴 값이 없고 방문처리를하기 위한 목적으로 재귀 사용
'''
dfs(x - 1, y)
dfs(x, y - 1)
dfs(x + 1, y)
dfs(x, y + 1)
return True
return False
# n, m을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
result += 1
print(result)- connected component 찾기
- 최초로 방문을 진행하게 되면
dfs(x - 1, y)
dfs(x, y - 1)
dfs(x + 1, y)
dfs(x, y + 1)
해당 부분에서 계속 인접한 부분에 대한 방문처리를 할 수 있기 때문에 아이스크림 덩어리에 대한 개수를 구할 수 있게 된다.
Q2. 미로 탈출
문제 설명
동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
입력 조건
- 첫째 줄에 두 정수 N, M(4 ≤ N, M ≤200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.
출력 조건
- 첫째 줄에 최소 이동 칸의 개수를 출력한다.
풀이
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):
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]
print(bfs(0,0))- 시작 지점에서 가까운 노드부터 모두 탐색하기 위해 BFS 적용
- 이전 노드의 값에 1을 더해가며 최단 거리를 갱신해간다.
해당 포스팅의 내용은
저)나동빈님의 『이것이 취업을 위한 코딩 테스트다 with 파이썬』을
통해 공부한 내용을 토대로 작성하였습니다.
이것이 취업을 위한 코딩 테스트다 with 파이썬
저자 | 나동빈
출판 | 한빛미디어
발매 | 2020.08.05.
728x90
'📊 Algorithm > Paradigm' 카테고리의 다른 글
| [알고리즘 대비 - 이코테] 6. 이진 탐색 (0) | 2022.02.10 |
|---|---|
| [알고리즘 대비 - 이코테] 5. 정렬 (0) | 2022.01.29 |
| [Python Plus] Extended Slices [::-1] (0) | 2022.01.25 |
| [알고리즘 대비 - 이코테] 3. 구현 (0) | 2021.09.19 |
| [알고리즘 대비 - 이코테] 2. 그리디 (0) | 2021.08.20 |