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

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

TypeScript vs. Python: 배열(Array) 사용법 비교

TypeScript는 정적 타입을 지원하여 코드의 안정성을 높이는 반면, Python은 동적 타이핑으로 유연하고 간결한 코드 작성을 지원한다.

1. 배열의 선언과 초기화

가장 큰 차이점은 타입 명시 여부이다. TypeScript는 변수 선언 시 타입을 지정하여 예측 가능하고 안정적인 코드를 작성하도록 유도하는 반면, Python은 타입을 명시하지 않아도 되어 간결하다.

TypeScript: 배열이 담을 요소의 타입을 명시적으로 지정해야 한다.
- let list: number[] = [1, 2, 3];
- let list: Array<number> = [1, 2, 3];
- 다양한 타입을 허용하려면 유니온 타입((string | number)[])을 사용할 수 있다.
Python: 파이썬의 리스트는 기본적으로 모든 데이터 타입을 담을 수 있는 동적 배열이다.
- my_list = [1, "hello", True]
- 타입을 강제하고 싶다면 array 모듈을 사용하거나, 타입 힌트(Type Hint)를 활용할 수 있으나, 이는 강제 사항이 아니다.
- from array import array
- arr = array('i', [1, 2, 3])

2. 요소 접근, 추가 및 삭제

배열의 요소를 다루는 기본적인 방법은 유사하지만, 사용하는 메서드의 이름과 기능에서 차이가 나타난다.

기능	TypeScript	Python (List)	설명
요소 접근	`arr[0]`	`my_list[0]`, `my_list[-1]`	TypeScript와 Python 모두 인덱스로 요소에 접근한다. Python은 음수 인덱스를 지원하여 뒤에서부터 접근이 가능하다.
맨 뒤에 요소 추가	`arr.push(4)`	`my_list.append(4)`	가장 일반적인 요소 추가 방식이다.
맨 앞에 요소 추가	`arr.unshift(0)`	`my_list.insert(0, 0)`	TypeScript에는 `unshift`라는 명확한 메서드가 있다.
특정 인덱스에 요소 추가	`arr.splice(1, 0, 1.5)`	`my_list.insert(1, 1.5)`	`splice`는 추가, 삭제, 교체가 모두 가능하여 더 강력하다.
맨 뒤 요소 삭제	`arr.pop()`	`my_list.pop()`	두 언어 모두 동일한 이름의 메서드를 사용한다.
맨 앞 요소 삭제	`arr.shift()`	`my_list.pop(0)` 또는 `del my_list[0]`	TypeScript는 `shift` 메서드를 제공한다.
특정 인덱스 요소 삭제	`arr.splice(1, 1)`	`my_list.pop(1)` 또는 `del my_list[1]`	특정 위치의 요소를 삭제하는 기능이다.
특정 값으로 요소 삭제	(직접 구현 필요)	`my_list.remove(3)`	Python은 값으로 요소를 찾아 삭제하는 `remove` 메서드를 기본 제공한다.

3. 배열 순회 (반복)

배열의 모든 요소를 순차적으로 접근하여 작업을 수행하는 반복문에서도 약간의 차이가 존재한다.

TypeScript: for...of, forEach, 그리고 전통적인 for 루프를 주로 사용한다.
- for…of: 배열의 ‘값(value)’을 순차적으로 가져온다. (가장 권장되는 방식 중 하나)
```
let list: number[] = [10, 20, 30];
for (const value of list) {
    console.log(value);
}
```
- forEach: 각 요소에 대해 콜백 함수를 실행한다.
```
list.forEach((value, index) => {
    console.log(`Index ${index}: ${value}`);
});
```
Python: for...in 구문을 사용하는 것이 가장 일반적이고 파이썬다운(Pythonic) 방법이다.
- for…in: 배열의 ‘값(value)’을 순차적으로 가져온다.
```
my_list = [10, 20, 30]
for value in my_list:
    print(value)
```
- enumerate: 인덱스와 값을 함께 가져와야 할 때 유용하게 사용된다.
```
for index, value in enumerate(my_list):
    print(f"Index {index}: {value}")
```

