코딩테스트에서 반복적으로 저지르는 로직 실수를 모았다. 실수를 하고 나서야 깨닫는 것들이지만, 패턴을 알면 미리 피할 수 있다.
"최소 개수", "최소 비용"을 구하라는 문제를 보면 직관적으로 "가장 큰 것부터 선택"하는 그리디를 떠올리기 쉽다. 하지만 선택 간에 상호 간섭이 있으면 그리디는 통하지 않는다.
색종이 붙이기
10×10 종이 위에 1인 칸을 1~5 크기의 색종이(각 5장)로 모두 덮되, 최소 장수를 구하는 문제다.
1을 찾는다
→ 최대 크기 색종이를 붙인다
→ 다음 1을 찾는다
→ 반복
// 되돌리기 없는 탐욕for (int k = 5; k >= 1; k--) {
if (remaining[k] == 0) continue;
if (!canPlace(r, c, k)) continue;
place(r, c, k, 0);
remaining[k]--;
solve(r, c, count + 1); // 재귀
place(r, c, k, 1); // 복구
remaining[k]++;
}그리디와의 결정적 차이는 되돌리기(복구)가 있다는 것이다.
그리디 적용 전 체크: (1) 탐욕 선택이 항상 최적인가? (2) 선택 간 상호 간섭이 있는가? (3) 반례를 만들 수 있는가? — 2번에 해당하거나 3번이 가능하면 백트래킹이나 DP를 고려.
그리디로 풀 수 있는 문제를 DFS/BFS 등 완전탐색으로 접근하는 실수다. "모든 경우를 봐야 할 것 같다"는 직감이 먼저 오면 탐색부터 떠올리게 되는데, 그리디 조건을 먼저 점검하는 습관이 필요하다.
// DFS로 모든 주유 조합 탐색
// → N=100,000에서 경우의 수 폭발
dfs(city, fuel, cost)long minPrice = price[0];
for (int i = 0; i < n - 1; i++) {
minPrice = Math.min(minPrice, price[i]);
answer += distance[i] * minPrice;
}
// O(N) 한 번 순회로 해결왼쪽→오른쪽 일방통행이고, 각 도시의 최적 선택이 이후에 영향을 주지 않으므로 그리디가 성립한다.
되돌아갈 필요가 없는 구조(일방통행, 정렬된 순서)에서 각 단계의 최적 선택이 전체 최적을 보장하면 그리디다. 하나라도 "아니오"면 완전탐색이나 DP를 고려하자.
전수 비교가 필요한 문제에서, 정렬 후 break로 탐색을 조기 종료하려는 시도다. 비교 조건이 단일 기준이면 정렬 최적화가 통하지만, 두 조건을 동시에 만족해야 하는 경우에는 어떤 정렬 기준도 "이후는 볼 필요 없다"를 보장할 수 없다.
Arrays.sort(sorted, (a, b) ->
b[1] != a[1] ? b[1]-a[1] : b[0]-a[0]);
for (int j = 0; j < n; j++) {
if (sorted[j][0] > now[0]
&& sorted[j][1] > now[1])
c++;
else break; // 여기가 문제
}for (int j = 0; j < n; j++) {
if (peoples[j][0] > now[0]
&& peoples[j][1] > now[1])
c++;
// break 없이 전부 순회
}(45, 190) ← 키는 크지만 몸무게 작다 → 조건 실패 → break
(88, 188) ← 둘 다 크지만 break 때문에 못 봄정렬 후 break가 유효하려면, 정렬 기준이 비교 조건 전체를 포함해야 한다. 두 값을 모두 비교해야 하면 전수 순회가 필요하다.
% 연산자는 +보다 우선순위가 높다. a + b % c는 a + (b % c)로 계산된다. 원형 배열의 인덱스 계산에서 이걸 놓치면 완전히 다른 값이 나온다.
int newSushi = i + k % n;
// 실제로는 i + (k % n)
// k%n은 상수 → 매번 같은 오프셋int newSushi = (i + k) % n;
// i+k를 먼저 계산 후 n으로 나머지
// 인덱스가 n 넘으면 0으로 순환예시 (n=5, k=3):
| i | i + k % n (잘못) | (i + k) % n (올바름) |
|---|---|---|
| 0 | 3 | 3 |
| 1 | 4 | 4 |
| 2 | 5 (범위 초과) | 0 |
| 3 | 6 (범위 초과) | 1 |
원형 인덱스 공식: (현재 + 오프셋) % 전체크기. 반드시 덧셈을 괄호로 묶고 나머지 연산을 적용한다.
instanceof로 타입을 확인했다고 해서 자동으로 그 타입이 되는 게 아니다. 확인 후에도 변수는 여전히 원래 타입이며, 해당 타입의 필드나 메서드에 접근하려면 명시적 캐스팅이 필요하다.
public boolean equals(Object other) {
if (other instanceof Position)
return this.row == other.row
&& this.col == other.col;
// 컴파일 에러: Object에 row 없음
return false;
}public boolean equals(Object other) {
if (other instanceof Position) {
Position p = (Position) other;
return this.row == p.row
&& this.col == p.col;
}
return false;
}Java 16+에서는 패턴 매칭으로 한 줄에 처리할 수 있다:
if (other instanceof Position p)
return this.row == p.row && this.col == p.col;백준에서 Java 11을 쓴다면 패턴 매칭 instanceof는 불가. 명시적 캐스팅을 사용하자.