코딩 테스트를 준비하면서 가장 헷갈렸던 지점 중 하나는
“이 문제를 DFS로 풀어야 하는지, 아니면 combinations 같은 라이브러리를 써도 되는지”였다.
특히 BOJ 14889 (스타트와 링크) 문제를 풀면서 이 고민이 명확해졌다.
1. 처음 접근: 문제를 어떻게 해석했는가
문제를 처음 보면 핵심은 두 가지다.
- N명 중 N/2명을 선택해서 두 팀으로 나눈다
- 각 팀의 능력치를 계산해서 차이의 최솟값을 구한다
여기서 중요한 포인트는 “선택”이다.
N명 중 절반을 뽑는 순간, 이 문제는 자연스럽게 조합 문제로 바뀐다.
2. 막혔던 지점: 선택 이후의 계산
절반을 뽑는 것까지는 이해가 되는데,
그 다음 “능력치를 어떻게 계산해야 하는지”에서 막혔다.
정리해보면 규칙은 이렇다.
- 한 팀이 주어지면, 그 팀 내부에서 2명씩 묶는다
- 각 쌍 (i, j)에 대해
s[i][j] + s[j][i]를 더한다 - 두 팀의 점수 차이를 절댓값으로 계산한다
즉, 이 문제는 단순히 팀을 나누는 게 아니라
“팀 내부 모든 조합을 다시 한 번 순회하는 문제”다.
3. combinations로 푸는 방식
가장 직관적인 풀이는 다음과 같다.
- N명 중 N/2명을 combinations로 선택
- 나머지를 링크 팀으로 구성
- 두 팀 각각에 대해 내부 2명 조합을 만들어 점수 계산
이 방식의 장점은 명확하다.
- 코드가 짧다
- 구조가 직관적이다
- 실수할 확률이 낮다
즉, 이 문제만 놓고 보면 combinations가 훨씬 편하다.
4. 그런데 왜 DFS를 고민하게 되었는가
문제를 풀다 보니 자연스럽게 이런 의문이 생겼다.
“이거 DFS 문제 아닌가?”
실제로 문제의 본질은 다음과 같다.
- 사람을 한 명씩 선택한다
- 팀이 완성되면 계산한다
이 구조는 전형적인 DFS(백트래킹) 구조다.
5. DFS로 다시 보면 구조가 보인다
DFS로 보면 문제는 이렇게 바뀐다.
- visited 배열로 팀 선택 상태를 관리
- depth가 N/2가 되면 팀 완성
- 그때 점수 계산
즉,
- combinations는 “완성된 결과를 가져오는 방식”
- DFS는 “결과를 만들어가는 방식”
이라는 차이가 있다.
6. combinations와 DFS의 본질적인 차이
이 부분이 가장 중요했다.
combinations
- 이미 완성된 조합을 제공
- 우리는 결과만 계산하면 됨
- 중간 과정에 개입할 수 없음
DFS
- 조합을 직접 생성
- 선택 과정 자체를 제어 가능
- 중간에 조건을 검사하고 멈출 수 있음
7. 언제 combinations를 써도 되는가
문제를 여러 개 풀다 보니 기준이 생겼다.
다음 조건을 만족하면 combinations를 써도 된다.
- 어차피 모든 경우를 다 봐야 한다
- 중간에 가지치기가 필요 없다
- 선택 과정에서 조건 검사가 없다
대표적인 예:
- 스타트와 링크 (14889)
- 치킨 배달 (15686)
- 로또 (6603)
이런 문제들은 “완전탐색 + 계산” 구조라서
combinations로 충분하다.
8. 언제 DFS가 필요한가
반대로 DFS가 반드시 필요한 경우도 있다.
- 선택 도중에 조건이 붙는 경우
- 예: 특정 조합 금지, 예산 제한
- 상태가 계속 변하는 경우
- 방문 여부, 누적 값 등
- 가지치기가 필요한 경우
이 경우에는 combinations로는 비효율적이거나
구현 자체가 어려워진다.
9. 결국 정리된 기준
문제를 풀 때 이렇게 판단하면 된다.
- 이 문제는 모든 경우를 끝까지 다 봐야 하는가?
- 그렇다면 combinations
- 선택하는 도중에 판단이 필요한가?
- 그렇다면 DFS
10. 스타트와 링크를 다시 보면
이 문제는 이렇게 정리할 수 있다.
- 본질: N명 중 절반을 뽑는 조합 문제 → DFS
- 구현: 팀 내부 점수 계산 → 구현
즉,
DFS(조합 생성) + 구현(점수 계산)
문제다.
마무리
처음에는 combinations를 쓰는 게 “편법”처럼 느껴졌는데,
지금은 오히려 이렇게 생각이 정리됐다.
- combinations는 빠르게 풀기 위한 도구
- DFS는 문제를 확장해서 풀기 위한 능력
결국 중요한 건 라이브러리가 아니라
문제에서 “선택 구조”를 읽어내는 능력
이라는 걸 느꼈다.
앞으로는 문제를 보면 먼저
“이걸 끝까지 다 볼 건지, 중간에 잘라야 하는지”부터 판단하려고 한다.
'프로그래밍 > 코딩 테스트, 더 이상 미룰 수 없다' 카테고리의 다른 글
| [코딩테스트, 더 이상 미룰 수 없다] BOJ 14501 - 코드를 외워둘 만한 대표적 DP 문제 (0) | 2026.03.31 |
|---|---|
| [코딩테스트, 더 이상 미룰 수 없다] BOJ 14502 연구소 - 구현을 감 잡아보zㅏ (0) | 2026.03.30 |
| [코딩 테스트, 더 이상 미룰 수 없다] 구현 문제 가이드 (0) | 2026.03.19 |
| [코딩테스트, 더 이상 미룰 수 없다] BOJ 2468 - DFS를 도구로 바라보기 (0) | 2026.03.19 |
| [코딩테스트, 더 이상 미룰 수 없다] BOJ 11053 - Dynamic Programming (DP) (0) | 2026.03.18 |