TypeScript vs. Python: 배열 순회 및 변형 심화

TypeScript는 메서드 체이닝(Method Chaining)을 통해 가독성을 높이는 반면, Python은 리스트 컴프리헨션이라는 독특하고 간결한 구문을 통해 강력한 기능을 제공한다.

1. 배열의 각 요소를 변형하기 (Mapping)

map은 배열의 모든 요소를 순회하며 주어진 함수를 적용하여 새로운 배열을 생성하는 기능이다. 원본 배열은 변경되지 않는다.

TypeScript: map() 메서드를 사용한다.
```
const numbers: number[] = [1, 2, 3, 4];
const squared: number[] = numbers.map(num => num * num);
// squared: [1, 4, 9, 16]
```
각 요소에 함수를 순차적으로 적용하고 그 결과값을 모아 새로운 배열로 반환하는 직관적인 방식이다.

Python: 리스트 컴프리헨션(List Comprehension)이 가장 일반적이고 효율적인 방법이다. map() 함수도 존재한다.

리스트 컴프리헨션:
```
numbers = [1, 2, 3, 4]
squared = [num * num for num in numbers]
# squared: [1, 4, 9, 16]
```
대괄호 안에 for 루프를 포함하는 형태로, 매우 간결하고 가독성이 높다고 평가받는다.

map() 함수:

def square(num):
    return num * num

numbers = [1, 2, 3, 4]
# map 객체를 반환하므로 list로 변환 필요
squared = list(map(square, numbers)) 
# squared: [1, 4, 9, 16]

2. 조건에 맞는 요소만 걸러내기 (Filtering)

filter는 배열의 모든 요소를 순회하며, 주어진 함수의 결과값이 true인 요소들만 모아 새로운 배열을 생성하는 기능이다.

TypeScript: filter() 메서드를 사용한다.

const numbers: number[] = [1, 2, 3, 4, 5];
const evens: number[] = numbers.filter(num => num % 2 === 0);
// evens: [2, 4]

Python: 여기서도 리스트 컴프리헨션이 널리 쓰인다.

리스트 컴프리헨션:

numbers = [1, 2, 3, 4, 5]
evens = [num for num in numbers if num % 2 == 0]
# evens: [2, 4]

for 루프 뒤에 if 조건을 추가하여 필터링 기능을 구현한다.

filter() 함수:

numbers = [1, 2, 3, 4, 5]
# filter 객체를 반환하므로 list로 변환 필요
evens = list(filter(lambda num: num % 2 == 0, numbers))
# evens: [2, 4]

3. 배열을 하나의 값으로 통합하기 (Reducing)

reduce는 배열의 각 요소에 대해 주어진 리듀서(reducer) 함수를 실행하여 하나의 결과값을 반환한다. 누적 계산에 주로 사용된다.

TypeScript: reduce() 메서드를 사용한다.

const numbers: number[] = [1, 2, 3, 4, 5];
const sum: number = numbers.reduce((accumulator, currentValue) => accumulator + currentValue, 0);
// sum: 15
// 0은 accumulator의 초기값이다.

accumulator는 이전 콜백의 반환값이 누적되는 변수이고, currentValue는 현재 처리 중인 요소이다.

Python: functools 모듈의 reduce() 함수를 사용해야 한다. (Python 3.x부터 내장 함수에서 모듈로 이동했다)

from functools import reduce

numbers = [1, 2, 3, 4, 5]
sum_value = reduce(lambda accumulator, current_value: accumulator + current_value, numbers, 0)
# sum_value: 15
# 0은 초기값(initializer)이다.

물론, 합계를 구하는 경우 파이썬의 내장 함수 sum()을 쓰는 것이 훨씬 간단하고 효율적이다.

sum_value = sum(numbers) # 결과: 15

TypeScript vs. Python: 연결 리스트(Linked List) 구현 및 사용법

