홈으로

소프트웨어 기술(스타트업 위주)

자료구조

자료구조

0. 빅오표기법 (Big-O Notation)

정의

빅오 표기법은 알고리즘의 실행 시간이나 공간 복잡도를 나타내는 수학적 표기법으로, 알고리즘의 성능을 입력 크기 n이 커질 때 어떻게 변화하는지를 표현합니다. 이는 알고리즘의 최악의 실행 시간(또는 공간 복잡도)을 나타내며, 알고리즘의 효율성을 분석할 때 사용됩니다.

주로 사용되는 빅오 표기법

  1. O(1) - 상수 시간
  • 설명: 입력 크기와 관계없이 일정한 시간이 걸리는 알고리즘입니다.
  • 예시: 배열에서 특정 인덱스의 값에 접근하는 경우.
int[] arr = {1, 2, 3};
int value = arr[2];  // O(1)
  1. O(n) - 선형 시간

설명: 입력 크기 n에 비례하여 시간이 증가하는 알고리즘입니다. 예를 들어, 배열을 순차적으로 탐색하는 경우입니다. 예시: 배열에서 모든 요소를 하나씩 출력하는 경우.

for (int i = 0; i < n; i++) {
    console.log(arr[i]);  // O(n)
}
  1. O(n^2) - 이차 시간

설명: 두 개의 중첩된 루프가 있을 때 발생하는 시간 복잡도입니다. 입력 크기 n에 대해 실행 시간이 n^2만큼 증가합니다. 예시: 두 배열을 비교하는 중첩된 반복문.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        consol.log(arr[i] + arr[j]);  // O(n^2)
    }
}

  1. O(log n) - 로그 시간 설명: 이진 탐색과 같은 알고리즘에서 나타나는 시간 복잡도입니다. 입력 크기가 증가할수록 실행 시간은 느리게 증가합니다. 예시: 이진 탐색 알고리즘.

  2. O(n log n) - 선형 로그 시간 설명: 분할 정복 알고리즘에서 자주 나타나는 시간 복잡도입니다. 입력 크기 n에 대해 n log n 만큼 시간이 걸립니다. 예시: 병합 정렬, 퀵 정렬.

빅오 표기법의 중요성

빅오 표기법은 알고리즘을 분석하고 비교하는 데 매우 중요합니다. 알고리즘을 설계할 때, 빅오 표기법을 사용하여 시간 복잡도를 최적화할 수 있는 방법을 모색하고, 입력 크기가 커질 때 알고리즘이 어떻게 성능을 발휘하는지 예측할 수 있습니다.

빅오 표기법 비교

알고리즘 A: O(n) 시간 복잡도를 가진 알고리즘은 입력 크기가 n일 때 선형적으로 실행됩니다. 알고리즘 B: O(n^2) 시간 복잡도를 가진 알고리즘은 입력 크기 n이 두 배가 되면 실행 시간이 4배로 증가합니다. 알고리즘 C: O(log n) 시간 복잡도를 가진 알고리즘은 입력 크기가 n이 두 배가 되어도 실행 시간은 크게 증가하지 않습니다.

1. Array (배열)

정의 배열은 연속된 메모리 공간에 동일한 타입의 데이터를 저장하는 자료구조이다.
각 요소는 인덱스를 통해 접근할 수 있으며, **임의 접근(random access, O(1))**이 가능하다.

특징

  • 장점: 인덱스를 통해 빠른 데이터 접근 가능
  • 단점: 삽입/삭제가 느린 현상(O(n), 중간에서 삽입할 경우)

JavaScript 예시

let arr = [10, 20, 30, 40, 50]

// 요소 접근 (O(1))
console.log(arr[2]) // 30

// 요소 추가 (O(1), 배열 끝에 추가할 때)
arr.push(60)

// 요소 삭제 (O(n), 중간에서 삭제 시)
arr.splice(2, 1) // 30 삭제
console.log(arr) // [10, 20, 40, 50, 60]

2. Linked List (연결 리스트)

정의
연결 리스트는 각 요소(노드)가 다음 노드를 가리킬 수 있는 방식으로 구성된 자료구조이다.
배열과 달리 메모리에 연속적으로 저장되지 않는다.

특징

  • 장점: 크기가 동적으로 변경 가능, 삽입/삭제가 빠름(O(1), 앞이나 중간에서)
  • 단점: 특정 요소 접근이 느림(O(n))

JavaScript 예시 (단일 연결 리스트)

