자료 구조 (Data Structures)

자료 구조(Data Structures)는 프로그래밍에서 데이터를 구성하고 조직하는 방법을 말한다. 코딩 테스트에서 자료 구조 문제는 주어진 문제를 해결하기 위해 효율적인 데이터 구조를 사용하는 방법을 확인하는데 사용된다.

Baekjoon - Data Structures

다음은 일반적으로 코딩 테스트에서 자주 출제되는 몇 가지 자료 구조와 관련된 문제 유형이다.

Array & List

배열(Array)은 정적 크기의 동일한 데이터 유형의 항목들을 인덱스로 접근하는 자료 구조이고, 리스트(List)는 동적 크기의 데이터 요소들의 시퀀스로 삽입, 삭제, 검색이 가능한 자료 구조이다.

Priority Queue

우선순위 큐(Priority Queue)는 데이터를 저장하고 관리하는 자료구조로, 각 원소는 우선순위에 따라 정렬되어 있다. 가장 높은 우선순위를 가진 원소에 빠르게 접근할 수 있으며, 일반적으로 힙(heap)을 사용하여 구현된다.

Baekjoon - Priority Queue

	시간복잡도
삽입(Insertion)	O(log n)
삭제(Deletion)	O(log n)
접근(Access)	O(1)

---

PriorityQueue library

from queue import PriorityQueue

# priority queue 초기화
pq = PriorityQueue()

# push
pq.put(4)
pq.put(2)
pq.put(5)
pq.put(3)
pq.put(1)

# pop
num = pq.get() # 1
num = pq.get() # 2
num = pq.get() # 3

# 최상단 접근
top = pq.queue[0] # 4

# 그외
size = pq.qsize() # 2
isEmpty = pq.empty() # False
isFull = pq.full() # True

heapq library

import heapq

# priority queue 초기화
pq = [4,2,5]
heapq.heapify(pq)

# push
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)

# pop
num = heapq.heappop(pq) # 1
num = heapq.heappop(pq) # 2
num = heapq.heappop(pq) # 3

# 최상단 접근
top = pq[0] # 4

Two-Pointer

투포인터(Two-pointer) 알고리즘은 배열 또는 리스트와 같은 순차적인 자료 구조에서 사용되는 알고리즘 기법이며, 일반적으로 두 개의 포인터를 사용하여 구현된다. 이 두 포인터는 주로 배열 또는 리스트의 시작과 끝을 가리키며, 양쪽 끝에서 시작하는 문제와 한쪽 방향에서 시작하는 문제로 구분할 수 있다.

Baekjoon - Two-pointer

---

양쪽 끝에서 시작하는 방식

양쪽 끝에서 시작하여 한 번에 한 칸씩 움직이는 두 개의 포인터를 사용하여 문제를 해결하는 알고리즘이다. 예를 들어, 정렬된 숫자 배열에서 합이 특정한 값이 되는 두 값을 찾는 문제를 풀 때 사용할 수 있다.

알고리즘의 동작은 다음과 같으며 시간복잡도는 O(n)이다:

1. 배열의 시작 위치에 왼쪽 포인터를, 끝 위치에 오른쪽 포인터를 초기화한다.
2. 왼쪽 포인터와 오른쪽 포인터가 만나기 전까지 다음 과정을 반복한다:
   • 현재 왼쪽 포인터와 오른쪽 포인터가 가리키는 값들의 합을 계산한다.
   • 합이 특정 값보다 크다면 오른쪽 포인터를 왼쪽으로 한 칸 이동시킨다.
   • 합이 특정 값보다 작다면 왼쪽 포인터를 오른쪽으로 한 칸 이동시킨다.
   • 합이 특정 값과 일치한다면, 이 두 값은 우리가 찾는 값이므로 알고리즘을 종료한다.
3. 알고리즘이 종료되었는데도 합이 특정 값과 일치하는 두 값이 없다면, 해당 값이 존재하지 않는다는 것을 의미한다.

