본문 바로가기

BackTracking14

[leetcode][216] Combination Sum III 문제 : leetcode.com/problems/combination-sum-iii/ 1에서 9까지의 숫자 만 사용할 수 있고 각 조합은 고유 한 숫자 집합이어야한다는 점을 고려하여 숫자 n이되는 k 숫자의 가능한 모든 조합을 찾습니다. 숫자 n을 k개의 수의 합으로 만들 때 가능한 조합들을 구하라. 이 때, 수들의 합은 1~9 중 고유한 수들의 조합이다. ex) 가능 : [1,3]. 불가능 : [2,2] -> 2가 겹침 백트래킹으로 풀었다. index 위치에 오름차순으로 숫자(let, i)를 하나씩 대입하면서 n-i, k-1 로 갱신하면서 배열을 만들어나간다. k 혹은 n이 음수가 되면 정답이 불가능한 경우다. n과 k가 모두 0이 되면 정답이 가능한 경우이므로 이때동안 만든 숫자 배열을 정답배열에 추.. 2020. 9. 12.
[leetcode][79] Word Search 문제 : https://leetcode.com/problems/word-search/ 2차원 문자 배열, 단어가 주어지면 배열에 단어의 유무를 리턴하는 문제. 신문 단어 퍼즐 같은 문제. DFS로 풀었다. 문자열 배열을 탐색하면서 탐색중인 인덱스를 시작 위치로 하여 단어가 있는지 판단한다. // board: 2차원 문자 배열 // word : 찾는 단어 // board[x][y]를 시작 위치로 하여 word가 있는지 find(board, x, y, word): // 경계 체크 if(x, y 이미 방문) return false if(board[x][y]와 word의 첫 번째 문자가 같지 않다면) return false ans = false x, y 방문 체크 for(nx, ny = 상, 하, 좌, 우 이동.. 2020. 3. 7.

티스토리툴바