[Job Preparation] 코딩 테스트 준비 : 자료구조 (with Python)

코딩 테스트 준비 : 자료구조 (with Python)

들어가며

• 코딩 테스트 전에 가볍게 읽어볼 자료구조(Data Structure) 관련 내용을 정리해본다
• 파이썬(Python) 코드로 정리하였다.

 

자료구조(Data Structure)

배열(Array)

• 연속된 메모리 공간에 데이터를 저장하며, 인덱스(Index)를 통해 요소에 접근할 수 있다.
• 파이썬의 리스트(@list@)가 배열처럼 사용된다.

arr = [1, 2, 3, 4, 5]

print(arr[2])  # 3
arr.append(6)  # 값 추가
arr.remove(3)  # 값 삭제

 

스택(Stack)

• LIFO(Last In, First Out) 구조
  • 마지막에 들어간 데이터가 가장 먼저 나온다.
• 파이썬의 리스트(@list@)를 스택처럼 사용할 수 있으며, @append()@ 메서드와 @pop()@ 메서드로 동작한다.

stack = []

stack.append(1)  # 값 추가
stack.append(2)
stack.append(3)

print(stack.pop())  # 3 (마지막에 추가된 값이 먼저 나옴)

 

큐(Queue)

• FIFO(First In, First Out) 구조
  • 먼저 들어간 데이터가 먼저 나온다.
• @collections.deque@를 사용하여 효율적으로 구현할 수 있다.

from collections import deque

queue = deque()

queue.append(1)  # 값 추가
queue.append(2)
queue.append(3)

print(queue.popleft())  # 1 (가장 먼저 들어간 값이 먼저 나옴)

 

해시 테이블(Hash Table)

• 키-값(Key-Value) 쌍을 저장
• 키(Key)를 해싱하여 데이터를 저장하고, 빠르게 검색할 수 있다.
• 딕셔너리(@dict@)가 해시 테이블처럼 사용된다.

hash_table = {}

hash_table['key1'] = 'value1'
hash_table['key2'] = 'value2'

print(hash_table['key1'])  # 'value1'

 

트리(Tree)

• 계층적인 구조로, 루트 노드에서 시작하여 자식 노드로 이어지는 데이터 구조
• 이진 트리(Binary Tree) : 각 노드가 최대 2개의 자식 노드를 갖는 트리

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 루트 노드 생성하기
root = Node(1)
root.left = Node(2)
root.right = Node(3)

# 자식 노드 생성하기
root.left.left = Node(4)
root.left.right = Node(5)

# 중위 순회
def inorder_traversal(node): 
    if node:
        inorder_traversal(node.left)
        print(node.value, end=' ')
        inorder_traversal(node.right)

inorder_traversal(root)    # 4 2 5 1 3

 

그래프(Graph)

• 정점(Vertex)와 간선(Edge)으로 이루어진 데이터 구조
  • 정점들이 간선으로 연결된다.
• 딕셔너리(@dict@)로 구현하거나, 리스트(@list@)를 이용한 인접 리스트 방식으로 구현할 수 있다.

graph = {
    1: [2, 3],
    2: [4, 5],
    3: [5],
    4: [],
    5: [4]
}

// 깊이 우선 탐색(DFS)
def dfs(v, visited):
    if v not in visited:
        print(v, end=' ')
        visited.add(v)    # 방문 표시
        for neighbor in graph[v]:
            dfs(neighbor, visited)

visited = set()
dfs(1, visited)  # 1 2 4 5 3

 

실행 과정

• 1번 정점 방문
  • 출력: 1
  • @visited = {1}@
  • 1번 정점과 연결된 2번과 3번이 있다. 먼저 2번 정점으로 이동한다.
• 2번 정점 방문
  • 출력: 2
  • @visited = {1, 2}@
  • 2번 정점과 연결된 4번과 5번이 있다. 먼저 4번 정점으로 이동한다.
• 4번 정점 방문:
  • 출력: 4
  • @visited = {1, 2, 4}@
  • 4번 정점은 더 이상 연결된 정점이 없으므로, 다시 2번으로 돌아온다.
• 5번 정점 방문:
  • 출력: 5
  • @visited = {1, 2, 4, 5}@
  • 5번 정점과 연결된 4번이 있지만, 이미 방문했으므로 넘어간다. 다시 2번으로 돌아간다.
• 3번 정점 방문:
  • 출력: 3
  • @visited = {1, 2, 3, 4, 5}@
  • 3번 정점과 연결된 5번이 있지만, 이미 방문했으므로 종료된다.

 

⇒ DFS는 1번에서 출발해 한 정점의 깊이로 계속 들어가며 탐색하고, 더 이상 들어갈 수 없을 때 다음 이웃 정점으로 이동하는 원리로 작동한다.

 

 

힙(Heap)

• 완전 이진 트리(Complete Binary Tree)의 일종
• 최소값이나 최대값을 빠르게 찾을 수 있는 자료구조
• 최소 힙(Min Heap)과 최대 힙(Max Heap)으로 구분된다.
• @heapq@ 모듈을 사용하여 최소 힙을 구현할 수 있다.

import heapq

min_heap = []

heapq.heappush(min_heap, 3)  # 값 추가
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 5)

print(heapq.heappop(min_heap))  # 1 (최소값이 먼저 나옴)

 

트라이(Trie)

• 문자열을 저장하고 탐색하는 데 최적화된 트리 구조
• 주로 문자열 검색 문제에서 사용된다.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

trie = Trie()

trie.insert("apple")

print(trie.search("apple"))  # True
print(trie.search("app"))    # False

 

유니온 파인드(Union-Find)

• 서로소 집합(Disjoint Set)을 표현하기 위한 자료구조
• 그래프의 연결 요소를 찾거나 합칠 때 사용된다.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX

uf = UnionFind(5)

uf.union(0, 1)
uf.union(1, 2)

print(uf.find(0) == uf.find(2))  # True (같은 집합)
print(uf.find(0) == uf.find(3))  # False (다른 집합)