def two_sum(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [left], right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return None

nums = [2, 7, 11, 15, 18, 22]
target = 29

result = two_sum(nums, target)

---

한쪽 방향에서 시작하는 방식(특정 구간 만들기)

한쪽 방향에서 시작하여 한 번에 한 칸씩 움직이는 두 개의 포인터를 사용하여 문제를 해결하는 방법도 있는데, 대표적으로 특정 구간 만들기 문제가 있다. 예시로는 주어진 숫자들의 리스트에서, 연속된 수열의 합이 특정 값을 가지는지 확인하는 문제가 있다.

해당 문제의 알고리즘의 동작은 다음과 같으며 시간복잡도는 O(n)이다:

1. 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다.
2. 현재 부분 합이 M과 같다면 카운트한다.
3. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다.
4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2-4번 과정을 반복한다.

def find_continuous_sequence(nums, target):
    left, right = 0, 0
    current_sum = 0

    while right < len(nums):
        current_sum += nums[right]

        while current_sum > target and left <= right:
            current_sum -= nums[left]
            left += 1

        if current_sum == target:
            return [left, right]

        right += 1

    return None

numbers = [1, 4, 20, 3, 10, 5]
target_value = 33

result = find_continuous_sequence(numbers, target_value)

---

한쪽 방향에서 시작하는 방식(토끼와 거북이)

다음으로, 토끼와 거북이 알고리즘, 또는 플로이드 순환 찾기 알고리즘(Floyd's Cycle Detection Algorithm)은 사이클이 있는 연결 리스트를 판단하는 데 사용된다. 이때, 알고리즘의 시간복잡도는 O(n)이며, 공간복잡도는 O(1)이다.

다음은 해당 알고리즘의 동작 과정이다:

1. 두 개의 포인터를 초기화한다. 토끼(Rabbit) 포인터와 거북이(Tortoise) 포인터를 리스트의 첫 번째 노드를 가리키도록 설정한다.
2. 토끼 포인터는 한 번에 두 칸씩 이동하고, 거북이 포인터는 한 칸씩 이동한다. 즉, 토끼 포인터는 리스트를 따라 이동하는 속도가 거북이 포인터의 두 배이다.
3. 포인터를 이동한 후에, 토끼와 거북이의 위치를 비교한다. 만약 두 포인터가 같은 위치에 도달한 경우, 사이클이 있는 연결 리스트임을 확인할 수 있다. 이는 토끼 포인터가 거북이 포인터를 한 바퀴 돌아서 따라잡은 것을 의미한다.
4. 사이클이 없는 경우, 즉 토끼 포인터가 리스트의 끝에 도달한 경우, 사이클이 없는 연결 리스트임을 확인할 수 있다.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def has_cycle(head):
    if not head or not head.next:
        return False

    slow = head
    fast = head.next

    while fast and fast.next:
        if slow == fast:
            return True
        slow = slow.next
        fast = fast.next.next

    return False

nodes = [Node(1), Node(2), Node(3), Node(4), Node(5)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i + 1]
nodes[-1].next = nodes[1]

result = has_cycle(nodes[0])

Sliding Window

슬라이딩 윈도우(Sliding Window)는 고정된 크기의 윈도우(부분집합)를 정의하고, 이 윈도우를 배열 또는 리스트에서 한 단계씩 이동시키면서 문제를 해결하는 기술이다.

Baekjoon - Sliding Window

---

일반적으로 슬라이딩 윈도우 알고리즘은 보통 선형 시간(O(n))에 문제를 해결할 수 있으며 다음과 같은 절차로 구현된다:

1. 초기 윈도우 설정: 윈도우의 크기와 초기 위치를 설정한다.
2. 초기 윈도우 내 연산 수행: 초기 윈도우에 대해 필요한 연산을 수행한다.
3. 윈도우 이동: 윈도우를 한 칸씩 이동시킨다.
4. 윈도우 간 연산 업데이트: 이전 윈도우와 새로운 윈도우 간에 중복되는 요소를 처리하고, 필요한 연산을 업데이트한다.
5. 결과 처리: 각 윈도우에서 필요한 연산의 결과를 저장하거나 필요한 조건에 따라 처리한다.
6. 반복: 윈도우를 더 이상 이동할 수 없을 때까지 위의 단계를 반복한다.

def sliding_window(nums, k):
    if not nums or k <= 0 or k > len(nums):
        return []

    # 초기화
    window_sum = sum(nums[:k])
    result = [window_sum]

    for i in range(k, len(nums)):
        # 윈도우에서 왼쪽 요소를 빼고 새로운 요소를 더하여 윈도우의 합 계산
        window_sum = window_sum - nums[i - k] + nums[i]
        result.append(window_sum)

    return result

nums = [1, 3, -1, -3, 5, 7, 2, 1]
k = 3

result = sliding_window(nums, k)

Prefix Sum

구간 합 알고리즘은 배열 또는 리스트와 같은 데이터 구조에서 특정 구간에 속하는 원소들의 합을 효율적으로 계산하기 위한 알고리즘이다. 구간 합을 계산하는 방법에는 여러 가지가 있지만, 가장 일반적인 방법은 누적 합(prefix sum)을 이용하는 것이다.

Baekjoon - Prefix Sum

---

누적 합은 배열의 원소들을 순차적으로 더한 결과를 저장한 배열로, 각 위치에는 해당 위치까지의 원소들의 합이 저장된다.

예) 배열 A의 누적 합 배열을 prefix_sum이라고 할 때, prefix_sum[i]는 A[0]부터 A[i]까지의 구간 합을 나타낸다.

구간 합을 계산할 때, 누적 합 배열을 사용하면 특정 구간의 합을 빠르게 계산할 수 있다.

예) A[i]부터 A[j]까지의 구간 합은 prefix_sum[j] - prefix_sum[i-1]로 계산할 수 있다. 단, i가 0일 경우 prefix_sum[-1]은 0으로 가정한다.

