Note 3. 자료구조

"Do it! 알고리즘 코딩 테스트 파이썬 편 [개정판]"을 기반으로 공부한 내용을 정리한 포스팅입니다 📚

---

1️⃣  배열과 리스트

배열
- 메모리의 연속 공간에 채워져 있는 형태의 자료구조
- 인덱스를 사용하여 값으로 바로 접근 
- 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움
- 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없음

리스트
- 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조
- 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야함
- 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도 빠름
- 리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절

‼️ 파이썬
파이썬의 리스트(list)는 리스트의 특징과 배열의 특징까지 모두 가지도록 구현됨

2️⃣  구간 합

‼️ 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 함

- 합 배열 S를 만드는 공식 : S[i] = S[i-1] + A[i]
- 구간 합을 구하는 공식 : S[j] - S[i-1]

ex) 리스트 A의 A[2]부터 A[5]까지의 구간 합을 구한다면
S[5] = A[0] + A[1] + A[2] +A[3] + A[4] + A[5]
S[1] = A[0] + A[1]
S[5] - S[1] = A[2] + A[3] + A[4] + A[5]

ex) 2차원 구간 합 배열
1행 합 배열 구하기 : D[1][j] = D[1][j-1] + A[1][j]
1열 합 배열 구하기 : D[i][1] = D[i-1][1] + A[i][1]
D[i][j]의 값을 채우는 구간 합 공식 : D[i][j] = D[i][j-1] + D[i-1][j] + D[i-1][j-1] + A[i][j]

ex) 질의 (x1,y1) (x2,y2)에 대한 답을 구간 합으로 구하는 방법 = (2,2에서 3,4)까지 의 구간합
D[3][4] - D[1][4] - D[3][1] + D[1][1]
D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]

❗️펜윅 트리(Fenwick Tree)
- 배열에서 값 변경 + 구간 합 계산을 빠르게 하기 위한 자료구조
- 부분합을 트리처럼 쪼개서 저장해두고, 필요한 만큼만 더하거나 빼자

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, diff):
        while i <= self.n:
            self.bit[i] += diff
            i += i & -i

    def prefix_sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

3️⃣  나머지 합

- (A+B)%C는 ((A%C) + (B%C))%C와 같다
- 즉, 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합에 나머지 연산을 한 값은 동일

- 만약 구간 합에서의 나머지 S[j]%M의 값과 S[i]%M의 값이 같다면 (S[j]-S[i])%M은 0이다
- 즉, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[j]와 S[i]가 같은 (i,j)쌍을 찾으면 원본 리스트에서 i+1부터 j까지의 구간 합이 M으로 나누어떨어진다는 것
- 즉, 누적합을 M으로 나눈 나머지가 같은 위치 2개를 고르면, 그 사이 구간합은 M의 배수!

4️⃣  투 포인터

투 포인터 이동 원칙 (연속된 자연수들의 합)
1) sum > N : sum = sum - start_index ; start_index++ (특정 구간의 합이 주어진 합보다 클 경우 start_index를 오른쪽으로 이동시켜 범위를 줄임)

2) sum < N : end_index++ ; sum = sum + end_index (특정 구간의 합이 주어진 합보다 작을 경우 end_index를 오른쪽으로 이동시켜 범위를 늘림)

3) sum = N : end_index++ ; sum = sum + end_index ; count ++ (같을 경우 count += 1 하고 end_index를 이동시켜 범위를 늘려 다른 경우의 수도 확인)

투 포인터 이동 원칙 (리스트에서 두 개의 합 : 리스트 양쪽 끝 값에서 시작)
1) A[i] + A[j] > M : 번호의 합이 M보다 크므로 큰 번호 index를 내리자 (j--)
2) A[i] + A[j] < M : 번호의 합이 M보다 작으므로 작은 번호 index를 올리자 (i++)
3) A[i] + A[j] == M : 양쪽 포인터를 모두 이동시키고 count를 증가시키자 (i++, j--)

5️⃣  슬라이딩 윈도우

2개의 포인터로 범위를 지정한 다음, 범위를 유지한 채로 이동하며 문제를 해결

- 길이가 P인 윈도우를 지정하여 리스트 S의 시작점에 놓고 윈도우를 오른쪽으로 밀면서 윈도우에 잡힌 값들이 조건에 맞는지 탐색
- 리스트 S의 길이만큼 탐색을 진행하므로 O(n)의 시간 복잡도로 문제 해결

6️⃣  파이썬 덱(deque)

- deque는 양쪽 끝에서 삽입과 삭제를 허용하는 일반화된 큐 데이터 구조
- 큐 뿐만 아니라 스택으로도 사용할 수 있는 자료구조
- 양쪽 끝에서 삽입 및 삭제에 대해 O(1) 시간 복잡도를 지원
- (값,인덱스) 형태로 저장
- from collections import deque

7️⃣  스택과 큐

스택(Stack)
- 삽입과 삭제 연산이 후입선출 (가장 마지막에 넣었던 값이 가장 먼저 나온다 = Last-in First-out)
- 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있음
- 파이썬에서의 스택 구현
   1) 삽입 : append
   2) top 위치에 있는 데이터 삭제 : pop
   3) top 위치에 현재 있는 데이터 확인 : s[-1]
- 스택은 깊이 우선 탐색, 백트래킹 종류의 코테에서 효과적 (개념 자체가 재귀 함수 알고리즘 원리와 일맥상통)

큐 (Queue)
- 삽입과 삭제 연산이 선입선출 (먼저 들어온 데이터가 먼저 나간다 = First-in First-out)
- 파이썬에서의 큐 구현 (일반적으로 deque를 이용하여 큐 구현)
   1) rear : 큐에서 가장 끝 데이터를 가리킴
   2) front : 큐에서 가장 앞 데이터를 가리킴
   3) rear 부분에 데이터 삽입 : append
   4) front 부분에 있는 데이터 삭제 : popleft()
   5) 큐의 맨 앞(front)에 있는 데이터 확인 : s[0]
- 큐는 너비 우선 탐색에서 자주 사용

8️⃣  우선순위 큐

들어온 순서가 아니라 ‘우선순위(priority)’에 따라 요소를 꺼내는 자료구조
- 보통 힙(Heap) 구조를 사용
- 힙(Heap)의 특징
   1) 완전 이진 트리 구조
   2) 부모 노드 ≤ 자식 노드 (최소 힙 기준)
   3) 삽입 / 삭제 시간복잡도 : O(log N)
- 우선순위 + 데이터 함께 저장하기
   (priority, value) 튜플 형식으로 저장

# 파이썬에서의 우선순위 큐

# 1) heapq 모듈 (가장 일반적)
# 기본은 최소 힙(min-heap)
# 가장 작은 값이 먼저 나온다
import heapq

pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 5)

print(heapq.heappop(pq))  # 1

# 2) PriorityQueue (queue 모듈)
# 내부적으로 heap 구조 사용
# 멀티스레드 환경에서 안전함
# 대신 heapq보다 느림
from queue import PriorityQueue

pq = PriorityQueue()
pq.put((1, "task1"))
pq.put((0, "task2"))

print(pq.get())  # (0, 'task2')

---

‼️ 끝