자료구조란 자료를 저장하는 방법론, 규칙!
효율성, 추상화, 재사용성을 만족한다면 좋은 자료구조라 할 수 있다.
보통 자료구조는 그것이 특화된 유형들이 있다.
ex) 마지막에 했던 작업을 되돌릴 때 스택 사용
자료구조란 개념적인 것이기 때문에 모든 언어에서 해당 자료구조를 구현할 수 있어야 한다.
특정 라이브러리에 한정되지 않는다.
파이썬에서는 주로 collection이라는 라이브러리를 많이 참조한다.
FILO : First In, Last Out
접시쌓기에 많이 비유된다.
가장 먼저 들어온 것이 가장 마지막에 나간다.
스택은 파이썬에 따로 라이브러리가 없고, array를 사용해서 구현할 수 있다.
이 문제를 풀 수 있으면 웬만한 스택 문제는 응용으로 풀 수 있다.
좀더 어려운 문제는 다음과 같은 문제
FIFO : First In, First Out
push로 쌓이고, pop으로 먼저 들어온 것을 제거한다.
서버의 태스크 분할 시 큐를 많이 사용한다.
필요 없는 부분은 제거해서 메모리를 줄이기 위해서! = 메모리를 효율적으로 쓰기 위해서이다.
스택 + 큐
양쪽에 둘다 넣고 뺄 수 있다.
파이썬에서 큐나 덱을 사용하는 경우, 주로 덱 라이브러리를 사용한다.
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)
관계를 위한 자료구조
노드(node)와 간선(edge)으로 구성
들어오는 간선 수를 indegree
나가는 간선 수를 outdegree
인접행렬
인접 리스트
특수한 구조를 가진 그래프
상하위 구조를 가짐
노드와 간선으로 구성
상/하위 관계가 분명
사이클이 없고, 모든 노드가 연결되어있어야 함 → 노드의 개수가 n개일 때 간선의 개수는 n-1개
사이클이 없다 = 하위노드 하나가 두 개의 상위 노드와 연결될 수는 없음
부모-자식, 선조-자손, 뿌리-잎
1 2 3 4 5 6 7 8
→ [0 1 1 2 2 2 3 6]1 | [2,3] |
---|---|
2 | [4, 5, 6] |
3 | [7] |
4 | |
5 | |
6 | [8] |
7 | |
8 |
핵심: 공통 조상 찾기!
거슬러올라갔을 때 나와 공통된 조상이 있어야 촌수가 존재!!
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)
우선순위가 가장 높은 요소를 root노드로 만든다. 우선순위 큐
라고도 부른다.
3 2 9 1 4 5
값을 추가할 때는 마지막에 붙이고, 최댓값은 맨 꼭대기로 올린다.
힙 정렬은 안정적으로 O(NlogN) 의 시간복잡도를 가진다.
3 7 6 4 2 9 1
기준점보다 크면 왼쪽, 작으면 오른쪽
장점: 수를 찾기 쉽다.
검색시 시간 복잡도가 O(logN) 이다. 그러나 원소들이 한쪽에만 몰려있을 수 있기 때문에 불안정한 시간복잡도를 가진다. → Balancing factor를 만들어서 이러한 약점을 보완한 트리로 레드블랙 트리 등이 있다.
파이썬의 set, dict는 해시 배열로 매핑해서 사용한다.
c++에서는 set, dict가 BST, 레드블랙트리를 기반으로 만들어졌다.