구간 합을 계산하는 데에 누적 합을 사용하면, 배열의 크기가 N이고 Q개의 구간 합 쿼리가 주어졌을 때, 전처리 과정에 O(N)의 시간 복잡도가 필요하며, 각 쿼리에 대해 O(1)의 시간 복잡도로 구간 합을 계산할 수 있다.

def prefix_sum(nums):
    if not nums:
        return []

    prefix = [0] * (len(nums) + 1)  # 누적 합을 저장할 리스트 초기화

    for i in range(1, len(nums) + 1):
        prefix[i] = prefix[i - 1] + nums[i - 1]  # 현재 위치의 누적 합 계산

    return prefix

nums = [1, 3, -2, 5, -7, 2, 5]
result = prefix_sum(nums)

Stack & Queue

스택(Stack)은 후입선출(Last-In, First-Out, LIFO) 원칙을 따르는 자료구조이다. 스택은 데이터를 쌓아 올리듯이 저장하고, 가장 최근에 삽입된 데이터가 가장 먼저 삭제된다.

큐(Queue)는 선입선출(First-In, First-Out, FIFO) 원칙을 따르는 자료구조이다. 큐는 데이터를 한쪽에서 삽입하고 반대쪽에서 삭제하는 방식으로 작동한다.

Baekjoon - Stack

Baekjoon - Queue

# stack과 queue는 보통 deque를 import하여 사용한다
from collections import deque

variable = deque(list)
variable     = deque[index]
deque        = deque1 + deque2
deque        = deque * integer
deque[index] = variable
del deque[index]               # 해당 위치의 요소 삭제

index    = deque.index(variable) # variable가 있는 index 반환, 없으면 error
variable = deque.pop()           # 오른쪽에서 값을 뺌
variable = deque.popleft()       # 왼쪽에서 값을 뺌
integer  = deque.count(variable) # variable의 개수 반환
deque.reverse()                  # deque를 뒤집어줌
deque.insert(index, variable)    # index 자리에 variable 추가
deque.append(variable)           # 오른쪽에 값을 넣음
deque.appendleft(variable)       # 왼쪽에 값을 넣음
deque1.extend(deque2)            # 오른쪽에 deque2를 넣음
deque1.extendleft(deque2)        # 왼쪽에 deque2를 넣음
deque.remove(variable)           # 첫번쨰로 나오는 variable 삭제, 없으면 error
deque.rotate(variable)           # variable이 양수면 오른쪽으로 회전, 음수면 왼쪽으로 회전