문제 설명에 나온 표현으로 어떤 자료구조/알고리즘을 써야 할지 빠르게 찾는 표. 각 항목의 자세한 코드는 해당 개념 article 참고.
해시
| 신호 | 패턴 |
|---|
| “각 원소가 몇 번 나오는지”, “가장 많이 등장한 것” | 빈도수 세기 |
| “두 배열을 비교해서 빠진 것/다른 것 찾기” (중복 없는 원소) | 집합(set) 차집합 |
| “두 배열을 비교해서 빠진 것/다른 것 찾기” (중복 가능한 원소) | 빈도수 맵 비교 (집합 차집합은 개수 차이를 구분 못 함, 예: [A,A,B]와 [A,B]) |
| “이미 나온 적 있는지”, “중복 확인” | 존재 여부 체크 |
정렬
| 신호 | 패턴 |
|---|
| “정렬했을 때 순서가 특이한 기준” (숫자 크기 아닌 문자열 합친 결과 등) | 커스텀 comparator |
| “여러 조건 중 1순위, 2순위가 있다” | 다중 조건 정렬 |
| “정렬한 다음 앞뒤에서 좁혀나간다” | 정렬 + 투 포인터 |
| “정렬한 다음 누적값으로 위치를 찾는다” | 정렬 + 이분탐색/누적합 |
그래프
입력 형태
| 입력이 이렇게 주어지면 | 신호 키워드 | 쓸 자료구조 |
|---|
n(노드 개수) + edges(간선 리스트) | “간선”, “연결 정보” | 인접리스트로 변환 |
n x n 관계 행렬 | “컴퓨터가 연결되어 있으면 1”, “네트워크” | 인접행렬 or 인접리스트 |
| 2차원 격자(지도/미로) | “맵”, “게임판”, “이동”, “벽” | 격자 자체를 그래프로 사용 |
질문 형태
| 질문 | 알고리즘 |
|---|
| “최단거리”, “최소 이동 횟수” (간선 비용이 전부 같거나 가중치 없음) | BFS |
| “최단거리” (간선마다 비용이 다름, 가중치 있음) | BFS로는 부족 — 다익스트라 등 별도 알고리즘 필요 |
| “도달 가능한가” (여부만) | DFS or BFS |
| “연결된 그룹/네트워크 개수” | 전체 순회 + DFS/BFS |
| “모든 경로”, “몇 가지 방법” | DFS (백트래킹). 단, 그래프에 사이클이 있으면 “모든 경로”가 무한할 수 있어 별도 처리 필요. 격자/DAG에서 “경로의 수”를 구하는 문제는 DP가 더 적합한 경우가 많다 |
완전탐색
n 범위로 순열/조합/비트마스킹 같은 “탐색 공간 자체가 n에 지수적으로 커지는” 완전탐색이 가능한지 먼저 확인
| n의 범위 | 가능한 방식 |
|---|
| n ≤ 10 | 순열(10! ≈ 360만) |
| n ≤ 20 | 비트마스킹(2^20 ≈ 100만) |
| n이 매우 큼 (수십만~백만 이상) | 순열/조합/비트마스킹 같은 지수적 완전탐색은 불가. 다만 원소를 한 번씩만 훑는 O(n)/O(n log n) 단순 순회는 n과 무관하게 여전히 가능 — “완전탐색이 불가능하다”는 건 “모든 경우의 수를 다 만들어보는 방식”이 불가능하다는 뜻이지, 모든 순회 자체가 불가능하다는 뜻이 아니다 |
신호
| 신호 | 방법 |
|---|
| “순서를 바꿔서 만들 수 있는 모든 경우” | 순열 (next_permutation) |
| “순서 상관없이 몇 개를 뽑는 모든 경우” | 조합 |
| “선택하거나 안 하거나” 반복 | 비트마스킹 or 재귀(백트래킹) |
| “조건 만족 시 더 진행 안 해도 됨” | 백트래킹 (가지치기) |
스택/큐
| 신호 | 자료구조 |
|---|
| “짝을 맞춰야 한다” (괄호, 태그 등) | 스택 |
| “가장 최근 것과 비교/제거” | 스택 |
| “순서대로 처리해야 한다” (대기열, 시뮬레이션) | 큐 |
| “일정 시간/순서마다 앞에서부터 하나씩 처리” | 큐 |
힙
| 신호 | 판단 |
|---|
| “가장 큰/작은 것을 K개 뽑아라” | 힙 |
| “값을 계속 추가하면서 그때그때 최댓값/최솟값 필요” | 힙 |
| “두 개를 합쳐서 다시 넣는 걸 반복” | 힙 |
| 그냥 한 번 정렬해서 끝 | 정렬로 충분, 힙 불필요 |
이분탐색
| 신호 | 패턴 |
|---|
| “정렬된 배열에서 특정 값의 위치” | 일반 이분탐색 |
| “최소/최대 얼마로 설정해야 조건을 만족하나” (판정 함수가 단조롭게 변함) | 파라메트릭 서치 |
| ”~ 이상/이하로 자르면 몇 개가 나오나” (조건이 단조롭게 변함) | 파라메트릭 서치 |
파라메트릭 서치는 “최솟값/최댓값을 찾는 문제”라는 것만으로는 적용할 수 없다. 후보 답에 대해 “이 값으로 조건을 만족하는가”를 판정하는 함수가 단조적이어야 하고(예: 어떤 값 이상에서는 항상 만족, 이하에서는 항상 불만족), 탐색할 답의 범위(최소~최대)도 정의할 수 있어야 한다.
그리디
| 신호 | 그리디 기준 |
|---|
| “최소 개수로 나눠라” (그리디 정당화가 가능한 동전 체계, 예: 1/5/10/50/100…) | 큰 단위부터 채운다 |
| “겹치는 구간을 최대한 안 겹치게 골라라” | 끝나는 시간이 빠른 것부터 |
| “분할 가능한 자원을 정해진 용량에 배분” (물건을 쪼갤 수 있음) | 비율(가치/비용) 좋은 것부터 |
| “순서를 정해서 총 대기시간/비용 최소화” | 짧은/작은 것부터 처리 |
주의: 그리디는 “그 순간 최선의 선택이 전체 최적해로 이어진다”는 게 증명될 때만 쓴다. 동전 단위가 예를 들어 [1, 3, 4]처럼 배수 관계가 아니면 큰 단위부터 채우는 그리디가 실패할 수 있다(6을 만들 때 그리디는 4+1+1을 고르지만 최적은 3+3). 반대로 배수 관계가 아니라고 그리디가 항상 실패하는 것도 아니다 — 문제별로 정당화가 되는지 확인해야 한다. 또한 물건을 쪼갤 수 없는 0/1 배낭 문제는 “쪼갤 수 없다”는 이유만으로 무조건 DP가 정답은 아니고, 그리디의 교환 논리가 성립하는지 또는 문제의 최적 부분 구조를 먼저 확인해야 한다.
DP
| 신호 | 접근 |
|---|
| “n번째 값이 이전 몇 개 값으로 결정됨” (피보나치류) | 1차원 DP |
| “경로의 수를 구해라” (격자 이동 등) | 2차원 DP |
| “최댓값이 되도록 선택해라” + 그리디 안 통함 | DP (선택/비선택 2경우 저장) |
| “두 문자열/배열 비교해서 공통된 것 찾기” | 2차원 DP (LCS류) |
DP 판단 신호: “그리디가 안 통한다”는 이유만으로 DP를 쓰는 건 아니다. DP는 일반적으로 (1) 같은 하위 문제가 반복해서 나오고(중복 부분 문제), (2) 부분 문제의 최적해를 조합하면 전체 최적해가 된다는(최적 부분 구조) 두 조건이 있을 때 후보가 된다. 완전탐색(재귀)으로 풀었을 때 같은 입력으로 함수가 여러 번 호출된다면 메모이제이션(DP 전환)을 검토할 신호이지만, 실제로 DP로 풀려면 상태를 어떻게 정의할지와 점화식을 별도로 세워야 한다.