본문 바로가기

분류 전체보기657

[Leetcode] 630. Course Schedule III 문제 : https://leetcode.com/problems/course-schedule-iii/ 소요기간(연속), 완료되어야 하는 기간을 가진 course들의 배열 courses이 입력으로 주어진다. 1일차부터 시작하고 2개의 코스를 한 번에 들을 수는 없다. 수강할 수 있는 최대 코스 수를 구하라. courses 배열을 완료되어야 하는 기간의 오름차순으로 정렬한다. 우선순위큐를 만든다. 이 큐에는 현재까지 수강가능한 최대 코스 수를 가지는 코스들의 수강기간(duration)로 이루어져 있다. (왜 duration을 넣는지는 뒤에서 설명할 예정(1)) 큐에 있는 코스들을 모두 수강했을 때 쇼요기간을 day 변수에 저장해둔다. 정렬된 courses 배열을 앞에서부터 탐색하면서 큐에 넣을 수 있는지 판단.. 2022. 6. 24.
[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] 51. N-Queens 문제 : https://leetcode.com/problems/n-queens/ 두 개의 퀸이 서로 공격하지 않도록 n x n 체스판에 n개의 퀸을 배치하라. 가능한 모든 경우의 체스판 형태를 반환하라. (Q : 퀸, . : 빈칸) (참고로 퀸은 한 번 움직일 때 앞, 뒤, 옆, 대각선 어떤 방향이든 원하는 만큼 이동 가능) 백트래킹으로 풀었다. 퀸은 앞, 뒤, 옆, 대각선 방향을 원하는 만큼 이동 가능하기 때문에 row, col, 대각선에 놓을 수 있는지 여부를 저장해야 한다. 백트래킹 구현 시 하나의 행에 퀸을 두는 경우의 수를 판단한다고 하면 하나의 행에는 하나의 퀸만 놓게 구현하면 row 에 퀸을 놓을 수 있는지 여부는 저장을 하지 않아도 된다. 열의 퀸 저장가능 여부는 n 크기의 boolean .. 2022. 6. 4.
[220601] leetcode 5월 Badge도 획득 알고리즘 포스팅은 뜸하지만 매일 문제는 풀고 있다. 요즘은 바빠서 다른 문제는 못 풀고 있는데 시간 좀 나면 근무 안하는 날에는 코드잼 못 풀었떤 문제들 하나씩 풀어서 포스팅하고 싶다. 그리고 포스팅 할것들 목록은 계속 업데이트 하고 있는데 그것도 하나씩 올리고. 하고 싶은게 많네. 행복하다 2022. 6. 1.
[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.

티스토리툴바