문제 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..

문제 https://leetcode.com/problems/word-break/ Word Break - 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 두 종류의 메모이제이션을 활용해서 해결하였다. 1. is_contain[i][j] 문자열 s의 i~j 부분 배열이 단어로 분해될 수 있는지 여부를 저장한다. 이를 확인하기 위해 모든 단어들을 언어에서 기본 제공하는 문자열의 find함수로 s에 포함 여부를 확인한다. 이때 s= "aaaaa..

문제 https://leetcode.com/problems/longest-common-subsequence/ Longest Common Subsequence - 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문제. ' text1을 A, text2를 B라고 했을 때 A의 i번째, B의 j번째 알파벳이 동일하다면 적어도 A의 i번째, B의 j번째 이후로는 공통부분 수열(CS)의 길이가 1 이상이 된다. 이처럼 A의 i번째와 B의..

문제 https://leetcode.com/problems/longest-increasing-subsequence/ Longest Increasing Subsequence - 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문제로 최대 증가 부분 수열(LIS) 문제라고 한다. O(n^2)의 풀이와 O(n log(n))의 풀이가 있는데 두 개 다 소개하도록 하겠다. 1. O(n^2) 풀이 가장 간단한 풀이로 배열의 뒤에서부터 ..

문제 https://leetcode.com/problems/coin-change/ Coin Change - 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 유명한 다이나믹 프로그래밍 문제. 처음 풀면은 그리디 방식으로 가장 높은 동전 순서대로 amount값을 만들어 가기 쉽다. 하지만 동전이 [1, 4, 6]로 있을 때 14를 만들어야 된다고 생각해보자. 가장 높은 동전인 6을 먼저 2개 사용하면 나머지 2는 1의 동전 2개로 만들어 총..

문제 https://leetcode.com/problems/missing-number/ Missing Number - 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 풀이 난이도: Easy 난이도 순으로 3가지 풀이를 소개하겠다. (가장 중요한 풀이는 3번째라고 생각한다.) 1. 정렬 time complex O(n log n) 가장 쉬운 풀이는 배열을 정렬하고 순서대로 살펴보며 빠진 수를 찾는 것이다. 하지만 배열의 정렬에 큰 복잡도가 소요된다. 2. 전체 합 이..

문제 https://leetcode.com/problems/counting-bits/ Counting Bits - 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 풀이 난이도: Easy 위의 그림을 보면 알겠지만 2^k ~ 2^(k+1) -1 의 수들은 k+1 번째 비트가 1이고 나머지는 0 ~ 2^k -1와 뒷부분이 완전히 동일하다. 따라서 0 ~ 2^k -1의 비트에서 1의 수들에 + 1을 붙인 것이 2^k ~ 2^(k+1) -1의 1의 개수가 된다. 따라서 ..

문제 https://leetcode.com/problems/sum-of-two-integers/ Sum of Two Integers - 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 어려운 문제라기보다는 비트 연산자를 잘 활용해서 구현을 해야 하는 문제이다. 같은 부호끼리의 합은 두 수를 양수로 고려하고 덧셈 후에 부호를 붙여주면 되기 때문에 같은 부호의 수를 더하는 함수와 다른 부호를 더하는 함수를 따로 구현하였다. 일단 같은 부호라..