[알고리즘]문제 유형별 알고리즘 선택 기준

풀이의 우선순위는 문제를 봤을 때 어떤 자료구조와 어떤 알고리즘을 사용해야 하는지 판단 할 수 있어야한다.

 

문제의 특성을 확인하고 어떤 자료구조와 알고리즘을 선택할지 파악하자.

 

 

1. 문제를 읽고 핵심 요구 사항 파악하기

 

먼저 문제의 본질을 이해하는것이 중요함.

 

 

• 입력 크기: 데이터가 크면 시간 복잡도를 고려해야 함.
• 실시간 처리가 필요한가? → 효율적인 자료구조 필요.
• 순차적으로 처리하는가? → 배열 or 리스트가 적합.
• 검색이 중요한가? → 해시맵, 이진 탐색 트리(BST) 고려.
• 최대/최소 값이 중요한가? → 힙(Heap) 사용.
• 경로 탐색이 필요한가? → 그래프 알고리즘 DFS, BFS 필요

 

2. 문제 유형별로 적절한 자료구조 및 알고리즘 판단

 

(1) 정렬이 필요한가?

• 정렬 후 특정 조건을 만족하는 요소 찾기 → 정렬 알고리즘 (퀵 정렬, 병합 정렬)
• 데이터가 많고 매번 정렬이 필요한가? → 힙(Heap) 사용 (우선순위 큐)
• 고유한 값 개수 세기 → 정렬 + 투 포인터 또는 해시셋 사용 

* 고유한 값 개수 세기 유형 문제란?

배열 내에 중복되는 수를 제거한 후 고유 한 숫자의 개수를 찾는 방법
-> Hash 사용 (unorderded_set 사용)

해시셋(unorderded_set)은 삽입/검색이 O(1)으로 매우 빠름.

 

(2) 탐색이 필요한가?

• 빠른 탐색이 중요 → 이진 탐색 (Binary Search)
• 연속된 데이터에서 특정 값 탐색 → 슬라이딩 윈도우
• 그래프에서 탐색 필요 → DFS, BFS

* 슬라이딩 윈도우란?
 
슬라이딩 윈도우는 고정된 길이 혹은 유동적인 길이의 범위에서 계산하는 기법.
투포인터와 유사하지만, 범위를 확장/축소하며 최적의 결과를 찾는 방식.

 

(3) 데이터 추가/삭제가 자주 발생하는가?

• 정렬된 데이터 유지하며 삽입/삭제 → 이진 탐색 트리(BST) or 힙(Heap)
• 가장 최근 데이터를 빠르게 가져와야 함 → 스택(Stack), 큐(Queue), 덱(Deque)
• 우선순위가 있는 데이터 처리 → 우선순위 큐 (Priority Queue, Heap)

* 각 자료구조 별 반복자(iterator) 및 내부 인덱스 접근 가능 여부

자료구조	반복자 지원	인덱스 접근
vector	✅ O(1)	✅ O(1)
deque	✅ O(1)	✅ O(1)
list(링크드리스트)	✅ O(N)	❌
set / unordered_set	✅ O(log N) / O(1)	❌
map / unordered_map	✅ O(log N) / O(1)	❌

 

(4) 문자열 관련 문제인가?

• 패턴 찾기 → KMP, 라빈 카프 알고리즘
• 중복된 문자를 빠르게 찾기 → 해시셋(HashSet)
• 사전순 정렬 → Trie(트라이)

 

(5) 부분합, 누적합, 최적화가 필요한가?

• 배열에서 구간합을 자주 계산 → 누적합(Prefix Sum), 세그먼트 트리
• 최소 비용을 구해야 한다 → 다익스트라 (Dijkstra), 플로이드-워셜 (Floyd-Warshall)

 

3. 입력 크기에 따른 알고리즘 선택

 

문제에서 주어진 입력 크기(N)을 보고 적절한 알고리즘을 선택해야 함.

 

시간 복잡도에 따른 선택 기준

입력 크기(N)	적절한 알고리즘
𝑁 ≤ 10	완전 탐색 (브루트포스) 가능
𝑁 ≤ 100	백트래킹, DP 가능
𝑁 ≤ 10,000	O(𝑁 log 𝑁) 가능 (정렬, 이진 탐색)
𝑁 ≤ 1,000,000	O(𝑁) 이하 가능 (해시, 투 포인터, 슬라이딩 윈도우)
𝑁 > 10,000,000	O(log 𝑁) 이하 알고리즘 필수 (이진 탐색, 세그먼트 트리, 해시)