전체 글 (30) 썸네일형 리스트형 [hard] 629. K Inverse Pairs Array 문제 https://leetcode.com/problems/k-inverse-pairs-array/ K Inverse Pairs Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이방법 숫자제한을 보니 제일 먼저 떠오르는 브루트포스로 풀면 시간초과가 날 수 밖에 없는 문제라서 DP로 접근해야겠다고 생각했다 그런데 DP 규칙을 어떻게 만들어야하는지... 역시 hard... 그래서 https://leetcode.com/problems/k-inverse-.. [medium] 576. Out of Boundary Paths 문제 https://leetcode.com/problems/out-of-boundary-paths/ Out of Boundary Paths - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이방법 중복방문 허용하면서 maxMove 이내로 움직여서 공을 칸 밖으로 내보낼 수 있는 경우의 수를 구하는 문제이다 처음에는 DFS로 접근하면 될 줄 알았는데 중복방문이 되다보니 시간초과가 났다 값을 저장하면서 처리해야 시간초과가 해결될 것 같은데 구현하는 과정에서 헷갈려.. [medium] 695. Max Area of Island 문제 https://leetcode.com/problems/max-area-of-island/ 풀이방법 자주 보이는 BFS 문제 유형이다. grid 전체를 탐색하는데 이미 방문한 곳은 체크하면서 중복 탐색하지 않도록 해야한다. (grid 값이 0인 부분은 탐색할 필요없다) 그리고 탐색하는 과정에서 1이 이어져있는 부분의 넓이를 계산하며 최대 넓이를 저장해두었다가, 전체 탐색이 끝나면 최대 넓이를 리턴한다. 그래서 시간복잡도는 O(M*N), 공간복잡도도 O(M*N) 코드 class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: M = len(grid) N = len(grid[0]) visit = [[False]*N for i in r.. [medium] 1696. Jump Game VI 문제 https://leetcode.com/problems/jump-game-vi/ Jump Game VI - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이방법 보자마자 DP로 풀어야겠구나 싶었다 (계단 오르기 문제랑 비슷한 유형으로 보여서...) dp 배열을 -inf 로 초기화하고 각 index에 도달했을 때 최대 score를 dp 배열에 저장해가면서 풀면 된다 dp[n-1] = max(dp[n-1-1], dp[n-1-2], ..., dp[n-1-k]) .. [medium] 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cut 문제 https://leetcode.com/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/description/ 풀이방법 가장 큰 사각형을 만드려면 가로와 세로가 각각 최대이면 된다. 가로가 최대인 것을 찾으려면 0, horizontalCuts, h 사이의 간격들 중에 가장 긴 부분을 길이를 찾아서 저장한다. 그런데 이 때 example2 처럼 horizontalCuts 혹은 verticalCuts 가 정렬되어있지 않을 수 있으므로, 먼저 정렬해주고 최대길이를 찾아야 한다. 비슷하게 세로가 최대인 것을 찾으려면 0, verticalCuts, w 사이의 간격들 중에 가장 긴 부분을 길이를 찾아서 저장한다. 그 다음이 .. [캐나다] 옐로나이프 & 밴프 국립공원 여행준비 드디어 코로나가 어느정도 마무리된 것 같아서 해외여행 계획을 세우고 있다. 코로나 전에 예약까지 다 했다가 취소했던 캐나다 오로라 여행을 드디어 다시 준비해보려고 한다. 목적지 캐나다 옐로나이프랑 밴프국립공원 옐로나이프는 가을, 겨울 모두 오로라를 볼 수 있다고 해서 덜 추운 가을로 정했다 (겨울까지 못 기다릴꺼 같기도 했고...) 항공권 옐로나이프, 캘거리 모두 직항이 없어서 환승을 해야한다. 항공권은 스카이스캐너, 11번가 항공, 인터파크 항공을 비교해서 최저가인 에어캐나다로!! 인천 -> 옐로나이프 갈 때 밴쿠버에서 환승을 해야하는데, 이 때 짐이 연결이 안되고 짐을 찾았다가 다시 붙여야한다고 해서 경유시간이 3시간 이상인걸로 예약했다. 숙소 옐로나이프에서 오로라 투어를 신청해야하는데 픽업오는 호텔.. [medium] 406. Queue Reconstruction by Height 문제 https://leetcode.com/problems/queue-reconstruction-by-height/description/ Queue Reconstruction by Height - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이방법 개인적으로 별로 안 좋아하는 문제 유형이다. 처음에 정렬하고 시작해서 그 다음은 조건 맞춰 구현만 하면 되는 문제 정렬방법은 사람마다 다른듯한데 나는 k를 우선순위로 하고 그 다음을 h로 해서 오름차순 정렬을 해서.. [medium] 665. Non-decreasing Array 문제 https://leetcode.com/problems/non-decreasing-array/description/ 풀이방법 1. 앞/뒤 방향에서 non-decreasing 조건에 맞는 숫자들인지 탐색하면서 start 인덱스와 end 인덱스를 움직인다 2. 조건에 맞지 않는 숫자가 나오면 그 위치에 인덱스를 고정한다. 인덱스 고정할 일 없이 while 문이 끝나면 True 리턴 인덱스가 고정됬는데 start 와 end의 간격이 1을 넘어가면, 이는 숫자 하나 삭제만으로는 조건을 만족시킬 수 없다는 의미이므로 False 리턴 4. 고정된 start, end 인덱스에서 nums[start] 혹은 nums[end]에 있는 숫자를 삭제해서 non-decreasing 조건에 맞출 수 있는지 체크한다 start.. 이전 1 2 3 4 다음
