자료구조와 알고리즘(Data Structures & Algorithms)

[알고리즘과 자료구조를 배우는 이유]
1. 문제 해결의 틀을 제공해준다
=> 데이터를 효율적으로 저장하고 관리해야 프로그램이 느려지지 않고 메모리 낭비 없이 동작한다.
2. 코딩테스트 필수
=> 제한된 시간 안에 큰 입력을 처리하려면 적절한 자료구조와 알고리즘을 선택해 최적화해야 합격 가능성이 높아진다.

 

 

1. 자료구조(Data Structure)

데이터를 효율적으로 저장·조회·갱신하기 위한 “틀”(컨테이너)

 

• 검색이 잦으면 → 조회가 빠른 DS
• 삽입·삭제 잦으면 → 그 연산을 빠르게 지원하는 DS
• 메모리 사용량도 고려해 선택

 

자료구조의 종류

 

• 배열(Array)
  • 메모리에 연속 저장
  • 연산 비용:
    • 인덱스 접근: O(1)
    • 삽입·삭제(끝 제외): O(n)
  • 사용 예시:
    • 고정 크기 데이터 저장, 순차적 순회가 많을 때 적합

// 배열 생성 및 인덱스 접근 예시
const arr = [10, 20, 30];
// 인덱스 1에 바로 접근 → O(1)
console.log(arr[1]);  // 20
// 중간 삽입 → O(n)
arr.splice(1, 0, 15); // [10, 15, 20, 30]

• 연결 리스트(Linked List)
  • 노드 단위로 포인터 연결
  • 연산 비용:
    • 탐색: O(n)
    • 삽입·삭제(노드 알고 있을 때): O(1)
  • 사용 예시:
    • 중간 삽입·삭제가 빈번한 경우 유리

// 단순 연결 리스트 삽입 예시
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
let head = new Node(1);
head.next = new Node(2);
// 중간 삽입: 새로운 노드 연결만 O(1)
const newNode = new Node(1.5);
newNode.next = head.next;
head.next = newNode;

• 집합(Set)
  • 중복 제거, 포함 여부 has() O(1) (해시 기반)
  • 구현: 해시 테이블 기반
  • 사용 예시: 중복 검사, 멤버십 테스트

// Set 생성 및 has() 예시
const s = new Set([1, 2, 3, 2]);
// 중복 제거되어 {1,2,3}
console.log(s.has(2)); // true, O(1)

 

• 맵(Map) / Dictionary
  • 키(key)-값(value) 쌍 저장, 조회·삽입·삭제 O(1)
  • 사용 예시: 캐싱, 빈도 카운팅

// Map 생성 및 get/set 예시
const map = new Map();
map.set('apple', 5);
map.set('banana', 3);
console.log(map.get('apple')); // 5, O(1)

• 스택(Stack)
  • LIFO(Last-In-First-Out) 
  • 연산 비용: push/pop 모두 O(1)
  • 사용 예시: 브라우저 뒤로가기, 재귀 호출 스택

// Stack 예시 (배열 사용)
const stack = [];
stack.push(1);  // [1]
stack.push(2);  // [1,2]
console.log(stack.pop()); // 2, O(1)

• 큐(Queue)

 

• FIFO(First-In-First-Out)
• 연산 비용: enqueue O(1), dequeue (배열 shift는 O(n)이나 링 버퍼 구현 시 O(1))
• 사용 예시: BFS, 작업 스케줄링

 

// 간단한 큐 구현 예시 (배열 shift)
const queue = [];
queue.push(1);  // [1]
queue.push(2);  // [1,2]
console.log(queue.shift()); // 1 (주의: shift는 O(n))

• 힙(Heap) / 우선순위 큐
  • 최대/최소값 빠르게 꺼낼 때 유리
  • 연산 비용:
    • peek(최댓값/최솟값): O(1)
    • insert, extract: O(log n)
  • 사용 예시: 실시간 최고 점수 유지, Dijkstra 알고리즘
• 이진 탐색 트리(Binary Search Tree)
  • 왼쪽 서브트리에 작은 값, 오른쪽 서브트리에 큰 값만 저장
  • 균형 잡힌 BST: 검색·삽입·삭제 모두 O(log n)
  • 사용 예시: 동적 정렬된 데이터 관리

 

 

 

 

추가적으로 공간복잡도에 대한 학습 예정

공간복잡도(Space Complexity)란?

각 DS가 추가로 사용하는 메모리(노드 포인터, 배열 크기 등)를 확인해야 합니다.
예: 연결 리스트는 노드마다 next 포인터를 저장 → Array보다 공간 오버헤드 존재.

 

---

 

2. 시간복잡도 종류 (Big O 표기법) => 코테는 최악비교를 

입력 크기 _n_이 커질 때, 연산 횟수가 어떻게 증가하는지 수학적으로 표현

 

 

• Big O: 최악의 경우 기준, 상수·계수 무시
• 최악/평균/최선 표기 차이
  • O-표기: 최악(Worst-case)
  • Θ(세타)표기: 평균(Average) 또는 정확하게 증가율을 표현
  • Ω(오메가)표기: 최선(Best-case)

 

