-
LeetCode #77. Combinations(조합) 2가지 DFS로 풀어보자!
고민- 이미 사용된 숫자는 어떻게 제외하고, 다음 재귀 시 재활용할 것인가?위 고민에 사로잡혀, 맨처음엔 Queue를 활용하여 풀이 방법 2번으로 풀었다. 하지만 책에서 제안한 풀이법을 보니, 굳이 Queue를 통해 남아있는 숫자를 관리하지 않아도 되고, 단순한 반복을 통해 풀이할 수 있다는 것을 알 수 있었다. 풀이 방법 간의 속도 차이도 큰 편이었다.문제 설명1부터 ( n )까지의 정수에서 ( k ) 개의 숫자를 선택하여 가능한 모든 조합(combination)을 반환하라. 조합은 선택된 원소들의 순서를 고려하지 않는다.입력 및 출력 예시Example 1:Input: n = 4, k = 2Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]Example..
Java/Algorithm
2024. 8. 6.
-
LeetCode #46. Permutations(순열) DFS(백트래킹, 재귀)로 풀어보자!
문제 설명정수 배열 nums가 주어졌을 때, 가능한 모든 순열(permutation)을 반환하라. 순열은 원소들의 모든 가능한 순서를 의미한다.입력 및 출력 예시Example 1:Input: nums = [1, 2, 3]Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]Example 2:Input: nums = [0, 1]Output: [[0, 1], [1, 0]]Example 3:Input: nums = [1]Output: [[1]]제약사항1 -10 nums의 모든 원소는 고유하다.풀이 1: 백트래킹 (Backtracking) 사용시간 복잡도시간복잡도: O(n * n!) (n은 배열의 길이)T(n)=n!×(c1×n + ..
Java/Algorithm
2024. 8. 3.
-
LeetCode # 17. Letter Combinations of a Phone Number / DFS(재귀), BFS(Queue)를 이용해 풀어보자
17. 전화번호 문자 조합 (Letter Combinations of a Phone Number)문제 설명주어진 숫자(2-9)를 이용해 전화번호 버튼에 해당하는 모든 문자 조합을 반환하라. 결과는 어떤 순서로든 상관없다.입력 및 출력 예시Example 1:Input: digits = "23"Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]Example 2:Input: digits = ""Output: []Example 3:Input: digits = "2"Output: ["a","b","c"]제약사항0 digits[i]는 ['2', '9'] 범위 내의 숫자이다.문제 해석숫자 문자열 `digits`를 입력받는다.`digits`의 길이는 만들 수 있는 문자 조..
Java/Algorithm
2024. 8. 2.
