CS 학습 - 9월 2주차 (3) | Paul’s Archives

자료구조와 알고리즘 (feat, TS와 Python 을 얹은)

TypeScript vs. Python: 해시 테이블(Hash Table) 사용법

Python과 TypeScript 모두 해시 테이블(Hash Table) 기능을 언어의 핵심적인 내장 기능으로 제공한다.** Python은 딕셔너리(dict)가 이 역할을 수행하며, TypeScript(JavaScript)에서는 일반 객체(Object)와 더불어 Map 객체를 사용하는 것이 정석이다. Map 객체는 키(key)의 타입이 자유롭다는 점에서 Python의 딕셔너리와 더 유사하다.

해시 테이블은 Key-Value 쌍으로 데이터를 저장하는 자료 구조로, 키를 해시 함수(Hash Function)에 통과시켜 얻은 인덱스(Index)에 값을 저장한다. 이 방식 덕분에 데이터의 추가, 검색, 삭제가 평균적으로 매우 빠른 시간 복잡도(O(1))를 가진다.

1. 해시 테이블의 선언과 초기화

두 언어 모두 직관적인 문법으로 해시 테이블을 생성할 수 있다.

Python: 중괄호 {}를 사용하여 딕셔너리를 생성하는 것이 가장 일반적이다.

# 빈 딕셔너리 생성
hash_table = {}

# 초기 값을 가진 딕셔너리 생성
user = {
    "name": "John Doe",
    "age": 30,
    "is_active": True
}

TypeScript: JavaScript의 Map 객체를 사용하는 것이 가장 강력하고 권장되는 방법이다. Map은 모든 타입의 값을 키로 사용할 수 있어 유연성이 높다.
```
// 빈 Map 생성 (key: string, value: any)
const hashTable = new Map<string, any>();

// 초기 값을 가진 Map 생성
const user = new Map<string, string | number | boolean>([
  ["name", "Jane Doe"],
  ["age", 30],
  ["isActive", true]
]);
```
물론, JavaScript의 일반 객체({})도 해시 테이블처럼 사용할 수 있지만, 키가 문자열이나 심볼(Symbol) 타입으로 제한되는 단점이 있다.

2. 데이터 추가, 접근, 삭제

Key를 이용해 데이터를 조작하는 방식은 두 언어가 매우 유사하다.

Python:

추가/수정: hash_table[key] = value
접근: hash_table[key] (키가 없으면 KeyError 발생) 또는 hash_table.get(key) (키가 없으면 None 반환)
삭제: del hash_table[key]

user = {"name": "John Doe", "age": 30}

# 추가/수정
user["age"] = 31
user["city"] = "Seoul"

# 접근
print(user["name"])       # "John Doe"
print(user.get("email"))  # None

# 삭제
del user["age"]
print(user) # {'name': 'John Doe', 'city': 'Seoul'}

TypeScript (Map 객체 기준):

추가/수정: hashTable.set(key, value)
접근: hashTable.get(key) (키가 없으면 undefined 반환)
삭제: hashTable.delete(key)
키 존재 여부 확인: hashTable.has(key)

const user = new Map<string, any>();

// 추가/수정
user.set("name", "Jane Doe");
user.set("age", 30);
user.set("age", 31); // 수정

// 접근
console.log(user.get("name")); // "Jane Doe"

// 키 존재 여부 확인
console.log(user.has("email")); // false

// 삭제
user.delete("age");
console.log(user); // Map(1) { 'name' => 'Jane Doe' }

3. 순회 (Iteration)

해시 테이블의 모든 Key-Value 쌍을 순회하는 방법도 유사한 패턴을 가진다.

Python: for 루프와 함께 .keys(), .values(), .items() 메서드를 활용한다.

user = {"name": "John Doe", "age": 30}

# Key 순회
for key in user.keys():
  print(key)  # name, age
      
# Value 순회
for value in user.values():
  print(value) # "John Doe", 30
      
# Key, Value 동시 순회
for key, value in user.items():
  print(f"{key}: {value}")

TypeScript (Map 객체 기준): forEach 루프나 for...of 구문을 사용한다.

const user = new Map<string, any>([
  ["name", "Jane Doe"],
  ["age", 30]
]);

// forEach 사용 (value, key 순서)
user.forEach((value, key) => {
  console.log(`${key}: ${value}`);
});

