복잡도&List/Stack/Queue/Deque

---

0) 복잡도 한눈표

주제	핵심 포인트
배열	인덱스 접근 O(1), 크기 고정, 중간 삽입/삭제 O(n)
선형 검색	정렬 불필요, 최선 O(1) · 최악 O(n)
이진 검색	정렬 필요, 최악 O(log n)
피보나치(재귀)	단순 재귀 O(2ⁿ) → 메모이제이션/반복으로 O(n) 권장
리스트	배열 기반: 접근 O(1) / 연결 리스트: 삽·삭제 O(1)(위치 알고 있을 때)
스택	LIFO, push/pop O(1)
큐	FIFO, offer/poll O(1), 원형 큐로 공간 재사용
덱	양끝 삽입/삭제 O(1)

---

1) 배열 (Array)

장점

• 구현 간단, 인덱스 접근 O(1), 메모리 연속 → 순차 접근 빠름

단점

• 크기 고정, 중간 삽입/삭제 O(n), 크기 여유분에 따른 메모리 낭비

---

2) 선형 검색 (Linear Search)

앞에서부터 차례로 비교

• 시간 복잡도: 최선 O(1) / 최악 O(n)
• 장점: 구현 매우 단순, 정렬 불필요
• 단점: 데이터가 클수록 느림

---

3) 이진 검색 (Binary Search)

정렬된 배열에서 중간값 기준으로 절반씩 버리기

• 시간 복잡도: 최선 O(1) / 최악 O(log n)
• 장점: 매우 빠른 검색(로그 증가)
• 단점: 정렬 필요, 선형 검색보다 구현 복잡

---

4) 피보나치 수열 (Fibonacci)

• 정의: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
• 특징: 재귀적 정의, 자연계 패턴에 다수 등장

---

5) 재귀 함수 (Recursive Function)

• Base Case(종료 조건) 필수
• Recursive Case(문제 분할)로 더 작은 문제 호출
• 장점: 표현 간결 / 단점: 호출 오버헤드, 깊은 재귀는 스택 오버플로우 위험

---

6) 재귀로 피보나치(Java)

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) return n;                 // Base Case
        return fibonacci(n - 1) + fibonacci(n - 2);  // Recursive Case
    }
    public static void main(String[] args) {
        int n = 10;
        System.out.println("F(" + n + ") = " + fibonacci(n));
    }
}

단순 재귀는 중복 계산으로 O(2ⁿ). 실무/코테는 DP(메모이제이션) 또는 반복문으로 O(n) 권장.

---

7) 자료구조 & ADT

자료구조: 데이터를 효율적으로 저장/관리하는 방법
ADT(추상 자료형): 데이터 + 연산의 규약만 정의, 구현은 감춤

---

8) 리스트 (List)

순서가 있는 집합, 인덱스/포인터로 접근

구현

• 배열 기반: 인덱스 접근 빠름, 크기 고정
• 연결 리스트: 노드(데이터+포인터), 동적 크기, 포인터 변경으로 삽입/삭제 유리

연산(예)

add(i,x), remove(i), get(i), set(i,x), indexOf(x), size(), isEmpty(), clear()

복잡도 정리

구현	접근	삽입	삭제	공간
배열 기반	O(1)	O(n)	O(n)	O(n)
연결 리스트	O(n)	O(1)*	O(1)*	O(n)
* 삽입/삭제 위치의 노드를 이미 알고 있다면 O(1); 위치 탐색까지 포함하면 O(n)

---

9) 스택 (Stack)

LIFO, 함수 호출 스택/수식 평가

연산

push, pop, peek, isEmpty, size, clear, search

복잡도

구현	접근	push	pop	공간
배열/연결리스트	O(1) (top)	O(1)	O(1)	O(n)

---

10) 큐 (Queue)

FIFO, 작업 스케줄링/스트림 처리

구현

• 배열 큐: front/rear 인덱스
• 원형 큐: 인덱스가 끝에 가면 처음으로 순환, 공간 재사용
• 연결 리스트 큐: 동적 크기, 제한 없음

연산

offer, poll, peek, isEmpty, size, clear

복잡도

구현	접근	삽입(offer)	삭제(poll)	공간
배열 큐	O(1)	O(1)	O(1)	O(n)
원형 큐	O(1)	O(1)	O(1)	O(n) (공간 재사용)
연결 리스트	O(1)	O(1)	O(1)	O(n)

---

11) 덱 (Deque)

양쪽 끝에서 삽입/삭제 가능한 큐

구현

• 배열 기반(순환), 이중 연결 리스트

연산

addFirst/Last, offerFirst/Last,
removeFirst/Last, pollFirst/Last,
getFirst/Last, peekFirst/Last, isEmpty, size, clear

복잡도

구현	접근	앞/뒤 삽입	앞/뒤 삭제	공간
배열(순환)	O(1)	O(1)	O(1)	O(n)
이중 연결 리스트	O(1)	O(1)	O(1)	O(n)

---

핵심 요약

• 검색: 정렬X → 선형 / 정렬O → 이진
• 삽입·삭제 많음: 연결 리스트/덱/큐
• 함수 호출/되돌리기: 스택
• 재귀: Base Case 명확히 + 깊으면 반복/DP로 전환