문제 https://leetcode.com/problems/longest-consecutive-sequence/ Longest Consecutive Sequence - 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 풀이 난이도: Medium 간단히 정렬로 해결하고 싶지만 시작 복잡도를 O(n)으로 구현해야 하는 문제. O(n)으로 구현하기 위해서는 값의 삽입, 삭제가 O(1)에 가능한 자료구조를 사용해야 한다. 가장 간단한 1차원 배열에 nums의 원소들을 저장..

문제 https://leetcode.com/problems/number-of-islands/ Number of Islands - 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 풀이 난이도: Medium DFS나 BFS로 풀 수 있는 문제로, 각 grid의 방문 여부를 저장하는 2차원 boolean 배열 visited로 간단히 구현할 수 있다. 모든 격자 중에 아직 방문하지 않고 1인 격자에서 DFS나 BFS를 실행할 때마다 Island의 count를 1씩 늘려준..

문제 https://leetcode.com/problems/pacific-atlantic-water-flow/ Pacific Atlantic Water Flow - 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 풀이 난이도: Medium 처음에는 해석하는데 애를 먹었는데 height above sea level이 해발고도를 의미하는 것이었다. 태평양(Pacific)과 대서양(Atlantic)으로 둘러싸인 섬의 각 좌표의 해발고도가 주어지고 물은 같거나 낮은 곳으..

문제 https://leetcode.com/problems/course-schedule/ Course Schedule - 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 풀이 난이도: Medium 선수 과목은 방향 그래프로 나타낼 수 있다. 문제에 주어지는 것은 방향 그래프의 edge이므로 선수 과목인 b에서 a로의 간선을 저장해주는 것으로 간단히 그래프를 구현할 수 있다. 단, 아래와 같이 0과 1 과목이 서로를 선수과목으로 가지고 있다면 두 과목 모두 수강할 ..

문제 https://leetcode.com/problems/clone-graph/ Clone Graph - 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 풀이 난이도: Medium java를 공부 중이라 연습하는 겸, 이제 알고리즘 문제도 자바로 풀어보려 한다. C++에서도 STL을 자주 사용했더니 java의 컬렉션 프레임워크도 빨리 적응할 수 있는 것 같다. 이번 문제는 인접 노드들을 저장하고 있는 노드들로 그래프를 주면 해당 그래프를 완전히 복사한 새로운 그..

문제 https://leetcode.com/problems/jump-game/ Jump Game - 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 풀이 난이도: Medium DP풀이 일단 가장 생각하기 쉬운 다이나믹 프로그래밍 풀이부터 소개하겠다. dp[idx]에 idx에서부터 마지막까지 도달할 수 있는 지 여부를 저장한다. dp[end]만 true로 설정하고 뒤에서부터 배열을 순서대로 확인해본다. idx에서는 1~nums[idx]까지 점프할 수 있으므로 dp[..

문제 https://leetcode.com/problems/decode-ways/ Decode Ways - 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 풀이 난이도: Medium string에서 idx번째인 한자리 수만 알파벳으로 decode한다고 생각해보자. 이를 위해서는 [0~idx-1]까지가 decode가 가능해야한다. 만약 02에서 2를 B로 해석하면 앞의 0는 독립적으로 해석이 되어야 하지만 0은 decode가 불가능하다. 이번에는 idx-1과 idx..

문제 https://leetcode.com/problems/house-robber-ii/ House Robber II - 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 풀이 난이도: Medium 이전 문제를 풀고 오면 굉장히 쉽게 해결할 수 있다. [LeetCode] 198. House Robber (C++) [LeetCode] 198. House Robber (C++) 문제 https://leetcode.com/problems/house-robber/ Hous..

문제 https://leetcode.com/problems/house-robber/ House Robber - 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 풀이 난이도: Medium 배열로 나타난 주택들에서 인접하지 않는 원소들의 최대합을 구하는 문제. 현재 배열의 위치를 now라고 할 때 1칸 전의 위치를 prev1, 2칸 전을 prev2라고 하자. prev1에는 prev1까지의 인접하지 않는 최대합을, prev2에는 prev2까지의 최대합을 저장한다. 이제..

문제 https://leetcode.com/problems/combination-sum-iv/ Combination Sum IV - 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 풀이 난이도: Medium 배열의 원소의 합이 target이 되는 조합을 구하는 문제. 조합을 구성하는 원소가 같더라도 순서가 다르다면 다른 조합으로 취급하기 때문에 조금 까다로웠다. 처음에는 dp[value]를 value를 만들 수 있는 조합의 수라고 할 때 dp[value] = dp..