// for...of 사용 (key, value 순서)
for (const [key, value] of user) {
  console.log(`${key}: ${value}`);
}

TypeScript vs. Python: 트리(Tree) 구조 구현 및 사용법

Python과 TypeScript 모두 트리(Tree)는 내장된 자료 구조가 아니므로, 일반적으로 클래스(Class)를 이용해 직접 노드(Node)와 트리 관계를 정의하여 구현해야 한다. 두 언어의 구현 로직은 거의 동일하지만, TypeScript는 제네릭과 타입 시스템을 통해 노드가 가질 데이터의 타입을 명확히 하여 안정성을 확보하는 반면, Python은 더 간결하고 유연한 코드로 빠르게 구현할 수 있다는 점에서 차이를 보인다.

트리는 이름 그대로 나무를 뒤집어 놓은 듯한 계층적 자료 구조이다. 최상위 노드인 루트(Root)에서 시작해 여러 자식 노드(Child Node)가 가지처럼 뻗어 나가는 형태를 가진다. 이진 트리(Binary Tree), 이진 탐색 트리(Binary Search Tree) 등 다양한 종류가 있지만, 여기서는 가장 기본이 되는 노드와 트리 구조의 구현에 초점을 맞춘다.

1. 노드(Node) 및 트리(Tree) 클래스 정의

트리를 구성하는 가장 기본 단위는 데이터와 자식 노드들의 참조를 담고 있는 ‘노드’이다.

Python: 클래스를 이용해 간단하게 노드를 정의할 수 있다. 자식 노드들은 보통 리스트(list)로 관리한다.

# 트리 노드 클래스
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = [] # 자식 노드를 담을 리스트

    def add_child(self, child_node):
        self.children.append(child_node)

# 트리 클래스 (루트 노드를 가짐)
class Tree:
    def __init__(self, root_node):
        self.root = root_node

TypeScript: 제네릭(<T>)을 활용하여 노드가 담을 데이터의 타입을 지정하고, children 배열 역시 해당 노드 타입의 배열임을 명시하여 타입 안정성을 높인다.

// 트리 노드 클래스
class TreeNode<T> {
  public value: T;
  public children: TreeNode<T>[] = []; // 자식 노드를 담을 배열

  constructor(value: T) {
    this.value = value;
  }

  public addChild(childNode: TreeNode<T>): void {
    this.children.push(childNode);
  }
}

// 트리 클래스
class Tree<T> {
  public root: TreeNode<T>;

  constructor(rootNode: TreeNode<T>) {
    this.root = rootNode;
  }
}

2. 트리 순회 (Tree Traversal)

트리의 모든 노드를 방문하는 것을 순회(Traversal)라고 한다. 대표적인 방법으로 깊이 우선 탐색(DFS, Depth-First Search)과 너비 우선 탐색(BFS, Breadth-First Search)이 있다. 여기서는 DFS를 재귀(Recursion) 방식으로 구현하는 예를 보인다.

Python: 재귀 호출을 이용해 간결하게 DFS를 구현할 수 있다.

class Tree:
    def __init__(self, root_node):
        self.root = root_node

    # 깊이 우선 탐색 (DFS)
    def dfs(self, start_node):
        # 현재 노드의 값을 출력 (또는 다른 작업 수행)
        print(start_node.value, end=' ')
            
        # 자식 노드들을 재귀적으로 방문
        for child in start_node.children:
            self.dfs(child)

# 사용 예시
root = TreeNode("A")
b = TreeNode("B")
c = TreeNode("C")
root.add_child(b)
root.add_child(c)

d = TreeNode("D")
e = TreeNode("E")
b.add_child(d)
b.add_child(e)

tree = Tree(root)
tree.dfs(tree.root) # 결과: A B D E C

TypeScript: 로직은 Python과 동일하지만, 노드의 타입을 명시하여 코드의 명확성을 높인다.

class Tree<T> {
  public root: TreeNode<T>;
  // ... 생성자 ...

  // 깊이 우선 탐색 (DFS)
  public dfs(startNode: TreeNode<T>): void {
    // 현재 노드의 값을 출력 (또는 다른 작업 수행)
    process.stdout.write(`${startNode.value} `);

    // 자식 노드들을 재귀적으로 방문
    for (const child of startNode.children) {
      this.dfs(child);
    }
  }
}

