TIL 2026-02-26

2/26 - 코딩테스트 강의 (이론 복습)

생성일: 2026년 2월 26일 오후 12:47

2-4 STL 사용하기

1. STL 구조 및 설계 원칙

• STL 구성요소: 컨테이너 + 반복자 + 알고리즘

  → 알고리즘과 컨테이너의 분리 설계가 핵심 (유연한 재사용)

• 템플릿 기반(Generic Programming)

  → 자료형 독립적 코드 작성 가능 (int, string, custom class 등)

• 코테 관점에서 중요한 점

  → 자료구조 선택 = 시간복잡도 설계의 시작

---

2. vector (동적 배열) – 코테 핵심 1순위

연산	시간복잡도	유의점
push_back()	O(1) (평균)	capacity 초과 시 O(N)
insert() (중간)	O(N)	원소 밀림 발생
clear()	O(N)	전체 삭제
[] 접근	O(1)	인덱스 기반 접근 가능

핵심 메서드

• push_back()
• insert(pos, value)
• reserve(n) → 재할당 방지
• size(), capacity()
• clear()

예시코드

vector<int>v;
v.reserve(100000);// 대량 입력 대비
v.push_back(1);
v[0] =10;

코테 유의점

• 입력 개수 예측 가능 → reserve 필수
• 중간 삽입 많으면 → deque 고려
• 인덱스 접근 필요하면 → vector가 최적

---

3. set – 정렬 + 중복 제거

특징	설명
내부 구조	Red-Black Tree
삽입/삭제	O(logN)
중복	불가
정렬	자동 오름차순

핵심 메서드

• insert()
• erase()
• find()
• clear()

예시코드

set<int>s;
s.insert(3);
s.erase(3);

코테 유의점

• 자동 정렬 → 별도 sort 불필요
• 중복 허용 필요 → multiset
• 정렬 필요 없고 탐색만 중요 → unordered_set
• 인덱스 접근 불가

---

4. map – Key-Value 자료구조

연산	시간복잡도
삽입	O(logN)
삭제	O(logN)
탐색	O(logN)
반복자 삭제	평균 O(1)

핵심 메서드

• m[key]
• m.at(key)
• insert()
• erase()
• find()

예시코드

map<string,int>m;
m["A"] =1;// 없으면 생성
m.at("A") =2;// 없으면 예외
m.erase("A");

코테 유의점

• []는 자동 생성 → 실수로 값 추가될 수 있음
• 존재 확인 → find() 사용 권장
• 단순 키 집합이면 → set 사용
• 키는 명확한 타입 (float 지양)

---

5. 반복자 (Iterator)

• begin(), end()
• rbegin(), rend()
• 알고리즘은 반복자를 통해 작동

예시코드

for(autoit =v.begin();it!=v.end();++it)
cout<< *it;

코테 포인트

• erase 후 반복자 무효화 주의
• range-based for가 간결하고 안전

---

6. 알고리즘 (algorithm 헤더)

자주 쓰는 함수

함수	설명
sort()	정렬
find()	탐색
count()	개수
unique()	중복 제거 (정렬 후 사용)

예시코드

sort(v.begin(),v.end());
autoit =find(v.begin(),v.end(),5);

코테 유의점

• unique는 정렬 후 사용
• 사용자 정의 정렬 → lambda 활용

sort(v.begin(),v.end(), [](inta,intb){
returna>b;
});

---

7. 코테 실전 선택 기준 정리

상황	추천 컨테이너
인덱스 접근	vector
정렬 + 중복 제거	set
키-값 저장	map
빠른 탐색만 필요	unordered_map
삽입/삭제 많음	deque

---

핵심 정리

• 자료구조 선택 = 시간복잡도 설계
• vector는 기본, set/map은 logN
• reserve()는 대량 입력 문제 필수
• [] vs at() 차이 숙지
• 자동 정렬 특성 이해해야 실수 방지

---

2-5 알고리즘 효율성 (코딩테스트 관점 정리)

컨테이너 선택 기준 (시간복잡도 중심)

| 컨테이너 | 삽입 | 탐색 | 특징 | 사용 상황 | | — | — | — | — | — | | vector | O(1) (뒤) / O(N) (앞) | O(N) | 연속 메모리 | 임의접근 많을 때 | | deque | O(1) (앞/뒤) | O(1)* | 청크 구조 | 앞 삽입 많을 때 | | map | O(logN) | O(logN) | Red-Black Tree | 정렬 필요 시 | | unordered_map | O(1) 평균 | O(1) 평균 | 해시 | 정렬 불필요 + 빠른 탐색 |

• 실제 체감 성능은 vector가 더 빠름

---

vector vs deque

• vector.insert(begin(), x) → O(N) (전체 이동 발생)
• deque.push_front(x) → O(1)
• 임의접근은 둘 다 O(1)이지만 캐시 효율은 vector 우세
• 코테에서 앞 삽입 많으면 deque, 그 외엔 vector

코드 요약:

vec.insert(vec.begin(),x);// O(N)
deq.push_front(x);// O(1)

유의점:

• vector는 앞 삽입 절대 지양
• 대량 push_back 시 reserve() 필수

---

map vs unordered_map

