코테 문제 판단 기준

- 1초 제한시간에서 일반적으로:

* O(N): ~1억

* O(N²): ~1만

* O(N³): ~500

* O(N⁴): ~50 

 

입력 크기로 판단

N이 50 이하면:
- O(N⁴)도 괜찮음
- O(N³)은 거의 항상 가능
- O(N²)은 매우 여유로움

N이 1000 이하면:
- O(N²)까지는 괜찮음
- O(N³)은 위험

N이 100,000 이하면:
- O(N) 또는 O(NlogN) 정도만 가능

 

문제 유형으로 판단

완전탐색이 필요해 보이고:
- 입력크기가 매우 작으면(N≤50) → 브루트포스 가능성 높음
- 특별한 제약조건이나 패턴이 없으면 → 브루트포스 가능성 높음

 

최단 경로

- N ≤ 400: 플로이드-워셜 (O(N³))
- N ≤ 20,000, E ≤ 300,000: 다익스트라 (O(ElogV))
- 가중치가 1이거나 없음: BFS (O(V+E))

 

그래프 탐색

- N ≤ 100,000: DFS/BFS 기본 (O(V+E))
- 사이클 찾기: DFS
- 최단거리/최소횟수: BFS
- 경로 존재 여부: DFS/BFS

 

DP

- N ≤ 1,000,000: O(N) DP
- N ≤ 5,000: O(N²) DP
- 문제에 '최대/최소'가 들어감
- 부분문제가 겹침
- 이전 상태로 현재 상태 계산 가능

 

정렬

- N ≤ 1,000,000: O(NlogN) 정렬
- "순서대로", "연속된", "인접한" 키워드
- 특정 조건으로 정렬 후 처리

 

이진 탐색

- N ≤ 1,000,000: 이진탐색 (O(logN))
- "특정 값 찾기"
- "가능한 최대/최소값"
- 답이 특정 범위 안에 있음

 

그리디

- "최대/최소" + 단순한 규칙
- 부분선택이 전체 해에 영향X
- 정렬 후 순차처리 가능

 

투포인터

- "연속된 부분수열"
- "구간의 합"
- N ≤ 100,000 정도

 

완전탐색 (브루트포스)

- N ≤ 50: 모든 조합/순열
- N ≤ 10: 재귀로 모든 경우
- "모든 경우", "가능한 모든"
- 제약조건이 빡빡하지 않음

 

구현 / 시뮬레이션

- 보드게임/맵 조작
- "주어진 규칙대로"
- 복잡한 조건처리
- 예제 입출력이 매우 자세함

 

자료구조

- 스택: "괄호", "후위표기식"
- 큐: "순서대로 처리", "대기열"
- 우선순위큐: "가장 큰/작은 것 처리"
- 해시: "중복체크", "빠른 검색"

 

팁

• 먼저 입력크기 확인
• 문제에서 사용된 키워드 체크
• 시간제한 확인
• 예제 입출력 패턴 파악
• 비슷한 유형 떠올리기