TypeScript와 Python 모두 연결 리스트(Linked List)를 직접 구현해야 한다는 점은 동일하다. 두 언어 모두 배열(리스트)과 달리 내장된 연결 리스트 자료 구조를 제공하지 않기 때문. 하지만 TypeScript는 타입 시스템을 활용해 노드(Node)의 구조를 명확하게 정의하여 안정성을 높이는 반면, Python은 간결한 문법으로 더 빠르게 구현할 수 있다.

연결 리스트는 각 요소가 데이터와 다음 요소를 가리키는 포인터(참조)를 함께 가지고 있는 선형 자료 구조이다. 배열과 달리 메모리에 연속적으로 위치하지 않아 삽입과 삭제가 효율적이다.

1. 노드(Node)와 리스트 구조 정의

연결 리스트를 구현하는 첫 단계는 기본 단위인 노드를 정의하는 것이다.

TypeScript: interface나 class를 사용해 노드의 형태를 명확하게 정의한다. 타입 시스템 덕분에 value의 타입과 next 포인터가 Node 혹은 null임을 강제할 수 있다.

// 노드의 구조 정의
interface INode<T> {
  value: T;
  next: INode<T> | null;
}

// 노드 클래스
class Node<T> implements INode<T> {
  public value: T;
  public next: INode<T> | null = null;

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

// 연결 리스트 클래스
class LinkedList<T> {
  private head: INode<T> | null = null;
  // ... 추가적인 메서드들
}

Python: class를 사용하여 노드를 정의한다. 타입 힌트(Type Hint)를 사용할 수는 있지만, TypeScript처럼 강제되지는 않는다.

# 노드 클래스
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# 연결 리스트 클래스
class LinkedList:
    def __init__(self):
        self.head = None
    # ... 추가적인 메서드들

2. 핵심 연산: 노드 추가 및 순회

가장 기본적인 연산인 ‘맨 뒤에 노드 추가’와 ‘리스트 순회’를 비교해 본다. 로직 자체는 동일하지만, 코드의 세부적인 표현에서 차이가 나타난다.

TypeScript: 타입 검사를 통과해야 하므로 null 체크가 명시적으로 이루어진다.

class LinkedList<T> {
  private head: Node<T> | null = null;

  // 맨 뒤에 노드 추가
  public append(value: T): void {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }

    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }

  // 리스트 순회 및 출력
  public printAll(): void {
    let current = this.head;
    const values: T[] = [];
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join(' -> '));
  }
}

Python: 문법이 더 간결하며, None을 활용한 null 체크가 자연스럽게 이루어진다.

class LinkedList:
    def __init__(self):
        self.head = None

    # 맨 뒤에 노드 추가
    def append(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
            return

        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
            
    # 리스트 순회 및 출력
    def print_all(self):
        values = []
        current = self.head
        while current:
            values.append(str(current.value))
            current = current.next
        print(" -> ".join(values))

결론적으로, 두 언어 모두 동일한 자료 구조의 원리를 따라 연결 리스트를 구현한다. TypeScript는 제네릭(T)과 인터페이스를 통해 재사용 가능하고 타입-안전(type-safe)한 코드를 작성하도록 유도하는 반면, Python은 더 적은 코드로 빠르게 핵심 로직을 구현하는 데 강점을 보인다.

TypeScript vs. Python: 스택(Stack) 구현 및 사용법

스택(Stack) 역시 TypeScript와 Python 모두 내장된 자료 구조가 아니므로, 배열(리스트)을 활용하여 직접 구현하는 것이 일반적이다. 두 언어의 구현 방식은 매우 유사하며, 핵심적인 차이는 TypeScript의 타입-안전성(Type-Safety)과 Python의 간결함에서 비롯된다.

스택은 ‘마지막에 들어온 것이 가장 먼저 나가는’(LIFO, Last-In, First-Out) 원칙을 따르는 자료 구조이다. 접시를 쌓고 위에서부터 차례로 꺼내는 것을 생각하면 이해하기 쉽다.

1. 스택의 구현 방식

배열(리스트)의 끝에서 데이터를 추가하고 제거하는 push와 pop 연산은 스택의 LIFO 동작 원리와 완벽하게 일치한다. 따라서 배열을 감싸는(wrapping) 클래스를 만들어 스택을 구현하는 것이 가장 효율적이다.

TypeScript: 제네릭(<T>)을 사용하여 어떤 타입의 데이터든 담을 수 있는 타입-안전한 스택 클래스를 정의한다. 내부 배열을 private으로 선언하여 외부에서 직접 접근하는 것을 막고, push, pop 같은 메서드를 통해서만 조작하도록 캡슐화하는 것이 일반적이다.

class Stack<T> {
  private items: T[] = [];

  // 스택에 데이터 추가 (push)
  push(item: T): void {
    this.items.push(item);
  }

  // 스택에서 데이터 추출 (pop)
  pop(): T | undefined {
    return this.items.pop();
  }

  // 스택의 가장 위 데이터 확인 (peek)
  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }

  // 스택이 비어있는지 확인
  isEmpty(): boolean {
    return this.items.length === 0;
  }
}