• map: 내부 정렬 → O(logN)
• unordered_map: 해시 → O(1) 평균
• 정렬 필요 없으면 unordered_map 선택

코드 요약:

map<int,int>m;// O(logN)
unordered_map<int,int>um;// O(1) avg

유의점:

• unordered_map은 해시 충돌 시 O(N)
• 키 범위 작으면 vector로 치환 고려

---

탐색 성능 비교

• vector + find → O(N)
• map.find() → O(logN)
• unordered_map.find() → O(1)

코드 요약:

find(vec.begin(),vec.end(),x);// O(N)
m.find(x);// O(logN)
um.find(x);// O(1)

유의점:

• 빈번 탐색 문제는 vector 절대 금물
• 데이터 크기 10^5 이상이면 해시 고려

---

문자열 결합 성능

방식	시간복잡도	특징
s = s + x	O(N)	매번 새 객체 생성
s += x	O(1) amortized	제자리 수정
append()	O(1) amortized	내부 버퍼 사용

코드 요약:

s+=x;// 추천
s.append(x);// 추천
s =s+x;// 지양

유의점:

• 반복 결합 시 + 사용하면 시간초과 위험

---

auto vs auto& (복사 비용)

• for(auto x : vec) → 복사 발생
• for(auto& x : vec) → 참조 (복사 없음)
• 큰 구조체일수록 차이 극심

코드 요약:

for(auto&x :vec) { }// 권장

유의점:

• 수정 안 하면 const auto& 사용
• range loop 기본은 참조로 습관화

---

정렬이 필요 없는 정렬 사용 금지

• map은 삽입할 때마다 정렬 유지 → O(logN)
• 단순 카운팅 문제는 unordered_map 사용
• 키 범위 작으면 배열 사용 (최적)

---

코테에서의 핵심 전략

• 앞 삽입 많다 → deque
• 임의접근 많다 → vector
• 빠른 탐색 필요 → unordered_map
• 정렬 필요 → map
• 문자열 반복 결합 → +=
• 반복문은 auto& 기본값

---

강의 3-1 재귀함수

---

재귀 설계 핵심 구조 (Base + Recursive Step)

| 구성 | 목적 | 실수 시 문제 | | — | — | — | | 기저 조건 | 종료 보장 | 무한 재귀 | | 재귀 단계 | 문제 축소 | 호출 깊이 과다 |

• 재귀는 문제 크기 감소 설계가 핵심
• 반드시 기저 조건 먼저 설계
• 시간복잡도는 호출 트리 구조로 판단

코드 요약:

if (n==0)return1;
return n*f(n-1);

---

재귀 호출과 스택 메모리 (Stack Frame)

• 호출마다 스택 프레임 생성
• 깊이 = 호출 깊이
• 공간복잡도: O(depth)

유의점:

• 깊이 N이면 공간 O(N)
• 10^5 이상 깊이는 위험
• 반복문 전환 고려

---

단순 재귀 vs 메모이제이션

방식	시간복잡도	특징
피보나치 단순 재귀	O(2^N)	중복 호출
메모이제이션	O(N)	결과 저장

문제점:

• fibo(n-1) + fibo(n-2) → 중복 계산
• 호출 수 지수 증가

코드 요약:

if (memo[n]!=-1)return memo[n];
memo[n] =f(n-1)+f(n-2);

유의점:

• DP로 전환 가능
• 배열 초기화 필수

---

DFS: 재귀 vs 반복 (Stack 사용)

| 구현 | 시간 | 공간 | | — | — | — | | 재귀 DFS | O(V+E) | O(depth) | | stack DFS | O(V+E) | O(V) |

• 재귀는 암묵적 스택 사용
• 반복은 명시적 stack 사용

코드 요약:

voidDFS(intnode){
visited[node] =true;
for(autonext :graph[node])
if(!visited[next])DFS(next);
}

유의점:

• visited 처리 순서 중요
  • 그래프 깊이 크면 반복 권장

---

지수 연산 최적화 (분할 정복)

방식	시간복잡도
단순 재귀 pow	O(N)
분할 정복 pow	O(logN)

핵심 아이디어:

• N 짝수 → pow(X,N) = pow(X,N/2)^2
• 문제 크기 절반 감소

코드 요약:

doublehalf =pow(x,n/2);
return (n%2==0)?half*half :half*half*x;

유의점:

• 반드시 N==0 기저조건
• long long 오버플로우 주의

---

재귀 사용이 효율적인 경우

• 분할 정복 (병합정렬, 퀵정렬)
• 트리/그래프 탐색
• 구조가 자연스럽게 분기될 때

비효율적 경우:

• 단순 반복 누적 문제
• 깊이 큰 선형 구조

---

시간복잡도 판단 기준 (코테 기준)

• 호출 1개씩 감소 → O(N)
• 호출 2개씩 분기 → O(2^N)
• 크기 절반 감소 → O(logN)

예시:

• fibo 단순 → O(2^N)
• pow 분할 → O(logN)
• DFS → O(V+E)

---

실전 코테 전략

• 깊이 최대치 계산 먼저
• 중복 호출 여부 확인
• 메모이제이션 가능 여부 판단
• 스택 초과 가능성 점검
• 가능하면 반복문 전환 고려

---