본문 바로가기
반응형

BackTracking10

[Leetcode] 437. Path Sum III 문제 : https://leetcode.com/problems/path-sum-iii/ 이진 트리와 targetSum이 주어지면 경로의 노드들 값의 합이 targetSum과 같은 경로들의 수를 구하라. 백트래킹. 트리를 탐색하면서 탐색한 노드들의 val의 합의 개수를 map에 저장한다. 탐색하면서 이때까지의 합(sum)에서 targetSum을 뺀 값의 개수들의 합이 정답이 된다. [그림 1]에서는 테이블들의 빨간색 셸들이 이에 해당하여 정답은 3이 된다. 시간복잡도는 O(N). N = 노드 수 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/437.%20Path%20Sum%20III.cpp 2021. 10. 18.
[leetcode] 113. Path Sum II 문제 : https://leetcode.com/problems/path-sum-ii/ 정수로 이루어진 이진트리와 targetSum이 주어질때, 루트에서 리프노드까지 경로의 노드들의 합이 targetSum과 같은 경로들을 구하여라. 백트래킹으로 경로들을 저장하면서 루트에서 리프노드에 도달할 때까지의 경로들의 합을 구한다. 리프노드에 도달했을때 합이 targetSum인 경우 정답 배열에 저장한다. 시간복잡도는 O(N). N = 트리의 노드 개수 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/113.%20Path%20Sum%20II.cpp 2021. 8. 4.
[leetcode] 90. Subsets II 문제 : https://leetcode.com/problems/subsets-ii/ 중복이 발생할 수 있는 정수형 배열 nums가 주어질때, 만들 수 있는 부분집합들을 구하여라. 동일한 정수들로 구성된 부분집합들은 중복으로 구하지 않는다. 백트래킹으로 탐색하면서 부분집합을 만든다. /* * nums : 입력 정수형 배열 * ind : 탐색 중인 인덱스 * subset : 이때까지 만든 부분집합 * * nums[ind~] 탐색하면서 subset에 정수를 추가하여 정답 부분집합을 만드는 함수 */ void backtracking(int[] nums, int ind, vector& subset) { 정답에 subset 추가. 만약 ind 인덱스가 nums 배열 인덱스 범위를 넘어가면 함수 종료. for(int.. 2021. 8. 3.
[leetcode] 639. Decode Ways II 문제 : https://leetcode.com/problems/decode-ways-ii/ A ~ Z 문자가 1 ~ 26 숫자로 인코딩된다.(01, 02 는 1, 2와 다르다.) 숫자와 * 문자로 이루어진 문자열이 주어진다. * 문자는 0을 제외한 1~9로 대체할 수 있다. 입력 문자열을 디코딩하였을 때 만들 수 있는 문자열들의 경우의 수를 구해라. 백트래킹과 DP(memoization)을 이용해서 풀었다. dp[ind] = 입력문자열[ind~]로 만들 수 있는 정답 경우의 수 ind 번째 문자를 탐색 중일 때, 해당 문자는 십의자리로 디코딩될수도 있고, 일의자리로 디코딩 될 수도 있다. 두 가지 경우의 수를 구한뒤 더해준다. 십의 자리로 디코딩될 수 있는 경우의 수를 먼저 알아보자. 만일 ind+1 번.. 2021. 7. 14.
[Leetcode][17] Letter Combinations of a Phone Number 문제 : leetcode.com/problems/letter-combinations-of-a-phone-number/ 전화 버튼과 동일한 숫자와 문자의 매핑이 있다. 2~9까지의 숫자로 이루어진 문자열이 주어지면 가능한 모든 문자 조합을 반환해라. 하나의 숫자에 복수개의 문자가 매핑되므로 dict[숫자] = 문자의 배열 을 먼저 구해준다. 가능한 문자 조합들은 백트래킹을 이용하여 구한다. 예시로 주어진 23이면 1. 빈 문자열부터 시작해서 2에 해당하는 문자들 중 하나를 넣고("a") 다음 숫자를 판단한다. 2. "a" 이후 3에 해당하는 문자들 중 하나를 세팅한다. "ad". 모든 digits들의 숫자를 판단했으므로 "ad"를 정답에 추가한다. 3. 가장 마지막 문자를 제거한 후('d'가 제거되어 "a.. 2021. 4. 10.
[BOJ][14888] 연산자 끼워넣기 문제 : www.acmicpc.net/problem/14888 N의 범위가 2~11 이다. 백트래킹으로 돌려도 될만한 시간이다. 정수집합을 앞에서부터 탐색해가면서 가능한 부호를 모두 돌려봐서 나오는 수들 중 최대값, 최소값을 구한다. pair answer; // arr : 정수형 배열 // signCnt : 부호 개수, // ind : arr 탐색 중인 인덱스 // result : 이때까지 계산한 결과값 // sign : arr[ind]에 적용할 부호. arr[ind] 앞에 들어갈 부호 void backtracking(int[] arr, int[] signCnt, int ind, int result, int sign) { // 경계값 확인 sign 부호 확인 + 인 경우: result += arr[ind.. 2020. 10. 24.
반응형