전체 글657 [Leetcode]11. Container With Most Water 문제 : https://leetcode.com/problems/container-with-most-water/ 수직선 높이를 나타내는 배열이 주어진다. 두 개의 수직선을 선택해서 그 사이에 물을 넣는다고 할 때 가능한 최대 용량은 얼마인가. 투포인터로 푼다. 왼쪽부터 시작하는 left 포인터, 오른쪽부터 시작하는 right 포인터가 있다. left, right 수직선을 선택했을 때의 용량을 구하고 이들 중 최대 값이 정답이 된다. 용량을 구한뒤 left가 right보다 낮다면 left를 +1 하고, right가 left보다 낮다면 right를 -1 해준다. 시간복잡도는 O(N). N = 배열의 크기 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/lee.. 2021. 11. 3. [Leetcode] 980. Unique Paths III 문제 : https://leetcode.com/problems/unique-paths-iii/ m x n 정수형 배열 grid가 주어진다. 1 : 시작 지점. (1개 존재) 2 : 종료 지점. (1개 존재) 0 : 걸을 수 있는 곳 -1 : 장애물 상하좌우 4방향으로 이동가능할 때, 시작지점에서 종료지점으로 갈 수 있는 방법의 수를 구하라. 백트래킹. 시작지점부터 장애물이 아닌 곳으로 이동하면서 이동횟수를 저장하면서 상하좌우 방향으로 탐색한다. 탐색하면서 지나간 자리는 다시 못 지나가게 별도의 플래그 배열에 탐색한 위치는 표시를 해둔다. 종료지점에 도달했을 때, 걸음의 수가 grid 배열의 0, 2 cell의 수와 같다면 정답이 가능하므로 정답 방법의 수에 1을 더한다. 시간복잡도는..? 소스코드 : h.. 2021. 11. 2. [Leetcode] 130. Surrounded Regions 문제 : https://leetcode.com/problems/surrounded-regions/ 'X', 'O' 로 이루어진 m x n 배열이 있다. 'O'로 둘러쌓인 'X' 구역이 있다면 이들을 모두 'O'로 바꾸어라. DFS, BFS 탐색으로 X로 이루어진 구역들을 구할 수 있다. 이 때, m x n 배열의 경계선에서부터 시작하는 X 구역들은 O로 둘러쌓인게 아니므로 범위에서 제외되어야 한다. 따라서 먼저 경계선에 존재하는 X 구역들을 모두 DFS나 BFS 탐색으로 이미 방문했다고 갱신한다. 이 후, 배열을 탐색하며 이미 방문/탐색 하지 않은 X구역들을 구한 뒤 이들을 모두 O로 바꿔주면 정답이 된다. 시간복잡도는 O(nm) 소스코드 : https://github.com/fpdjsns/Algorit.. 2021. 11. 1. [Leetcode] 222. Count Complete Tree Nodes 문제 : https://leetcode.com/problems/count-complete-tree-nodes/ 완전 이진 트리(complete binary tree)의 루트 노드가 입력으로 주어지면 트리의 노드 수를 반환해라. 시간복잡도를 O(N) 보다 작게 만들어라. 포화 이진 트리의 노드 수는 2^(트리 높이) - 1 임을 사용하자. 최좌측 단노드까지의 높이와 최우측 단노드까지의 높이가 같은 경우 포화 이진 트리가 된다. 높이가 다른 경우, 왼쪽 하위 노드들 수와 오른쪽 하위 노드들 수를 구해서 더하고 루트 노드 수인 1을 더한 값이 노드 수가 된다. 왼쪽 하위 노드들 수와 오른쪽 하위 노드들 수는 재귀함수를 이용해 구한다. 완전이진트리인지 구하기 위해 log2N이 소요되고, 최악의 경우 높이를 탐색.. 2021. 10. 29. [Leetcode] 437. Path Sum III 문제 : https://leetcode.com/problems/path-sum-iii/ 이진 트리와 targetSum이 주어지면 경로의 노드들 값의 합이 targetSum과 같은 경로들의 수를 구하라. 백트래킹. 트리를 탐색하면서 탐색한 노드들의 val의 합의 개수를 map에 저장한다. 탐색하면서 이때까지의 합(sum)에서 targetSum을 뺀 값의 개수들의 합이 정답이 된다. [그림 1]에서는 테이블들의 빨간색 셸들이 이에 해당하여 정답은 3이 된다. 시간복잡도는 O(N). N = 노드 수 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/437.%20Path%20Sum%20III.cpp 2021. 10. 18. [leetcode] 279. Perfect Squares 문제 : https://leetcode.com/problems/perfect-squares/ 정수 n이 입력으로 주어지면 완전제곱수들의 합으로 n을 만들 때 사용되는 완전제곱수들의 최소 개수를 반환하라. DP로 풀 수 있다. dp[i] = i를 만들 때 사용되는 완전제곱수들의 최소 개수 = dp[i - j*j] + 1 들 중 최소값 (j*j 2021. 10. 14. 이전 1 ··· 18 19 20 21 22 23 24 ··· 110 다음
