본문 바로가기

Star43

[Leetcode] 1254. Number of Closed Islands 문제 : https://leetcode.com/problems/number-of-closed-islands/description/ 0(육지)과 1(물)로 이루어진 2차원 그리드가 주어집니다. 섬은 4방향으로 연결된 0으로 이루어진 최대 그룹이며, 폐쇄된 섬은 1로 둘러싸인 섬입니다. 폐쇄된 섬의 수를 반환하세요. 섬은 물로 완벽하게 둘러쌓여야 하므로 배열의 가장자리와 맞닿아 있는 육지는 섬으로 보지 않습니다. 따라서, 먼저 가장자리부터 탐색하면서 DFS 혹은 BFS로 가장자리 땅이 육지인 경우 연결된 육지들을 전부 물로 바꿔주는 사전작업을 해줍니다. 이 후, 땅들을 다시 탐색하면서 탐색 중인 땅이 육지인 경우 정답을 1 추가한 뒤, 마찬가지로 DFS/BFS로 연결된 육지들을 모두 물로 바꿔줘서 중복 정답.. 2023. 4. 6.
[Leetcode] 2439. Minimize Maximum of Array 문제 : https://leetcode.com/problems/minimize-maximum-of-array/description/ 0부터 인덱싱된 n개의 음이 아닌 정수로 구성된 nums 배열이 제공됩니다. 한 번의 작업에서는 다음을 수행해야 합니다. 1. 1 0 입니다. 2. nums[i]를 1 감소시킵니다. 3. nums[i-1]를 1 증가시킵니다. 작업 수행 후 nums의 최대 정수 값 중 가능한 최소 값을 반환합니다. nums의 최대 정수 값 중 가능한 최소 값을 구하려면 모든 요소들을 평균 값으로 만들면 됩니다. 문제 2, 3번을 통해 알 수 있는 점은 뒤에 있는 nums 요소의 수는 앞으로 이동 가능할 수 있다. 입니다. ex) [1, 2, 3, 4] -> [3, 2, 3, 2] (4의 2를.. 2023. 4. 5.
[Leetcode] 629. K Inverse Pairs Array 문제 : https://leetcode.com/problems/k-inverse-pairs-array/ inverse pairs : 0 nums[j] 조건을 만족하는 [i, j]. DP[n][k] = n 크기의 nums 배열이 있을 때 k 개의 inverse pairs 를 가지는 경우의 수. n-1 크기의 nums에서 어떻게 n 크기의 nums를 만들 수 있는지 먼저 살펴보자. [그림 1] 에서 n=4, k=1인 경우는 왼쪽 아래와 같이 총 3가지 방법이 있다. 3가지 리스트들에서 4인 원소들을 제거하면 오른쪽과 같은 리스트들이 나온다. 여기에서 추론 가능한건 n-1 크기의 배열에서 추가되는 4의 위치에 따라 k(inverse pairs)의 크기가 달라진다는 것이다. 예를 들어보자. [그림 2] 에서 [.. 2022. 7. 17.
[Leetcode] 968. Binary Tree Cameras 문제 : https://leetcode.com/problems/binary-tree-cameras/ 이진트리의 루트 노드가 주어진다. 노드의 각 카메라가 부모, 자신, 직계 자식 노드를 모니터링 할 수 있는 트리 노드에 카메라를 설치한다. 트리의 모든 노드를 모니터링 하는데 필요한 최소 카메라 수를 구하라. DFS로 최하단에 있는 노드들부터 상태를 갱신하면서 탐색한다. 각 노드들에서 나타날 수 있는 경우는 총 3가지이다. 1. Not Monitored : 모니터링 되고 있지 않은 상태이다. (이 경우 부모 노드에서 처리하도록 한다.) 2. Monitored : 모니터링 되고 있는 상태이다. 3. Set Camera : 카메라가 세팅된 상태이다. 탐색 중인 노드는 초기 값은 모니터링 되고 있지 않은 상태(.. 2022. 6. 17.
[Leetcode] 1658. Minimum Operations to Reduce X to Zero 문제 : https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/ 정수 배열 nums와 정수 x가 입력으로 주어진다. 한 번의 작업으로 배열 nums에서 가장 좌측 혹은 가장 우측에 있는 요소를 제거 하고 x에서 제거한 요소의 값을 뺄 수 있다. 최소 몇 번의 작업으로 x를 정확히 0으로 만들 수 있는지 구하라. 만일 불가능하다면 -1을 반환하라. 부분합과 투포인터로 구할 수 있다. 부분합을 만들어 subsum 배열에 세팅한다. 첫 번째 예제 [1, 1, 4, 2, 3], x=5 로 표를 세팅해보면 [그림1]과 같다. 정답이 되는 제거되는 요소는 가장 뒤 요소 2, 3이다. 이를 반대로 생각하면 제거되지 않는 요소들의 합은 nums 전체.. 2022. 6. 11.
[leetcode] 354. Russian Doll Envelopes 문제 : https://leetcode.com/problems/russian-doll-envelopes/ 배열을 width 오름차순으로 정렬한다. 조건에서 width 는 고려하지 않게 하기 위함이다. 정렬 후 앞에 있는 요소의 width는 뒤에 있는 요소의 width 보다 항상 작거나 같으므로 height 만 고려하면 된다. 결국 정렬된 후 height의 LIS(최장 증가 수열)의 길이를 구하면 이게 정답이 된다. 위와 같은 알고리즘을 사용한다고 할 때, 고려할 점이 하나 있다. [[4,5],[4,6],[6,7],[2,3],[1,1]] 입력 배열이 위와 같을 때, [4,5] [4,6] 중 하나만 선택되게 해야 한다. height의 LIS로 정답을 구할 때 width가 동일한 요소들은 하나만 선택하게 하려.. 2022. 5. 26.

티스토리툴바