// 사용 예시
const root = new TreeNode<string>("A");
const b = new TreeNode("B");
const c = new TreeNode("C");
root.addChild(b);
root.addChild(c);

const d = new TreeNode("D");
const e = new TreeNode("E");
b.addChild(d);
b.addChild(e);

const tree = new Tree(root);
tree.dfs(tree.root); // 결과: A B D E C

힙(Heap) 구현 및 사용법

힙(Heap)의 경우, Python은 heapq라는 강력한 내장 라이브러리를 제공하여 즉시 사용 가능하지만, TypeScript는 직접 클래스로 구현해야 한다.

힙은 ‘완전 이진 트리’의 일종으로, 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같은(최소 힙, Min Heap) 혹은 크거나 같은(최대 힙, Max Heap) 속성을 만족하는 자료 구조이다. 우선순위 큐(Priority Queue)를 구현하는 데 주로 사용된다.

1. Python: `heapq` 모듈 활용

Python은 heapq 모듈을 통해 일반 리스트를 최소 힙처럼 다룰 수 있는 함수들을 제공한다. 이는 매우 효율적이고 파이썬다운(Pythonic) 방식이다.

핵심: 별도의 힙 클래스 없이, 일반 리스트를 heapq 함수에 전달하여 힙 연산을 수행한다.

import heapq

# heapq 모듈은 최소 힙(Min Heap)을 기본으로 한다.
heap = []

# 힙에 원소 추가 (heappush)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

print(heap) # 결과: [1, 3, 7, 4] (힙 속성을 만족하는 리스트)

# 힙에서 가장 작은 원소 삭제 및 반환 (heappop)
smallest = heapq.heappop(heap)
print(smallest) # 결과: 1
print(heap)     # 결과: [3, 4, 7]

2. TypeScript: 직접 클래스로 구현

TypeScript는 내장 힙이 없으므로, 배열을 기반으로 힙의 핵심 연산(sift-up, sift-down)을 포함하는 클래스를 직접 구현해야 한다.

핵심: insert 시에는 추가된 노드를 부모와 비교하며 위로 올리고(siftUp), delete 시에는 루트 노드를 제거한 뒤 마지막 노드를 루트로 가져와 자식과 비교하며 아래로 내린다(siftDown).

// 최소 힙 (Min Heap) 구현
class MinHeap<T> {
  private heap: T[] = [];

  // 부모-자식 인덱스 계산을 위한 헬퍼 함수들
  private getParentIndex(i: number): number { return Math.floor((i - 1) / 2); }
  private getLeftChildIndex(i: number): number { return 2 * i + 1; }
  private getRightChildIndex(i: number): number { return 2 * i + 2; }
  private swap(i1: number, i2: number): void { [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]; }

  // 힙에 원소 추가
  public insert(value: T): void {
    this.heap.push(value);
    this.siftUp(this.heap.length - 1);
  }

  // 가장 작은 원소(루트) 삭제
  public delete(): T | null {
    if (this.heap.length === 0) return null;
    this.swap(0, this.heap.length - 1);
    const deletedValue = this.heap.pop()!;
    this.siftDown(0);
    return deletedValue;
  }

  private siftUp(index: number): void { /* ... 부모와 비교하며 위로 올리는 로직 ... */ }
  private siftDown(index: number): void { /* ... 자식과 비교하며 아래로 내리는 로직 ... */ }
}

그래프(Graph) 구현 및 사용법

그래프(Graph)는 두 언어 모두 내장 기능이 없어 직접 구현해야 하며, 주로 Python은 딕셔너리(dict)를, TypeScript는 Map 객체를 이용해 인접 리스트(Adjacency List) 형태로 표현하는 것이 일반적이다.

그래프는 정점(Vertex 또는 Node)과 그 정점을 연결하는 간선(Edge)의 집합으로 이루어진 자료 구조이다. 소셜 네트워크, 지하철 노선도 등이 그래프의 대표적인 예이다.

1. Python: 딕셔너리를 이용한 인접 리스트

Python에서는 딕셔너리를 사용하여 각 정점을 키(key)로, 해당 정점에 인접한 정점들의 리스트를 값(value)으로 가지는 인접 리스트(Adjacency List) 방식으로 그래프를 표현하는 것이 매우 일반적이다.

