BackTracking14 [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. [BOJ][15686] 치킨 배달 문제 : https://www.acmicpc.net/problem/15686 백트래킹으로 풀 수 있다. 도시들을 탐색하면서 집 배열, 치킨집들 배열을 만든다. 치킨집들을 선택해나가면서 집들에서 가장 가까운 치킨집의 거리들을 갱신해나간다. // dist : i번 집과 치킨집과의 최소 거리 // ind : 치킨집 인덱스, // cnt : 선택된 치킨집 개수 void backtracking(vector dist, int ind, int cnt) { // 경계값 확인 backtracking(dist, ind + 1, cnt); // ind 번째 선택하지 않고 다음 치킨집 탐색 pair chi = chickens[ind]; // ind 번째 치킨집 좌표 저장 int sum = 0; // dist 배열 합 for .. 2020. 10. 20. [leetcode][39] Combination Sum 문제 : leetcode.com/problems/combination-sum/ 정수형 배열 candidates이 주어질 때 이들을 더해서 target을 만들 수 있는 배열을 구해라. 이 때, candidates 값은 중복해서 더해질 수 있다. 오랜만에 찾아온 백트래킹 친구. fun backtracking(index, target, 저장배열[]) { if (target == 0) 정답배열에 저장배열 추가. if (target < 0) 정답 불가능하므로 종료. for(num = candidates[index, 끝]) { 저장배열 뒤에 num 추가. backtracking(index, target - num, 저장배열) 저장배열 뒤에 추가한 num 삭제. } } 시간복잡도는 O(|candidates| * ta.. 2020. 10. 5. 이전 1 2 3 다음