자료구조란 자료를 저장하는 방법론, 규칙!
효율성, 추상화, 재사용성을 만족한다면 좋은 자료구조라 할 수 있다.
보통 자료구조는 그것이 특화된 유형들이 있다.
ex) 마지막에 했던 작업을 되돌릴 때 스택 사용
자료구조란 개념적인 것이기 때문에 모든 언어에서 해당 자료구조를 구현할 수 있어야 한다.
특정 라이브러리에 한정되지 않는다.
파이썬에서는 주로 collection이라는 라이브러리를 많이 참조한다.
STACK
FILO : First In, Last Out
접시쌓기에 많이 비유된다.
가장 먼저 들어온 것이 가장 마지막에 나간다.
스택은 파이썬에 따로 라이브러리가 없고, array를 사용해서 구현할 수 있다.
이 문제를 풀 수 있으면 웬만한 스택 문제는 응용으로 풀 수 있다.
좀더 어려운 문제는 다음과 같은 문제
QUEUE
FIFO : First In, First Out
push로 쌓이고, pop으로 먼저 들어온 것을 제거한다.
서버의 태스크 분할 시 큐를 많이 사용한다.
스택과 큐를 쓰는 이유는?
필요 없는 부분은 제거해서 메모리를 줄이기 위해서! = 메모리를 효율적으로 쓰기 위해서이다.
DEQUE
스택 + 큐
양쪽에 둘다 넣고 뺄 수 있다.
파이썬에서 큐나 덱을 사용하는 경우, 주로 덱 라이브러리를 사용한다.
from collections import deque
풀이
from collections import deque
n, k = map(int, input().split())
dq = deque(range(1, n+1))
print(dq)
ans = list()
while len(dq): # 모두 제거되면 반복문 탈출
dq.rotate(-k+1)
# rotate는 맨 뒤의 요소를 맨 앞으로 보낸다.
# k번째인 요소들을 제거할 것이므로 k-1번 rotate 해야한다.
# 그런데 맨 앞의 요소를 맨 뒤로 보내야 하기 때문에 rotate안에 음수를 넣어준다.
# rotate(n)에서 n이 양수면 뒤 -> 앞으로 동작, n이 음수면 앞 -> 뒤로 동작
ans.append(dq.popleft()) # pop은 last요소를 제거하고, popleft는 first요소를 제거한다.
print(ans)Graph
관계를 위한 자료구조
노드(node)와 간선(edge)으로 구성
들어오는 간선 수를 indegree
나가는 간선 수를 outdegree
그래프를 저장하는 법
-
인접행렬
- 행: 출발 , 열: 도착을 나타내는 행렬로 표현
- 정점의 개수가 n개일때 n*n으로 표현된다.
- 방향성이 있다면 비대칭 행렬이 될 수도 있다.
- 가중치 추가
- 단점 : 0으로 채워진 공간(쓸모이 공간만 차지)이 많아서 메모리 관리가 비효율적이다.
-
인접 리스트
- [[(도착지, 가중치), (도착지, 가중치)], [(도착지, 가중치)]] 와 같이 시작점을 인덱스로 한 리스트로 표현할 수 있다.
Tree
특수한 구조를 가진 그래프
상하위 구조를 가짐
노드와 간선으로 구성
상/하위 관계가 분명
사이클이 없고, 모든 노드가 연결되어있어야 함 → 노드의 개수가 n개일 때 간선의 개수는 n-1개
사이클이 없다 = 하위노드 하나가 두 개의 상위 노드와 연결될 수는 없음
부모-자식, 선조-자손, 뿌리-잎
- 재귀적인 속성을 가짐
- 트리 아래 트리를 서브 트리라고 한다.
트리를 저장하는 법
- 부모만 저장 - 아래에서부터 위로 올라갈 때. 선조 찾아 올라갈 때 유용
→ [0 1 1 2 2 2 3 6]1 2 3 4 5 6 7 8
- 자식만 저장 - 위에서부터 아래로 내려갈 때.
1 [2,3] 2 [4, 5, 6] 3 [7] 4 5 6 [8] 7 8
예제 - 촌수 계산하기
핵심: 공통 조상 찾기!
거슬러올라갔을 때 나와 공통된 조상이 있어야 촌수가 존재!!
풀이 1 - 직계조상일 때 반례가 존재한다.
n = int(input())
a, b = map(int, input().split())
p = [0 for _ in range(n+1)] # 0 은 부모가 없음을 의미
for i in range(int(input())):
x, y = map(int, input().split())
p[y] = x
Aa, Ba = [], [] # 조상
Ad, Bd = 0, 0 # 촌수
while p[a] > 0:
Aa.append((a, Ad))
Ad += 1
A = p[A]
while p[b] > 0:
Ba.append((b, Bd))
Bd += 1
B = p[B]
for i in Aa:
for j in Ba:
if i[0] == j[0]:
print(i[1] + j[1])
exit()
print(-1)내 풀이 - 틀림
만약 다음과 같이 직통으로 쭉 이어진 경우 틀린 답이 나올 수 있다.
증조할머니-할머니-엄마-딸 의 경우, 엄마-딸의 촌수는 1인데, 아래 코드로 하면 사람마다 직계조상과의 촌수를 구해서 더하기 때문에 5가 나와버린다.
def lca(tree, leaf, level):
while tree[leaf]:
leaf = tree[leaf]
level += 1
return lca(tree, leaf, level)
return level, leaf
n = int(input())
a, b = map(int, input().split())
p = [0 for _ in range(n+1)] # 0 은 부모가 없음을 의미
for i in range(int(input())):
x, y = map(int, input().split())
p[y] = x
if lca(p, a, 0)[1] == lca(p, b, 0)[1]:
print(lca(p, a, 0)[0] + lca(p, b, 0)[0])
else:
print(-1)이진트리를 바탕으로 만들어진 자료구조 - 힙, BST
Heap
우선순위가 가장 높은 요소를 root노드로 만든다. 우선순위 큐 라고도 부른다.
3 2 9 1 4 5
값을 추가할 때는 마지막에 붙이고, 최댓값은 맨 꼭대기로 올린다.
힙 정렬은 안정적으로 O(NlogN) 의 시간복잡도를 가진다.
Binary Search Tree - 이진검색트리
3 7 6 4 2 9 1
기준점보다 크면 왼쪽, 작으면 오른쪽
장점: 수를 찾기 쉽다.
검색시 시간 복잡도가 O(logN) 이다. 그러나 원소들이 한쪽에만 몰려있을 수 있기 때문에 불안정한 시간복잡도를 가진다. → Balancing factor를 만들어서 이러한 약점을 보완한 트리로 레드블랙 트리 등이 있다.
파이썬의 set, dict는 해시 배열로 매핑해서 사용한다.
c++에서는 set, dict가 BST, 레드블랙트리를 기반으로 만들어졌다.