class Graph:
    def __init__(self):
        # 키: 정점, 값: 인접 정점 리스트
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, vertex1, vertex2):
        # 무방향 그래프(Undirected Graph)의 경우 양쪽에 모두 추가
        self.adjacency_list[vertex1].append(vertex2)
        self.adjacency_list[vertex2].append(vertex1)

# 사용 예시
graph = Graph()
graph.add_vertex("A")
graph.add_vertex("B")
graph.add_vertex("C")
graph.add_edge("A", "B")
graph.add_edge("B", "C")

print(graph.adjacency_list) 
# 결과: {'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}

2. TypeScript: `Map` 객체를 이용한 인접 리스트

TypeScript에서는 키의 타입이 자유로운 Map 객체를 사용하여 인접 리스트를 구현하는 것이 가장 유연하고 안정적인 방법이다.

class Graph<T> {
  // 키: 정점, 값: 인접 정점 배열
  private adjacencyList: Map<T, T[]> = new Map();

  public addVertex(vertex: T): void {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  public addEdge(vertex1: T, vertex2: T): void {
    // 무방향 그래프(Undirected Graph)의 경우
    this.adjacencyList.get(vertex1)?.push(vertex2);
    this.adjacencyList.get(vertex2)?.push(vertex1);
  }
}

// 사용 예시
const graph = new Graph<string>();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge("A", "B");
graph.addEdge("B", "C");

console.log(graph); 
/* 결과: 
Graph {
  adjacencyList: Map(3) { 'A' => [ 'B' ], 'B' => [ 'A', 'C' ], 'C' => [ 'B' ] }
}
*/

Python 자료 구조별 구현 특징 요약

자료 구조	구현 방식 및 특징	관련 라이브러리 및 설명
배열<br>(Array)	내장 타입인 `list`를 사용한다. 크기가 동적으로 변하며, 모든 타입의 데이터를 담을 수 있는 동적 배열이다.	내장 `list`: 기본적으로 사용.`array` 모듈: C와 유사한 단일 타입의 고정 배열이 필요할 때 사용.
연결 리스트<br>(Linked List)	내장 기능이 없어 `Node` 클래스를 직접 정의하여 구현한다. 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가진다.	(직접 구현): 별도의 표준 라이브러리가 없어 직접 구현이 일반적이다.
스택<br>(Stack)	내장 `list`를 그대로 사용한다. `append()`가 `push` 역할을, `pop()`이 `pop` 역할을 하여 LIFO 구조를 자연스럽게 만족한다.	내장 `list`: 스택을 위한 완벽한 기능을 제공하므로 별도 라이브러리가 불필요하다.
큐<br>(Queue)	`list`의 `pop(0)`는 비효율적이므로, 양방향 데이터 입출력이 빠른 `deque` 객체를 사용하는 것이 정석이다.	`collections.deque`: `append()` (enqueue)와 `popleft()` (dequeue) 연산이 모두 O(1) 시간 복잡도를 가지는 최적의 라이브러리이다.
해시 테이블<br>(Hash Table)	내장 타입인 `dict`를 사용한다. Key-Value 쌍으로 데이터를 저장하며, 매우 빠른 속도로 데이터를 검색, 추가, 삭제할 수 있다.	내장 `dict`: 기본 해시 테이블. `collections.defaultdict`: 존재하지 않는 키를 조회할 때 기본값을 자동으로 생성해준다.
트리<br>(Tree)	내장 기능이 없어 `TreeNode` 클래스를 직접 정의하여 구현한다. 노드가 데이터와 자식 노드 리스트(또는 `left`, `right` 포인터)를 가진다.	(직접 구현): 목적에 맞는 트리(이진 트리, 이진 탐색 트리 등)를 직접 클래스로 구현해야 한다.
힙<br>(Heap)	일반 `list`를 `heapq` 모듈의 함수들로 제어하여 최소 힙(Min Heap)으로 사용한다. 리스트 자체가 힙이 되는 방식이다.	`heapq`: `heappush`, `heappop` 등의 함수를 통해 리스트를 효율적인 우선순위 큐로 만들어주는 표준 라이브러리이다.
그래프<br>(Graph)	내장 기능이 없다. 주로 `dict`를 이용한 인접 리스트 방식으로 구현한다. 딕셔너리의 키는 정점, 값은 인접 정점 리스트이다.	(직접 구현): `dict`와 `list`를 조합해 직접 구현한다. 복잡한 분석이 필요하면 `networkx` 같은 전문 라이브러리를 사용한다.