Python: Python의 리스트는 그 자체로 스택처럼 사용될 수 있다. append() 메서드가 push 역할을, pop() 메서드가 pop 역할을 한다. 가독성과 재사용성을 위해 클래스로 감싸는 것이 좋은 관례이다.

class Stack:
    def __init__(self):
        # 관례적으로 _ 를 붙여 내부에서만 사용함을 표시
        self._items = []

    # 스택에 데이터 추가 (push)
    def push(self, item):
        self._items.append(item)

    # 스택에서 데이터 추출 (pop)
    def pop(self):
        if not self.is_empty():
            return self._items.pop()
        return None # 혹은 예외 발생

    # 스택의 가장 위 데이터 확인 (peek)
    def peek(self):
        if not self.is_empty():
            return self._items[-1] # 음수 인덱싱 활용
        return None

    # 스택이 비어있는지 확인
    def is_empty(self):
        return not self._items

2. 핵심 연산 비교

스택의 핵심 연산인 push, pop, peek를 비교하면 두 언어의 철학 차이가 드러난다.

기능	TypeScript	Python (List 기반)	설명
Push (추가)	`items.push(item)`	`_items.append(item)`	TypeScript는 `push`, Python은 `append`를 사용하여 배열(리스트)의 끝에 요소를 추가한다.
Pop (추출)	`items.pop()`	`_items.pop()`	두 언어 모두 동일한 이름의 `pop()` 메서드를 사용하며, 배열의 마지막 요소를 제거하고 반환한다.
Peek (확인)	`items[items.length - 1]`	`_items[-1]`	Python의 음수 인덱싱(`-1`)이 마지막 요소를 가리키므로 코드가 더 간결하다.

결론적으로, 스택을 구현하는 알고리즘은 두 언어에서 동일하다. TypeScript는 정적 타입을 통해 의도치 않은 타입의 데이터가 스택에 들어오는 것을 컴파일 시점에 막아주어 안정성을 높여준다. 반면, Python은 특유의 간결한 문법(음수 인덱싱 등)을 통해 더 빠르게 코드를 작성할 수 있는 장점이 있다.

언더바(_)의 의미

싱글 언더스코어 : _var(보호된 멤버) 클래스 상에서 싱글 언더스코어는 보호된 멤버라는 뜻, 즉, 내부 사용용이니 조심히 사용하는 것을 권장한다는 의미를 내포함. 클래스 서계자의 의도와 다르게 사용될 수 있으니 주의가 필요함.

더블 언더스코어 : __var(비공개 멤버) 외부에서 사용을 적극적으로 막기 위해 사용되는 케이스. Python 인터프리터가 이 변수의 이름을 Name Mangling 이라는 기술로, 사용시 내부적으로 __items 를 __ClassName__items 로 형태를 바꾸며, 사용시 AttributeError 가 발생될 수 있다.

TypeScript vs. Python: 큐(Queue) 구현 및 사용법

큐(Queue)를 구현할 때, Python은 collections 모듈에 포함된 deque라는 매우 효율적인 자료 구조를 기본으로 제공한다. 반면, TypeScript는 내장된 큐 자료 구조가 없어 개발자가 직접 구현해야 하며, 간단한 배열(Array)을 사용하거나 성능을 위해 연결 리스트(Linked List)를 기반으로 만들어야 한다.