class Node {
  constructor(value) {
    this.value = value
    this.next = null
  }
}

class LinkedList {
  constructor() {
    this.head = null
  }

  append(value) {
    let newNode = new Node(value)
    if (!this.head) {
      this.head = newNode
      return
    }
    let current = this.head
    while (current.next) {
      current = current.next
    }
    current.next = newNode
  }

  print() {
    let current = this.head
    let result = []
    while (current) {
      result.push(current.value)
      current = current.next
    }
    console.log(result.join(' -> '))
  }
}

let list = new LinkedList()
list.append(10)
list.append(20)
list.append(30)
list.print() // 10 -> 20 -> 30

3. Stack (스택)

정의
LIFO(Last In, First Out) 방식으로 동작하는 자료구조.
가장 나중에 추가된 데이터가 가장 먼저 제거된다.

특징

  • 장점: 빠른 데이터 추가/삭제 (O(1))
  • 단점: 중간 요소 접근이 느림 (O(n))

JavaScript 예시

class Stack {
  constructor() {
    this.stack = []
  }

  push(value) {
    this.stack.push(value)
  }

  pop() {
    return this.stack.pop()
  }

  peek() {
    return this.stack[this.stack.length - 1]
  }
}

let stack = new Stack()
stack.push(10)
stack.push(20)
console.log(stack.peek()) // 20
console.log(stack.pop()) // 20
console.log(stack.pop()) // 10

4. Tree (트리)

정의
트리는 계층적 구조를 이루는 자료구조로, 노드(Node)와 간선(Edge)으로 구성된다.
루트(Root) 노드에서 시작하여 각 노드가 여러 개의 자식 노드를 가질 수 있다.

  1. Binary Tree (이진 트리): 모든 노드가 최대 2개의 자식을 가짐

  2. Binary Search Tree (이진 탐색 트리): 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼

  3. Full Binary Tree (포화 이진 트리): 모든 노드가 0개 또는 2개의 자식을 가짐

  4. Complete Binary Tree (완전 이진 트리): 마지막 레벨을 제외하고 모든 레벨이 채워짐

  5. Balanced Tree (균형 트리): 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하

  6. Unbalanced Tree (불균형 트리): 한쪽으로 치우쳐 있어 성능 저하 가능성 있음

특징

  • 장점: 계층적 데이터 표현 가능, 빠른 검색 (이진 탐색 트리 기준 O(log n))
  • 단점: 구현이 복잡할 수 있음

JavaScript 예시 (이진 트리 노드 구현)

class TreeNode {
  constructor(value) {
    this.value = value
    this.left = null
    this.right = null
  }
}

class BinaryTree {
  constructor() {
    this.root = null
  }
}

5. Queue (큐)

정의
FIFO(First In, First Out) 방식으로 동작하는 자료구조.
먼저 추가된 데이터가 먼저 제거된다.

특징

  • 장점: 빠른 데이터 삽입/삭제 (O(1))
  • 단점: 중간 요소 접근이 느림 (O(n))

JavaScript 예시

class Queue {
  constructor() {
    this.queue = []
  }

  enqueue(value) {
    this.queue.push(value)
  }

  dequeue() {
    return this.queue.shift()
  }
}

let queue = new Queue()
queue.enqueue(10)
queue.enqueue(20)
console.log(queue.dequeue()) // 10
console.log(queue.dequeue()) // 20

6. Hash Table (해시 테이블)

정의 해시 테이블은 키-값(Key-Value) 쌍을 저장하는 자료구조이다.
빠른 검색을 위해 해시 함수를 사용하여 데이터를 매핑한다.

JavaScript 예시

let hashTable = new Map()
hashTable.set('name', 'Alice')
hashTable.set('age', 25)
console.log(hashTable.get('name')) // Alice

7. Graph (그래프)

정의 그래프는 **노드(Node)와 간선(Edge)**으로 이루어진 자료구조로, 연결 관계를 나타낼 때 사용한다.

JavaScript 예시 (인접 리스트)

class Graph {
  constructor() {
    this.adjList = new Map()
  }
  addVertex(vertex) {
    this.adjList.set(vertex, [])
  }
}
let graph = new Graph()
graph.addVertex('A')

8. Heap (힙)

정의 힙은 완전 이진 트리 기반의 자료구조로, 최대값 또는 최소값을 빠르게 찾을 수 있다.

JavaScript 예시 (최소 힙)

class MinHeap {
  constructor() {
    this.heap = []
  }
}
Previous
인프라 설계
Next
알고리즘