본문 바로가기

Star41

[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.
[Leetcode] 785. Is Graph Bipartite? 문제 : https://leetcode.com/problems/is-graph-bipartite/ 인접한 노드의 색을 현재 노드의 색과 다른 색으로 칠해가면서 너비우선탐색을 진행한다. 칠할 수 있는 색은 두가지이다. 인접한 노드에 색이 칠해져 있지 않다면 현재 노드의 색과 다른 색으로 노드를 칠하고 칠한 노드를 탐색한다. 인접한 노드에 이미 색이 칠해져 있다면 현재 노드의 색과 비교한다 현재 노드의 색과 다른 색이면 유효한경우이다. 현재 노드의 색과 같은 색이면 유효하지 않으므로 false를 반환한다. 시작노드를 첫번째 노드만으로 잡고 너비우선탐색을 한 번만 진행한다면 [그림 1]과 같이 3~6번 노드의 유효성은 체크할 수 없다. 모든 노드를 시작지점으로 잡고 위 방법으로 노드들을 탐색하되 노드의 색 배.. 2022. 4. 29.
[Leetcode] 31. Next Permutation 문제 : https://leetcode.com/problems/next-permutation/ 정수 배열이 있을 때 해당 배열의 요소들의 순서를 바꿔서 사전순 다음 시퀀스로 만들어라. 만일 불가능하다면 사전순 가장 작은 순서로 재배열해야한다. 예를 들어, arr = [2, 1, 3]이라면 사전순 다음 순서인 [2, 3, 1]로 재배열 시켜야한다. 전부 내림차순으로 정렬된 순열의 다음 사전순 배열은 이들을 역순한 것과 같다. 예를 들어, arr = [3, 2, 1]의 경우 다음 사전순 배열은 [1, 2, 3]이다. 내림차순된 배열의 다음 사전순 배열을 구하는 방법을 알았으니 내림차순 배열의 가장 앞에 있는 숫자를 해당 숫자보다 큰 수들보다 가장 작은 수로 바꾸면 다음 사전순 배열을 구할 수 있다. 말이 좀.. 2022. 4. 3.

티스토리툴바