자료구조 및 알고리즘 1주차

1. 자료구조와 알고리즘

1.1 자료구조(Data Structure)

정의: 데이터를 어떻게 저장하고, 어떻게 활용할 것인지에 대한 구조적인 방법.
예시: 배열(Array), 연결리스트(Linked List), 스택(Stack), 큐(Queue), 해시테이블(Hash Table) 등.
주요 포인트: 올바른 자료구조 선택은 코드의 효율성(성능)과 가독성, 유지보수성 등에 큰 영향을 미침.

1.2 알고리즘(Algorithm)

정의: 어떤 문제를 해결하기 위한 단계적 절차나 방법.
예시: 정렬(Sort), 탐색(Search), 재귀(Recursion) 등.
주요 포인트: 문제 상황에 맞게 알고리즘을 선택하고, 시간복잡도와 공간복잡도 등을 고려해 효율성을 판단.

2. 시간복잡도(Time Complexity)

2.1 빅오(Big-O), 빅오메가, 빅세타

빅오(Big-O): 알고리즘의 평균/최악 시간복잡도를 간단히 표현 (대개 평균을 Big-O로 표기하는 경우가 많지만, 엄밀히는 최악의 경우를 나타냄).
빅오메가(Ω): 최선의 시간 복잡도.
빅세타(Θ): 평균의 시간 복잡도.
개발 현장에서는 빅오 위주로 효율성을 평가하는 경우가 많음.

2.2 대표적인 시간복잡도 예시

O(1): 상수 시간 → 입력 크기에 관계없이 일정한 실행 시간.
O(n): 선형 시간 → 입력 크기에 비례해 실행 시간 증가.
O(log n): 로그 시간 → 데이터가 커질수록 증가 폭이 완만.
O(n log n): 선형로그 시간 → 정렬 알고리즘(퀵소트, 머지소트 등)에서 자주 등장.
O(n^2): 이차 시간 → 2중 반복문 등이 대표적.

3. 자료구조

3.1 배열(Array)

정의: 연속된 메모리 공간에 데이터를 순차적으로 저장하는 자료구조.
장점: 인덱스를 통해 임의 접근이 가능하므로 조회(access)가 O(1).

단점:

중간에 삽입/삭제가 빈번하면 비효율적(O(n)).
배열 크기가 고정되어 있어, 공간을 재할당해야 하는 경우가 있음.

// 배열 선언 및 접근
const arr = [10, 20, 30];
console.log(arr[0]); // 10  -> O(1)

// 삽입
arr.push(40); // 배열 끝에 추가 -> O(1)

// 중간 삭제
arr.splice(1, 1); // 인덱스 1부터 1개 삭제 -> O(n)
console.log(arr); // [10, 30, 40]

3.2 연결리스트(Linked List)

정의: 데이터를 담은 노드(Node)들이 포인터를 통해 서로 연결된 형태의 자료구조.
장점:
- 삽입/삭제가 빈번한 경우 효율적 (다음 노드 포인터만 변경하면 됨).
- 동적 메모리 할당으로, 배열처럼 크기가 고정되지 않음.
단점:
- 임의 접근이 불가능 → 특정 노드를 찾으려면 처음부터 순회(O(n)).

JavaScript로 간단 구현 예시 (클래스 기반으로 표현)

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

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

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

// 사용 예시
const list = new LinkedList();
list.append(10);
list.append(20);
console.log(list.head.data); // 10
console.log(list.head.next.data); // 20

3.3 스택(Stack)

정의: LIFO(Last In, First Out), 즉 “나중에 들어온 데이터가 먼저 나가는” 구조.

특징:

주로 ‘쌓는다’는 개념.
push(삽입), pop(삭제) 연산이 대표적.

const stack = [];
// push
stack.push(10);
stack.push(20);
// pop
console.log(stack.pop()); // 20 -> 가장 나중에 들어온 데이터부터 꺼냄
console.log(stack.pop()); // 10

용도 예시: 함수 호출 스택, 되돌리기(undo) 기능, 웹 브라우저 뒤로가기 등.

3.4 큐(Queue)

정의: FIFO(First In, First Out), 즉 “먼저 들어온 데이터가 먼저 나가는” 구조.

특징:

주로 “줄을 선다”는 개념.
enqueue(삽입), dequeue(삭제) 연산이 대표적.

const queue = [];
// enqueue
queue.push(10);
queue.push(20);
// dequeue
console.log(queue.shift()); // 10 -> 먼저 들어온 데이터부터 꺼냄
console.log(queue.shift()); // 20

용도 예시: 프린터 작업 대기열, 네트워크 패킷 처리 등.

3.5 덱(Deque)

정의: Double Ended Queue의 약자로, 양쪽(앞뒤) 모두에서 삽입과 삭제가 가능한 자료구조.
특징:
- 스택과 큐의 특성을 모두 가짐.
- 자바스크립트 Array에서도 unshift, shift, push, pop 조합으로 덱 기능을 구현 가능.

3.6 해시테이블(Hash Table)

정의: 해시 함수를 통해 Key → 해시값(인덱스)으로 매핑하여 데이터를 저장하는 구조.
장점:
- 탐색, 삽입, 삭제 등이 평균적으로 O(1).
- Key-Value 형태로 데이터에 접근하기 편리.
단점:
- 해시 충돌(Collision)이 발생하면 연결리스트 등으로 관리되어, 최악의 경우 O(n)까지 갈 수 있음.
- 적절한 해시 함수 선택 및 해시 테이블 크기 관리가 중요.

자바스크립트에선 기본 객체(Object)가 해시 개념

const map = {};
map["apple"] = 1000;  // 해시 함수로 문자열 "apple"을 인덱스로 변환
map["banana"] = 2000;

console.log(map["apple"]);   // 1000
console.log(map["banana"]);  // 2000

실제 구현은 자바스크립트 엔진 내부에서 해시테이블 구조로 동작함.

3.7 집합(Set)

정의: 중복을 허용하지 않는 자료구조.

특징:

해시테이블을 내부적으로 사용(중복 여부를 빠르게 확인).

JavaScript의 Set 객체 사용 예

javascript복사편집const mySet = new Set();
mySet.add(10);
mySet.add(20);
mySet.add(10);  // 중복, 실제로는 추가되지 않음
console.log(mySet); // Set { 10, 20 }

1. 자료구조와 알고리즘

1.1 자료구조(Data Structure)

1.2 알고리즘(Algorithm)

2. 시간복잡도(Time Complexity)

2.1 빅오(Big-O), 빅오메가, 빅세타

2.2 대표적인 시간복잡도 예시

3. 자료구조

3.1 배열(Array)

3.2 연결리스트(Linked List)

3.3 스택(Stack)

3.4 큐(Queue)

3.5 덱(Deque)

3.6 해시테이블(Hash Table)

3.7 집합(Set)