Medium174 [leetcode] 429. N-ary Tree Level Order Traversal 문제 : https://leetcode.com/problems/n-ary-tree-level-order-traversal/ 트리가 주어지면, 레벨 순서 순회 결과를 구하여라. 탐색문제. 너비우선탐색으로 구할 수 있다. 큐를 만들고 해당 큐에 루트 노드를 넣는다. 큐를 빌때까지 탐색하면서 새로운 큐에 탐색한 노드들의 자식 노드들을 넣는다. 큐가 빌때까지 탐색한 노드들이 같은 레벨에 있는 노드들이다. 새로운 큐를 만들었으면 해당 큐를 다시 빌때까지 탐색하면서 또다른 큐(다음 레벨의 노드들)를 만드는 과정을 반복한다. 시간복잡도는 O(N). N = 노드 개수. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/429.%20N-ary.. 2021. 8. 7. [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] 542. 01 Matrix 문제 : https://leetcode.com/problems/01-matrix/ 0과 1로 이루어진 mat 배열이 주어질 때, 각 셸에서 0과 가장 가까운 거리를 저장한 배열을 만들어 반환하라. BFS로 풀었다. 배열을 탐색하면서 0인 셸들의 x, y 좌표를 큐에 넣는다. 큐에 넣은 셸들의 0과 가장 가까운 거리는 0이다. 두 번 탐색하면 안되기 때문에 visit 배열을 만들고 큐에 넣은 좌표들의 visit을 true로 세팅한다. 큐를 탐색하며 큐의 front에 있는 좌표(let, (x, y))의 상하좌우 셸들 중에 탐색하지 않은 좌표(let, (nx, ny))들을 큐에 넣는다. 그리고 큐에 넣은 좌표들의 탐색여부를 true로 갱신, 정답 배열의 값을 (x, y) 정답 배열의 값 + 1로 갱신한다. m.. 2021. 7. 29. [leetcode] 236. Lowest Common Ancestor of a Binary Tree 문제 : https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/ 트리가 주어질 때, 노드 p, q의 최하위 공통조상(LCA; Lowest Common Ancestor)를 찾아라. 재귀함수로 풀었다. 이 함수는 탐색하는 노드를 루트로 하는 서브트리에서 p, q를 찾은경우 해당 노드를 반환하거나, 만약 두노드의 최하위 공통조상인 경우 해당 노드를 반환한다. p, q 가 서브트리에 없는 경우는 NULL을 반환한다. 현재 탐색 중인 노드가 p 또는 q 인 경우 현재 노드를 반환한다. 왼쪽 자식, 오른쪽 자식들을 탐색노드로 함수를 호출한다. 왼쪽, 오른쪽 자식들에서 p, q를 찾았다면(NULL이 아니라면) 현재 탐색중인 노드가 LCA가 되므로.. 2021. 7. 22. [Leetcode][611] Valid Triangle Number 문제 : https://leetcode.com/problems/valid-triangle-number/ 0이상의 정수배열 nums가 주어질 때, 이 들 중 3개 수를 골라서 삼각형을 만들 수 있는 경우의 수를 구해라. 투포인터로 풀었다. nums 배열을 오름차순 정렬한다. nums를 처음부터 탐색하면서 탐색하는 정수는 고정적으로 사용하는 변의 길이다. (let, a) 탐색한 정수의 바로 다음 정수들을 탐색하는데 이를 다음으로 선택하는 변의 길이이다. (let, b) 삼각형을 만들기위한 2개의 변을 고정했다. 삼각형이 되기 위한 조건은 두 개의 변의 길이 합이 나머지 하나(최장길이 변)의 길이보다 커야한다. 나머지 변을 c라고 하자. 만일 이전 탐색으로 구한 길이들의 관계가 a + b > c 였다면, b는.. 2021. 7. 15. 이전 1 ··· 9 10 11 12 13 14 15 ··· 29 다음