고민
- 이미 사용된 숫자는 어떻게 제외하고, 다음 재귀 시 재활용할 것인가?
위 고민에 사로잡혀, 맨처음엔 Queue를 활용하여 풀이 방법 2번으로 풀었다. 하지만 책에서 제안한 풀이법을 보니, 굳이 Queue를 통해 남아있는 숫자를 관리하지 않아도 되고, 단순한 반복을 통해 풀이할 수 있다는 것을 알 수 있었다. 풀이 방법 간의 속도 차이도 큰 편이었다.
문제 설명
1부터 ( n )까지의 정수에서 ( k ) 개의 숫자를 선택하여 가능한 모든 조합(combination)을 반환하라. 조합은 선택된 원소들의 순서를 고려하지 않는다.
입력 및 출력 예시
Example 1:
Input: n = 4, k = 2
Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]Example 2:
Input: n = 3, k = 1
Output: [[1], [2], [3]]제약사항
- 1 <= n <= 20
- 1 <= k <= n
풀이 1: 백트래킹 (Backtracking) 사용
시간 복잡도
- 시간복잡도: O(k×C(n,k))
- 조합을 생성하기 위해 발생하는 k번의 재귀 호출
- 조합의 수 nCk
- Leetcode 16ms
핵심 아이디어
백트래킹을 통해 가능한 모든 숫자 조합을 탐색하고, 각 조합이 완성되면 결과 리스트에 추가하는 방식으로 구현합니다.
코드 구현
public class L_77_조합 {
public static void main(String[] args) {
L_77_조합 l77 = new L_77_조합();
int n = 4;
int k = 2;
System.out.println(l77.combine(n, k));
}
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> results = new ArrayList<>();
dfs(results, new ArrayList<>(), n, k, 1);
return results;
}
public void dfs(List<List<Integer>> results, List<Integer> elements, int n, int k, int start) {
// 조합은 순열과 달리 이미 선택한 원소와 다음에 선택할 수 있는 원소를 구분할 필요가 없음
// start 숫자를 +1씩 증가시켜 다음 숫자부터 반복할 수 있도록 함
// k를 -1씩 감소시켜 k개만큼의 숫자 조합이 완성됐음을 확인한다.
// 기저 조건: k가 0이 되면, 현재 조합을 결과 리스트에 추가
if (k == 0) {
results.add(new ArrayList<>(elements));
return;
}
// start부터 n까지의 숫자를 순서대로 선택하여 조합을 만든다
for (int i = start; i <= n; i++) {
elements.add(i); // 현재 숫자를 조합에 추가
dfs(results, elements, n, k - 1, i + 1); // 재귀적으로 다음 숫자 선택
elements.remove(elements.size() - 1); // 백트래킹: 마지막 숫자 제거
}
}
}설명
초기화:
results리스트는 모든 가능한 조합을 저장합니다.elements리스트는 현재까지 탐색한 조합을 저장합니다.start는 다음 숫자를 선택할 시작 인덱스입니다.
백트래킹 과정:
- 기저 조건:
k가 0이면elements는 완전한 조합이므로results에 추가합니다. - 숫자 선택:
start부터 ( n )까지의 숫자를 선택하고, 재귀적으로 탐색합니다. - 백트래킹: 재귀 호출 후에는
elements에서 마지막 숫자를 제거하여 다른 조합을 탐색할 수 있도록 합니다.
풀이 2: 깊이 우선 탐색 (DFS) 사용
시간 복잡도
- 시간복잡도: O(k×C(n,k))
- 조합을 생성하기 위해 발생하는 k번의 재귀 호출
- 조합의 수 nCk
- Leetcode 66ms
핵심 아이디어
Deque를 사용하여 남은 숫자들을 관리하며 DFS를 수행합니다.
코드 구현
public void dfs(List<List<Integer>> results, List<Integer> path, Deque<Integer> remains, int k, int n) {
// 경로의 길이가 k가 되면, 결과에 현재 경로를 추가
if (path.size() == k) {
results.add(new ArrayList<>(path));
return;
}
// 남은 숫자에서 선택하여 조합 생성
for (int i = 0; i < n; i++) {
// Queue를 사용하여 순서대로 남은 숫자들을 관리, DFS 수행
// remains에서 숫자를 poll하여 path에 추가하고, dfs를 호출
// remains에서 남은 숫자들을 계속 추출하고 새로운 덱을 생성하기 때문에, 메모리 사용량이 상대적으로 더 높고 수행 속도가 느림
if (remains.isEmpty()) return; // 남은 숫자가 없으면 종료
path.add(remains.poll()); // 남은 숫자에서 하나를 선택하여 경로에 추가
dfs(results, path, new ArrayDeque<>(remains), k, n); // 다음 단계 탐색
path.remove(path.size() - 1); // 탐색 완료 후 현재 숫자 제거
}
}설명
초기화:
results리스트는 가능한 모든 조합을 저장합니다.path리스트는 현재까지 탐색한 조합을 저장합니다.remains는 아직 선택되지 않은 숫자들이 들어있는 덱입니다.
DFS 과정:
path의 길이가 ( k )가 되면,results에 추가합니다.remains에서 숫자를 추출하여 조합을 구성하고, 새로운 덱을 생성하여 재귀 호출을 통해 탐색합니다.- 재귀 호출이 끝나면, 경로에서 마지막 숫자를 제거하여 다른 조합을 탐색할 수 있도록 합니다.
결론
두 방법 모두 문제를 풀이할 수 있었지만, 메모리 사용량을 줄이면서 최적화된 방법으로 정답에 접근하는 방향을 찾는 연습을 더 해야 할 것 같다.
<현재 공부 중인 알고리즘 도서>
댓글