본문 바로가기

알고리즘 문제/Leetcode283

[leetcode] 1463. Cherry Pickup II 문제 : https://leetcode.com/problems/cherry-pickup-ii/ rows x cols 체리 필드(grid)가 주어지고 각 요소값은 체리 수를 의미한다. 로봇1은 왼쪽 상단 (0,0)에서 출발하고 로봇2는 오른쪽 상단 (0, cols-1)에서 출발한다. 셀 (i,j)에서 로봇은 (i+1, j-1), (i+1, j), (i+1, j+1) 3가지 중에 한 곳으로 이동할 수 있다. 두 로봇이 동일한 셀에 있을 때 한 로봇만 체리를 가져갈 수 있다. 로봇들이 이동할 때, 수집할 수 있는 체리의 최대 수를 구해라. DP로 풀 수 있다. dp[row][col1][col2] = 로봇1은 (row, col1), 로봇2는 (row, col1)에 있을 때 수집가능한 체리수의 최대값. dp[ro.. 2022. 1. 11.
[Leetcode] 1041. Robot Bounded In Circle 문제 : https://leetcode.com/problems/robot-bounded-in-circle/ 로봇이 (0, 0) 위치에 북쪽 방향을 향하고 있다. 'G' : 1칸 앞으로. 'L' : 왼쪽으로 회전. 'R' : 오른쪽으로 회전. 로봇은 주어진 명령을 영원히 반복하며 이동한다고 할 때, 로봇이 특정 원을 벗어나지 않는지 구해라. 방향 회전은 L, R 90도씩만 움직이기 때문에 명령을 1번, 2번, 3번, 4번 수행 한 뒤 원점 (0, 0)으로 돌아올 수 있다면 특정 원을 벗어나지 않는 경우이고 4번 이내에 (0, 0)으로 돌아오지 않는다면 원을 벗어날 것이다. 시간복잡도는 O(N). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetco.. 2022. 1. 11.
[leetcode] 1094. Car Pooling 문제 : https://leetcode.com/problems/car-pooling/ 총 좌석이 capacity인 차량이 있다. 차량엔 capacity 만큼의 탑승자만 태울 수 있다. 차량은 동쪽으로만 주행하며 (탑승자 수, from, to) 정보를 저장한 trip 배열이 주어진다. from에서 탑승자 수 만큼 차량에 태우고 to에 탑승자 수 만큼 차량에서 내린다. capacity를 넘지 않게 모든 trip 여행들을 탐색할 수 있으면 true 아니면 false를 반환하라. 부분합 배열을 만들어서 풀 수 있다. to의 최대값이 1000이므로 1000 크기의 passenger 배열을 만든다. trips 배열을 탐색하며 passenger[from] 에는 탑승자 수 만큼 더하고, passenger[to]에는 탑.. 2022. 1. 7.
[leetcode] 131. Palindrome Partitioning 문제 : https://leetcode.com/problems/palindrome-partitioning/ 문자열 s가 입력으로 주어지면 파티션의 모든 하위 문자열이 palidrome 이 되도록 하는 모든 경우를 구하라. 문자열을 앞뒤로 읽었을 때 같은 문자열인 경우 palidrome이라 한다. DP + backtracking 팰린드롬인지 구하는 함수. DP // dp[s][e] = str[s ~ e]가 palidrome인지 fun isPalidrome(str, s, e) { if(dp[s][e]가 없으면) dp[s][e] = str[s]와 str[e]가 같은 문자이며 isPalidrome(str, s+1, s-1) 인 경우 return dp[s][e]; } 팰린드롬 하위 문자열들을 만들어서 partit.. 2022. 1. 6.
[Leetcode] 1496. Path Crossing 문제 : https://leetcode.com/problems/path-crossing/ path를 탐색하며 현재 위치 좌표를 갱신한다. 갱신하면서 set에 현재 위치의 좌표에 온적있는지 확인한다. 만일 탐색한적 있다면 true를 반환한다. 탐색한적 없다면 set에 현재 위치를 추가하고 탐색을 계속한다. 모든 path를 탐색할때까지 중목된 좌표를 탐색한 적 없다면 false를 반환한다. 시간/공간복잡도는 O(N). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1496.%20Path%20Crossing.cpp 2021. 12. 28.
[Leetcode] 56. Merge Intervals 문제 : https://leetcode.com/problems/merge-intervals/ 간격 start, end 를 저장한 interval 배열이 주어질 때, 겹치는 모든 간격을 병합하여 간격이 겹치지 않게 만든 뒤 간격 배열을 반환하라. intervals 배열을 start 오름차순으로 정렬한다. start, end 변수를 만들고 겹치는 간격을 만나면 end 변수를 갱신해간다. 정렬한 배열을 앞에서부터 탐색하며 종료 간격 end가 탐색하는 간격의 start보다 같거나 크다면 합쳐질 수 있는 경우이므로 end를 갱신한다. 만일 그렇지 않다면 start, end를 정답 배열에 추가한다. [[1,3],[2,6],[8,10],[15,18]] 예시 intervals[i] start end answer 배열 .. 2021. 12. 24.

티스토리툴바