큐는 ‘가장 먼저 들어온 것이 가장 먼저 나가는’(FIFO, First-In, First-Out) 원칙을 따르는 자료 구조이다. 은행 창구나 놀이공원의 줄서기를 생각하면 쉽게 이해할 수 있다.

1. 큐 구현 방식의 핵심 차이

큐의 핵심은 한쪽 끝(rear)에서는 데이터를 추가하고, 반대쪽 끝(front)에서는 데이터를 제거하는 것이다. 이 “앞에서 제거하는” 연산 때문에 일반적인 배열(리스트)을 사용하면 성능 문제가 발생할 수 있다.

배열의 비효율성: 배열의 맨 앞 요소를 제거(shift() 또는 pop(0))하면, 그 뒤의 모든 요소들을 한 칸씩 앞으로 당겨야 한다. 이 작업은 배열의 크기가 클수록 오래 걸리는, 즉 성능이 좋지 않은 연산(시간 복잡도 O(n))이다.
Python의 해결책: Python은 이러한 문제를 해결하기 위해 양쪽 끝에서 데이터를 추가하고 제거하는 속도(O(1))가 매우 빠른 deque(데크, double-ended queue)를 제공한다.
TypeScript의 선택지: TypeScript는 개발자가 상황에 맞게 구현 방식을 선택해야 한다.
1. 간단한 구현: 배열의 shift() 메서드를 사용해 간단히 구현 (데이터가 적을 때 유용).
2. 성능적 구현: 이전에 다룬 연결 리스트를 기반으로 직접 구현 (데이터가 많고 성능이 중요할 때).

2. Python: `collections.deque` 활용

Python에서 큐를 구현할 때는 deque를 사용하는 것이 가장 표준적이고 효율적인 방법이다.

from collections import deque

class Queue:
    def __init__(self):
        # deque 객체를 내부에서 사용한다.
        self._items = deque()

    # 큐의 뒤쪽에 데이터 추가 (enqueue)
    def enqueue(self, item):
        self._items.append(item)

    # 큐의 앞쪽에서 데이터 추출 (dequeue)
    def dequeue(self):
        if not self.is_empty():
            # popleft()는 O(1) 시간 복잡도를 가진다.
            return self._items.popleft()
        return None

    # 큐의 가장 앞 데이터 확인 (peek)
    def peek(self):
        if not self.is_empty():
            return self._items[0]
        return None

    # 큐가 비어있는지 확인
    def is_empty(self):
        return not self._items

3. TypeScript: 배열 또는 연결 리스트 활용

TypeScript에서는 내장된 deque가 없으므로, 두 가지 방식으로 접근할 수 있다.

1. 배열을 이용한 간단한 구현

가장 직관적이고 빠르게 구현할 수 있는 방법이지만, 성능 저하의 가능성을 인지하고 있어야 한다.

class Queue<T> {
  private items: T[] = [];

  // 큐의 뒤쪽에 데이터 추가 (enqueue)
  enqueue(item: T): void {
    this.items.push(item);
  }

  // 큐의 앞쪽에서 데이터 추출 (dequeue)
  dequeue(): T | undefined {
    // shift()는 O(n)의 시간 복잡도를 가져 성능에 불리할 수 있다.
    return this.items.shift();
  }

  // 큐의 가장 앞 데이터 확인 (peek)
  peek(): T | undefined {
    return this.items[0];
  }

  // 큐가 비어있는지 확인
  isEmpty(): boolean {
    return this.items.length === 0;
  }
}

2. 성능을 위한 연결 리스트 기반 구현

데이터의 양이 많고, 추가/삭제가 빈번하게 일어나는 등 성능이 중요한 상황에서는 연결 리스트를 기반으로 큐를 구현하는 것이 정석이다. 연결 리스트의 head에서 노드를 제거하고(dequeue), tail에 새로운 노드를 추가(enqueue)하는 방식이다. 이 경우, 두 연산 모두 O(1)의 빠른 시간 복잡도를 보장받을 수 있다.