본문 바로가기

dfs21

[Kickstart][2020][Round A] 2. Plates 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d40bb N개의 접시 스택이 주어지고, 각 접시들은 각 스택마다 K개의 접시들로 이루어진다. 각 접시들은 양의 정수를 가지고 있으며 접시들은 쌓여 있으므로 위에 있는 접시들부터 차례대로 가져올 수 있다. (중간에 있는 접시만 가져올수는 없다.) 최대 P개의 접시들로 저녁을 구성하려고 할 때, 해당 접시들의 양의 정수의 합이 최대가 되는 경우를 구하라. (최대 접시들의 고유 값의 합 리턴) 탐색은 dfs로 하고 메모이제이션을 위해 dp를 사용했다. n번째 접시 스택부터 N번빼 접시 스택까지 접시를 선택할 수 있다고 할 때, 총 P-p개의 접시로.. 2020. 3. 24.
[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.
[leetcode][140] Word Break II 문제 : https://leetcode.com/problems/word-break-ii/ DFS를 돌리면 TLE가 발생해서 memoization을 추가했다. dp[lastInd] = s[0 ~ lastInd] 로 만들 수 있는 정답 가능 문자열의 리스트이다. 즉 우리가 구할 건 dp[ |str| - 1 ]. 문자열의 뒤에서부터 탐색을 하므로 wordDict의 문자열들의 마지막 문자를 key로 하는 dictionary를 하나 만들었다. ex) wordDict = ["ab", "b", "ac"] -> dict ={ {'b', ["ab", "b"]}, {'c', ["c"]}} dict에서 lastInd를 key로 하는 단어들을 가져온 뒤, 문자열의 서브 문자열이 가능한지 체크한다. ex) banana a가 l.. 2019. 12. 19.
[leetcode][979] Distribute Coins in Binary Tree 문제 : https://leetcode.com/problems/distribute-coins-in-binary-tree/ 루트에서 자식노드로 내려가면서 현재 탐색 중인 노드를 루트로 하는 서브트리의 모든 노드들이 코인을 하나씩 가지고 남는 코인개수를 반환한다. 이 함수를 getCoins라 한다면 수도코드는 다음과 같다. getCoins(root) = getCoins(root.left) + getCoins(root.right) + root.val - 1 root 노드의 val(가지고 있는 코인 개수)와 자식 노드들에게서 남는 코인개수를 가져와서 더해준다. 그리고 1을 빼준다. 이유는 root 노드도 1개의 코인을 가져야하기 때문에 root 몫의 코인 개수(1개)는 제외시켜야 하기 때문이다. 남는 코인개수를.. 2019. 12. 17.
[leetcode][1219] Path with Maximum Gold 문제 : https://leetcode.com/problems/path-with-maximum-gold/ grid 사이즈 조건이 n, m 2019. 10. 14.
[leetcode] 1020. Number of Enclaves 문제 : https://leetcode.com/problems/number-of-enclaves/ DFS 문제. 배열 A를 탐색하면서 1일 때 현재 요소를 기준으로 상하좌우로 탐색(DFS)하면서 1의 개수를 센다. 세면서 방문한 배열 요소는 0으로 갱신한다. 만약 DFS 탐색시 배열밖으로 벗어난다면 1의 개수는 정답이 될 수 있으므로 정답에 더해준다. 소스코드 : https://gist.github.com/fpdjsns/91d296e10a828da48b4751a9fad00080 2019. 4. 8.