자료구조 - Songwooseok123/Study_Space GitHub Wiki
a = [1,2,3]
- a.append(x): O(1)
- a.pop() : O(1) -> pop은 기본적으로 맨 마지막꺼 빼냄
- 근데 list에서 a.pop(0) 이런 특정 index를 지정하는 건 복잡도 O(n)임 -> 복사후 index 한칸씩 땡겨야 되서
- sum,max,min, remove, replace는 복잡도 O(n)
- stask(선입후출) LIFO
- stack은 걍 리스트로구현,
- stack 문제는 pop을 잘 활용해야함.
- 불필요한 for문을 사용해서 탐색하는 것(복잡도 *n 되는것) 보단 마지막 원소만 지우는 것(복잡도 o(1))이 훨씬 이득
- 4949번: 균형잡힌 세상 - 문자열에서 "( )", "[ ]"이 균형을 이루는지
- queue(선입선출, 즉 대기줄) FIFO
- queue는 collections의 deque로 구현
- deque(), popleft()
from collections import deque
ddd= deque()
ddd.append(5)
print(ddd)
ddd.append(4)
print(ddd)
ddd.append(3)
print(ddd)
ddd.popleft()
print(ddd)
'''
deque([5])
deque([5, 4])
deque([5, 4, 3])
deque([4, 3])
'''
d= deque(range(1,int(input())+1))
- 18258번: 큐에 원소 추가, pop 구현 문제
- 가장 큰 원소 혹은 가장 작은 원소를 반복적으로, 효율적으로 뽑아야할 때 사용
- 1715번: 10,20,40의 카드더미 3장이 있는데, 어떻게 정렬해야 OMP(Optimal Mege Pattern)이 가장 작을까?
- 허프만 코딩의 원리에 따라 더미에서 가장 작은 2개를 계속 선택해 나가는 방법
- 1417번: 투표하는데,단독 우승하려면, 나머지 후보들에게서 뺏어와야하는 표 수 구하기 (가장 큰애를 골라서 뺏어와야 겠네)
- (5,7,7) 이면 나머지 두명한테 한표씩 뺏어와서 (6,5,5)로 만들 수 있음.
- 가장 작은 원소 먼저 뺌
- 원소 넣고 빼는데는 logN 복잡도(heapq 쓰던, from queue import PriorityQueue 쓰던)
🔸 heapq
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heapq.heappop(heap)) # 출력: 1
🔹 queue.PriorityQueue
from queue import PriorityQueue
pq = PriorityQueue()
pq.put(3)
pq.put(1)
pq.put(2)
print(pq.get()) # 출력: 1
print(pq) # 하면 <queue.PriorityQueue object at 0x000001AB...> ← 우리가 기대하는 리스트 아님!
pq.empty() # False
pq.qsize() # 길이
백준 1715번 문제를 풀다가 "우선 순위 큐(Priority Queue)"에 대해 알게 되었고 우선순위 큐를 구현하기 위해 파이썬의 heapq 모듈 사용 중 heapq.heappush 하는 과정이 이해가 가지 않아서 이를 계기로 '나동빈'님의 영상을 보게 되었습니다.
import heapq #heap 라이브러리 import
heap_list = []
iterable =[3,5,9,6,4]
for value in iterable :
heapq.heappush(heap_list,value) #heap 라이브러리의 heappush 함수를 이용해서 iterable의 원소를 heap_list에 추가
print(heap_list)
위의 코드는 파이썬에서 heap 라이브러리를 import하고 heapq.heappush 함수를 이용해서
iterable이라는 이름의 list의 원소를 하나씩 heap_list에 추가하는 코드입니다.
코드의 출력으로
[3]
[3, 5]
[3, 5, 9]
[3, 5, 9, 6]
[3, 4, 9, 6, 5]
다음과 같이 나오게 되는데, 결과 5번째 줄에 '원소 4'가 추가 될 때 '원소 5'와 순서가 바뀌는 것을 보고 heap 에 데이터를 추가할 때 따르는 규칙에 대해 궁금하게 되어 '나동빈' 님의 영상을 찾아보게 되었습니다.
이 게시글은 유튜브 '동빈나' 님의 영상(https://www.youtube.com/watch?v=AjFlp951nz0)을 바탕으로 공부한 것을 정리한 내용입니다.
우선 순위 큐(Priority Queue)를 설명하기 앞서 먼저 3가지 자료구조에 대해 알아보도록 하겠습니다.
자료구조 : 추출되는 데이터
- 1. Stack : 가장 나중에 삽입된 데이터부터 추출(LIFO 구조 : Last In First Out)
- 2. Queue : 가장 먼저 삽입된 데이터(FIFO 구조 : First In First Out) ->파이썬에선 보통 'deque' 를 사용해서 구현
- 3. Priority Queue : 가장 우선 순위가 높은 데이터
이 중에서 3. Priority Queue를 구현하는 방법 2가지와 시간 복잡도에 대해 알아 보겠습니다.
Priority Queue를 구현 하는 방법
| PQ 구현 방식 | 삽입 시간 | 삭제 시간 |
|---|---|---|
| List | O(1) | O(N) |
| Heap | O(logN) | O(logN) |
- Heap 정렬 : N개의 데이터를 heap에 넣었다가 꺼내는 작업 -> O(NlogN)
정리 :
"Priority Queue를 구현하는 방법으로 Heap 모듈을 이용할 수 있다"
"데이터를 추가,삭제할 때 최악의 경우에도 시간복잡도 O(logN)로 힙의 성질을 유지할 수 있다는 장점이 있다. "
그렇다면 'Heap'은 뭘까?
Heap : 완전 이진 트리 자료구조의 일종 -> 항상 root node(트리에서 가장 위에 있는 노드)를 제거
- heap에는 min heap과 max heap 2가지 종류가 있는데 그 중에서 min heap에 대해서 자세히 다뤄보도록 하겠습니다.
- Max heap : 루트 노드가 가장 큰 값을 가짐
- Min heap : 루트 노드가 가장 작은 값을 가짐
Min heap 트리 구조
트리에서 상위에 있는 노드를 부모노드, 하위에 있는 노드를 자식 노드라고 합니다.
원소 3은 5와 9의 부모 노드이며 , min heap은 부모노드가 항상 자식노드보다 작은 것을 만족시킵니다.
Heap의 구조에 대해서 알아보니, 처음에 궁금했던 삽입 순서에 대한 이해가 가기 시작했습니다.
[3,5,9,6] 으로만 이뤄져 있던 트리에 원소 4를 넣으니 min heap의 성질을 만족 시키기 위해(4는 5보다 작으니 상위로 올라가야겠다! ) 원소 4가 부모노드로 올라가는 것입니다. 밀려난 원소(5)는 원소 4가 있던 자식 노드로 자리가 바뀝니다.
heap에 원소를 집어 넣을 때 규칙을 알아보았습니다. heap에서 원소를 하나씩 꺼낼 때는 마찬가지로 min heap의 성질을 만족시켜야 합니다
밑의 코드와 결과를 보면 heapq.pop 함수를 통해서 가장 작은 원소부터 꺼내는 것을 확인 할 수 있습니다.
import heapq
heap_list = []
iterable =[3,5,9,6,4]
for value in iterable :
heapq.heappush(heap_list,value)
print(heap_list)
print("")
print("heapq.heappop함수를 이용해 데이터를 하나씩 꺼내보자")
result =[]
for i in range(len(heap_list)):
result.append(heapq.heappop(heap_list))
print(result)
[3]
[3, 5]
[3, 5, 9]
[3, 5, 9, 6]
[3, 4, 9, 6, 5]
heapq.heappop함수를 이용해 데이터를 하나씩 꺼내보자
[3]
[3, 4]
[3, 4, 5]
[3, 4, 5, 6]
[3, 4, 5, 6, 9]
요약
여태까지 우선순위 큐 자료구조와 이를 구현하기 위해 파이썬에서 사용할 수 있는 Heap 모듈에 대해서 알아 보았습니다.
최소값, 최대값을 계속 호출할 때 사용하는 우선순위 큐 자료구조를 구현할 때, heap 모듈을 사용하면 데이터를 추가,삭제할 때 최악의 경우에도 시간복잡도 O(logN)로 힙의 성질을 유지할 수 있다는 장점이 있습니다.
감사합니다.
- 3033번: 문자열 주어지고, 2번이상 반복되는 문자열 중에 가장 긴거 구하기
- 문자열이 반복되는지 구하기 위해서 hash 값으로 비교한다.
- 5525번: 문자열 주어지고, 특정 문자열이 몇 번 등장하는지 구하기(hash로 풀 수 있지만, 시간초과나서 다른 방법이 더 나음)
- 같은 문자열은 해쉬값이 같다.
- 다른 문자열은 해쉬값이 같을 수 있다 -> 다른 문자열을 해쉬값이 다르도록 31진법으로 바꾸는거임. 만약에 대문자 포함한다면 52 이상 진법으로 바꿔야 겠지
- 근데 문자열이 길면 값이 너무 커지니까 매 자리수마다 특정 수(1e9 +7)로 나눠서 나머지를 취한다.
- 각 구간마다 해쉬값을 새로 구하는게 아니라, 전의 해쉬값을 활용해서 다음 해쉬값을 효율적으로 구한다. 밑의 그림 참고
- 비교 연산이 빠르다. 만약에 n짜리 길이 2개 문자열을 비교하려면 n번 비교해서 같은지 판단해야되는데, hash 구해놓으면 걍 정수 2개 비교하면 끝.
- 해쉬 계산을 위한 준비물(모드, 파워)
- 첫 해쉬값 구하기
- 첫 해쉬값을 기반으로 구간 돌면서 hash값 업데이트 하기
- hash 값을 업데이트 할 땐 , 항상 커지면 mod로 나눈다. 음수가 될 거 같으면 mod를 더한다.
- 14465: 정상적으로 작동하는 연속 k개의 신호등이 존재하라면 최소 몇개의 신호등을 수리해야 하는지
- 2559: 연속적인 며칠 k일 동안의 온도의 합이 가장 큰 값을 계산
- 배열의 연속한 구간 합을 구할 때
- 그냥 리스트의 sum은 o(n) 복잡도를 가짐.
- 구간합을 1억 번 구하라그러면 1억번 *n
- 누적합을 한 번만 구해놓으면, 누적합 구하는 복잡도 + 1억번 *1
- a[3]~a[4] 합은 psum[4] - psum[2]
- 1068: 부모 배열이 주어진다. 만약 k노드를 지웠을 때, 리프 노드의 개수를 구하라.
- 14267: 부모(직장 상사) 배열이 주어진다. 상사로부터 칭찬받은 직원과 칭찬의 정도가 주어진다. 칭찬은 내리사랑으로 이뤄진다(칭찬 받은 부하는 그칭찬 정도만큼 그의 부하한테 칭찬해줌) . 이럴 때 직원들의 칭찬 받은 정도 구하기
- 선: 간선/엣지, 점: 노드
- 위로 연결되어 있는 노드들이 모두 조상노드
- 바로 위에 연결되어 있는건 부모노드
- 밑에 연결되어 있는 모든 노드들이 자손노드
- 바로 밑에 연결되어 있는 노드가 자식노드
- 맨 위에 있는게 루트 노드, 맨 밑에 있는게 leaf 노드
- 부모 노드가 뭔지를 저장
- 자식 노드가 뭔지를 저장
- 2606: k 컴퓨터가 바이러스에 걸렸을 때, 바이러스에 걸리게 되는 컴퓨터의 총 수 구하기
- 5567: 친구의 친구까지 결혼식 초대 할 때 총 몇명 초대하는지
- 인접리스트 (인접한 노드로 구성된 배열)
- 간선이 있는지 없는지 고려
- hashtable이라고도 불리고, 파이썬의 dictionary또한 hashtable로 구현되어있다. key와 value 쌍으로 데이터를 저장하는 자료구조를 말한다.
- class는 속성과 method로 이루어져 있음. - init 생성자 : 인스턴스를 만들 때 가장먼저 호출되는 method
class semiGPT(nn.Module):
def __init__(self, vocab_length): # init 생성자
super().__init__()
self.embedding_token_table = nn.Embedding(vocab_length, vocab_length)
def forward(self, inputs, targets=None):
logits = self.embedding_token_table(inputs)
if targets is None:
loss = None
else:
batch, seq_length, vocab_length = logits.shape
logits = logits.view(batch * seq_length, vocab_length)
targets = targets.view(batch*seq_length)
loss = F.cross_entropy(logits, targets)
return logits, loss
def generate(self, inputs, max_new_tokens):
for _ in range(max_new_tokens):
logits, loss = self.forward(inputs)
logits = logits[:, -1, :]
probs = F.softmax(logits, dim=-1)
next_inputs = torch.multinomial(probs, num_samples=1)
inputs = torch.cat((inputs, next_inputs), dim=1)
return inputs
model = semiGPT(ko_vocab_size).to(device) # 여기서 model이 instance임 ("semiGPT 클래스로부터 만들어진 model 인스턴스"라고 표현함)
- model이라는 instance를 만들고,
- model.generate()라는 method를 사용
- super 부분은 부모 클래스의 init 메서드를 호출하는 것이다.
- super는 물려받은 부모 클래스의 메서드에 접근할 수 있게 해줌
- super().init() 호출은 nn.Module(부모)의 생성자(부모클래스의 init에 있는 속성들)를 호출한다. 이는 nn.Module의 모든 기능(method)과 속성을 제대로 초기화하고 사용할 수 있게 하는 단계임.
- 부모 class를 상속하고서 method를 오버라이드 할 수도 있음.
## 부모 클래스
class Monster:
def __init__(self, name, health, attack):
self.name = name
self.health = health
self.attack = attack
def move(self):
print(f"[{self.name}] 지상에서 이동하기")
## 자식 클래스
class Wolf(Monster): # 상속을 받았기 때문에 생성자를 생략함
pass
class Shark(Monster):
def move(self): # 메서드 오버라이딩
print(f"[{self.name}] 헤엄치기")
class Dragon(Monster):
def move(self): # 메서드 오버라이딩
print(f"[{self.name}] 날기")
wolf = Wolf("울프", 1500, 200)
wolf.move()
shark = Shark("샤크", 3000, 400)
shark.move()
dragon = Dragon("드래곤", 8000, 800)
dragon.move()
결과
[울프] 지상에서 이동하기
[샤크] 헤엄치기
[드래곤] 날기
- 파이썬에서 자료형도 클래스다
a= 10
b= 'aaa'
print(b.__dir__())
``` -> class의 메서드를 확인할 수 있다.
</details>