자료구조
stack과 queue를 사용할 때 overflow와 underflow를 고민해야 한다
- overflow: 특정 자료구조가 수용 가능한 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생
- underflow: 특정 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태.
stack
한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조 "LIFO (Last In First Out)"
- s.top(): 스택의 가장 윗 데이터를 반환
- s.pop(): 스택의 가장 윗 데이터를 삭제
- s.push():스택의 가장 위(top) 자리 위에(top = top + 1) 메모리를 생성 후 데이터 x 넣기
- s.empty(): 스택이 비었다면 1, 아니면 0을 반환
# stack python 연습 코드
stack=[]
stack.append(5) # [5]
stack.append(2) # [5, 2]
stack.append(3) # [5, 2, 3]
stack.append(7) # [5, 2, 3, 7]
stack.pop() # [5, 2, 3]
stack.append(1) # [5, 2, 3, 1]
stack.append(4) # [5, 2, 3, 1, 4]
stack.pop() # [5, 2, 3, 1]
print(stack)
print(stack[::-1])queue
먼저 들어온 것이 먼저 나간다 "FIFO (First In First Out, 선입선출)"
예) 은행의 번호표 체계
- Enqueue: 큐 맨 뒤에 어떠한 요소 추가
- Dequeue: 큐 맨 앞쪽의 요소 삭제
- Peek: front에 위치한 데이터를 읽음
- front: 큐의 맨 앞의 위치 (인덱스)
- rear: 큐의 맨 뒤의 위치(인덱스)
# 파이썬으로 큐를 구현 시 collections 모듈에서 제공하는 deque 자료구조 사용
# 대부분 코딩테스트에서 collections 같은 기본 라이브러리 허용
from collections import deque
queue=deque()
queue.append(5) # deque([5])
queue.append(2) # deque([5, 2])
queue.append(3) # deque([5, 2, 3])
queue.append(7) # deque([5, 2, 3, 7])
queue.popleft() # deque([2, 3, 7])
queue.append(1) # deque([2, 3, 7, 1])
queue.append(4) # deque([2, 3, 7, 1, 4])
queue.popleft() # deque([3, 7, 1, 4])
print(deqeue) # deque([3, 7, 1, 4]): 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # deque([4, 1, 7, 3])재귀 함수
재귀 함수: 자기 사진을 다시 호출하는 함수.
컴퓨터 내부에서 재귀 함수의 수행은 스택 구조를 이용한다. 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.
재귀 함수의 종료 조건
재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 한다. 조건이 명시되지 않으면 무한 호출 가능성이 있다.
def recursive_function():
print('재귀 함수를 호출합니다.")
recursive_function()
recursive_function()팩토리얼 예제
def factorial_iterative(n):
result=1
# 1부터 n까지 수를 차례대로 곱하기
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_iterative(5))그래프의 기본 구조
노드와 간선으로 표현되며 노드를 정점이라고 한다.
그래프 탐색: 1개의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다.
인접 행렬 (Adjacency Matrix)
2차원 배열로 그래프의 연결 관계를 표현하는 방식
단점: 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비.
INF=9999999 # 무한의 비용: 연결이 되어 있지 않은 노드
# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
print(graph) # [[0, 7, 5], [7, 0, 9999999], [5, 9999999, 0]] 인접 리스트 (Adjacency List)
리스트로 그래프의 연결 관계를 표현하는 방식.
장점: 연결된 정보만 저장하므로 메모리를 효율적으로 낭비
단점: 인접 행렬 방식에 비해 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.
python에서는 단순하게 2차원 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) # [[(1, 7), (2, 5), (0, 7), (0, 5)]]
DFS (Depth-First Search)
깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
시간복잡도: O(N)
def dfs (graph, v, visitied):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[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)BFS (Breath First Search)
너비 우선 탐색이라는 의미를 가진다. 가까운 노드부터 탐색
from collections import deque
# BFS의 정의
def bfs (graph, start, visited):
# 큐 (Queue) 구현을 위해 deque 라이브러리 사용
queue =deque([start])
# 현재 노드를 방문 처리
visited[start]=True
# 큐가 빌 때까지 반복
white queue:
v=queue.popleft()
print(v, end='')
# 해당 원소와 연결된, 이직 방문하지 않은 원소들을 큐에 삽입
for i in graph[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
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