O(1)	상수 시간 – 입력 크기 무관	배열 인덱스 접근, Set.has(), Map.get(), 스택 push/pop
O(log n)	로그 시간 – 입력을 반씩 줄여가며	이분 탐색, 균형 이진 탐색 트리 검색/삽입, 힙 삽입/삭제
O(n)	선형 시간 – 입력 비례	순차 탐색(배열 순회), 연결 리스트 탐색, BFS/DFS (정점+간선수)
O(n log n)	분할 정복·정렬 계열	퀵 정렬, 병합 정렬, 힙 정렬
O(n²)	이중 반복문 – 입력² 비례	버블/선택/삽입 정렬, 인접 행렬 순회, 중첩 for문 문제

 

추가적으로 최악/평균/최선 표기 차이(보통 코테는 최악 기준), 우선순위 큐 내부 동작(힙ify 등) 학습예정

 

---

 

3. 알고리즘(Algorithm)

자료구조 위에서 데이터를 처리하는 절차

 

• 자료를 탐색, 정렬, 그래프 순회 등으로 가공
• 문제 요구 사항(최단경로, 부분합, 회로검사 등)에 맞춘 절차 설계

 

분류 기법 용도

탐색(Search)	Linear Search Binary Search	배열·리스트 등에서 원하는 값 찾기
정렬(Sort)	Bubble, Selection, Insertion Quick, Merge, Heap Sort	데이터를 크기·순서대로 재배열
그리디(Greedy)	Interval Scheduling Coin Change	매 단계 최적 선택 후 전체 최적 달성
분할 정복(Divide&Conquer)	Merge Sort, Quick Sort, FFT	큰 문제를 작은 문제로 분할해 해결
동적 프로그래밍(DP)	Knapsack, LCS, DP 테이블 작성	중복 계산 제거, 최적 부분 구조
그래프 순회	DFS (재귀/스택) BFS (큐)	네트워크, 최단경로, 연결 요소 찾기
투 포인터 / 슬라이딩 윈도우	Two-pointer, Sliding Window	연속 부분합, 구간 최대/최소, 최적화

 

// 이분 탐색 (Binary Search) – O(log n)
function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;  // 찾으면 인덱스 반환
    if (arr[mid] < target) left = mid + 1;  // 오른쪽 절반 탐색
    else right = mid - 1;                   // 왼쪽 절반 탐색
  }
  return -1; // 못 찾으면 -1 반환
}

// 투 포인터 – 연속 부분합 예시 – O(n)
function maxContinuousSum(arr, k) {
  let sum = 0, max = -Infinity;
  // 초기 윈도우 합 계산
  for (let i = 0; i < k; i++) sum += arr[i];
  max = sum;
  // 슬라이딩 윈도우: 한 칸씩 이동하며 합 갱신
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];  // 새로 들어온 값 더하고, 빠진 값 빼기
    max = Math.max(max, sum);
  }
  return max;
}

// DFS (Depth-First Search) – 인접 리스트 기반 – O(n + m)
function dfs(graph, start) {
  const visited = new Set();
  function visit(node) {
    if (visited.has(node)) return;
    visited.add(node);
    for (const nei of graph[node]) {
      visit(nei);
    }
  }
  visit(start);
  return visited;
}

// DP (피보나치 예시) – O(n)
function fib(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

 

---

 

 

4. 자료구조·알고리즘·시간복잡도의 연관 관계 ( 문제 → 시간제한 → DS 선택 → 알고리즘 적용)

 

1. 문제 요구:
   • “데이터 검색만” vs “정렬 + 검색” vs “그래프 경로 찾기” 등
2. 시간제한 확인:
   • n 최대치 보고 O(n²) 불가 → O(n log n) 이하 선택
3. 자료구조 선택:
   • 검색이 잦으면 → Set/Map (O(1))
   • 정렬된 데이터 유지+검색 → BST or 정렬+이분탐색
   • 최단 경로 → 그래프 + BFS/DFS
4. 알고리즘 적용:
   • “부분합” → 투 포인터/슬라이딩 윈도우
   • “최댓값” → 힙 / 정렬 / DP

 

---

5. 코테에 접목하는 순서와 실전 꿀팁

 

 

1. 제약 조건부터 읽기
   • n 크기, 메모리, 시간 제한 파악 → 허용 O(?) 범위 예측
2. 핵심 연산 분류
   • 삽입·삭제·검색·정렬·탐색 등
3. 허용 시간복잡도 결정
   • n ≤ 10³ → O(n²) 가능
   • n ≤ 10⁵ → O(n log n) 권장
   • n ≤ 10⁶ 이상 → O(n) 필요
4. 자료구조 선택
   • 중복/멤버십 테스트 → Set/Map
   • 순차 탐색 → 배열/리스트
   • 최댓값 유지 → Heap
5. 알고리즘 기법 선택
   • “정렬” vs “탐색” vs “구간 문제” vs “경로 문제” vs “최적화 문제”
6. 템플릿화
   • 자주 쓰는 코드(이분 탐색, BFS/DFS, 투 포인터 등) 미리 구현해 두고 가져쓰기
7. 코드 작성 & 주석
   • 핵심 로직에 짧은 주석 추가 → 문제 의도·시간복잡도 표기
8. 테스트 케이스
   • 작은 입력, 최대 입력, 예외 입력 모두 검증
9. 시간복잡도 확인
   • “이 알고리즘 O(?)”를 면접관에게 자신있게 말할 수 있어야 함