코딩테스트에서 자주 출제되는 각 자료구조별 예시 문제

2.1 배열 (Array)

예시 문제:

배열에서 최댓값 찾기

# 배열에서 최댓값 찾기
arr = [3, 5, 1, 2, 4]
max_value = arr[0]
for num in arr:
    if num > max_value:
        max_value = num
print(max_value)  # 5

구현 포인트

1. 초기값 설정: 첫 번째 원소를 임시 최댓값으로 설정합니다.
2. 선형 탐색: 배열의 모든 원소를 순회하며 현재 최댓값과 비교합니다.
3. 갱신 조건: 현재 원소가 최댓값보다 크면 갱신합니다.

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)

 

2.2 연결 리스트 (Linked List)

예시 문제:

단일 연결 리스트 뒤집기

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
    
def reverse_linked_list(head):
    prev = None
    current = head  # 시작 노드(1)
    while current:
        next_node = current.next  # 다음 노드(2) 저장
        current.next = prev       # 현재 노드의 next를 이전 노드로 연결
        prev = current            # prev를 현재 노드로 이동
        current = next_node       # current를 다음 노드로 이동
    return prev  # 새로운 헤드(3)

# 리스트 생성
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# 역순 변환
reversed_head = reverse_linked_list(head)

# 출력
cur = reversed_head
while cur:
    print(cur.data, end=' ')  # 3 2 1
    cur = cur.next

구현 포인트

1. 3포인터 기법: prev, current, next_node를 사용해 노드 연결 방향을 변경합니다.
2. 반복적 처리: 현재 노드의 next를 이전 노드(prev)로 연결합니다.
3. 포인터 이동: 작업 후 포인터를 다음 노드로 이동시킵니다.

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)

 

2.3.1 스택 (Stack)

예시 문제:

괄호가 올바르게 짝지어졌는지 확인

# 괄호가 올바르게 짝지어졌는지 확인
s = "()[]{}"
stack = []
mapping = {')': '(', ']': '[', '}': '{'}
for char in s:
    if char in mapping.values():
        stack.append(char)
    elif char in mapping.keys():
        if stack == [] or mapping[char] != stack.pop():
            print(False)
            break
else:
    print(len(stack) == 0)  # True

구현 포인트

1. 스택 활용: 열린 괄호를 스택에 저장합니다.
2. 매핑 테이블: 닫힌 괄호와 짝이 되는 열린 괄호를 매핑합니다.
3. 불일치 처리: 스택이 비었거나 짝이 맞지 않으면 False 반환합니다.

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)

 

2.3.2 큐 (Queue)

예시 문제:

스택 두 개로 큐 구현하기

class MyQueue:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def enqueue(self, x):
        self.stack_in.append(x)

    def dequeue(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())	# 역순으로 이동
        return self.stack_out.pop() if self.stack_out else None 	# 출력 스택에서 추출


q = MyQueue()
q.enqueue(1)
q.enqueue(2)
print(q.dequeue())  # 1
print(q.dequeue())  # 2

1. 입력 스택과 출력 스택 분리: enqueue는 입력 스택, dequeue는 출력 스택에서 처리합니다.
2. 데이터 이동: 출력 스택이 비면 입력 스택의 모든 데이터를 이동시킵니다.

• Amortized 시간 복잡도: O(1) (데이터 이동이 최악의 경우 O(n)이지만 평균적으로 O(1))

 

2.4 해시 테이블 (Hash Table)

예시 문제:

두 수의 합이 특정 값이 되는 인덱스 찾기 (Two Sum)

# 두 수의 합이 타겟인 인덱스 찾기
nums = [2, 7, 11, 15]
target = 9
hash_map = {}
for i, num in enumerate(nums):
    complement = target - num  # 9-2=7 → 7이 맵에 있는지 확인
    if complement in hash_map:
        print([hash_map[complement], i])  # [0,1]
        break
    hash_map[num] = i  # 현재 숫자 저장

구현 포인트

1. 해시 맵 활용: 숫자와 해당 인덱스를 저장합니다.
2. 보수(complement) 계산: target - 현재 숫자가 해시 맵에 있는지 확인합니다.

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)

 

2.5 트리 (Tree)

예시 문제:

이진 트리의 최대 깊이 구하기

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root):
    if not root:
        return 0  # 리프 노드의 자식은 깊이 0
    left = max_depth(root.left)   # 왼쪽 서브트리 깊이
    right = max_depth(root.right) # 오른쪽 서브트리 깊이
    return max(left, right) + 1   # 현재 노드 깊이 (+1)

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
print(max_depth(root))  # 3

구현 포인트

1. 재귀적 접근: 각 서브트리의 깊이를 계산합니다.
2. 기저 조건: 노드가 None이면 0을 반환합니다.

• 시간 복잡도: O(n)
• 공간 복잡도: O(h) (h: 트리 높이)

 

2.6 힙 (Heap), 우선순위 큐 (Priority Queue)

예시 문제:

K번째로 큰 원소 찾기

import heapq

def find_kth_largest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

nums = [3,2,1,5,6,4]
k = 2
print(find_kth_largest(nums, k))  # 5

 

구현 포인트

1. 최소 힙 사용: 힙 크기를 k로 유지하면 루트가 k번째 큰 원소가 됩니다.
2. 크기 제한: 힙 크기가 k를 초과하면 가장 작은 원소를 제거합니다.

• 시간 복잡도: O(n log k)
• 공간 복잡도: O(k)