알고리즘 문제/Leetcode283 [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] 827. Making A Large Island 문제 : https://leetcode.com/problems/making-a-large-island/ n x n 크기의 0과 1로 이루어진 grid 배열이 입력으로 주어질 때, 1로 이루어진 섬의 최대 크기를 구하여라. 이 때, 최대 한 번 0을 1로 바꿀 수 있다. dfs를 한 번 돌리면서 연결된 1들을 하나의 섬으로 보고 섬의 번호와 해당 섬의 크기를 map에 저장한다. grid 배열을 한 번 더 탐색하면서 탐색하는 셸이 0인 경우 해당 셸의 상하좌우에 있는 섬의 번호들을 가져온다. 상하좌우에 있는 섬들의 합 + 1 (탐색중인 0 셸이 1로 바뀌면서 증가된 섬의크기)들이 하나의 0을 1로 바꿨을 때 구할 수 있는 섬의 크기이다. 구할 수 있는 섬들의 크기들 중 최대값이 정답이 된다. 시간/공간 복잡.. 2021. 8. 2. [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] 108. Convert Sorted Array to Binary Search Tree 문제 : https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/ 오름차순 정렬된 nums 배열이 주어질 때, height-balanced BST로 변형하라. height-balanced BST는 모든 노드들의 두 하위 트리깊이가 1이상 차이가 나지 않는 이진 트리이다. height-balanced BST가 뭔가 했더니 이런식으로 불균형적인 트리를 만들지말란 의미였다. [그림 1]에서 왼쪽 하위트리의 높이는 1, 오른쪽 하위트리의 높이는 3 이므로 1 이상 차이가 나서 높이 균형 BST가 아니다. 결국 노드들을 왼쪽 오른쪽 균등하게 분배하면서 bst를 만들라는 뜻이다. 정렬된 nums 배열의 중간 값을 현재 노드로 만들고 중간 값.. 2021. 7. 27. 이전 1 ··· 17 18 19 20 21 22 23 ··· 48 다음
