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

문제 https://leetcode.com/problems/container-with-most-water/ Container With Most Water - 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 log(n)) pair 자료구조를 이용하여 firt에는 높이, second에는 위치 값을 저장한 다음 높이를 내림차순으로 정렬해주자..

문제 https://leetcode.com/problems/3sum/ 3Sum - 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 Two Sum문제를 조금 더 발전시킨 문제. 문제 해결의 핵심은 세 개의 값을 더해 0(x + y + z = 0)을 만드는 것보다 y + z = -x 로 두 값을 더해 특정 값을 만드는 것으로 문제를 변형하는 것이다. 따라서 모든 원소 값을 x로 한 번씩 설정하여 스위핑으로 서치를 하면 O(n*n)의 시간 복..

문제 https://leetcode.com/problems/search-in-rotated-sorted-array/ Search in Rotated Sorted 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 풀이 난이도: Medium 이전 문제 153. Find Minimum in Rotated Sorted Array를 활용해서 해결했는데, 훨씬 깔끔하고 빠른 해결법은 다음 게시글을 참고하자. [LeetCode]C++ binary search wi..

문제 https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ Find Minimum in Rotated Sorted 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 풀이 난이도: Medium 정렬되었지만 회전된(?) 배열에서 최솟값을 찾는 문제. 정렬된 원형 힙을 생각하면 편할 것 같다. 물론 단순하게는 배열을 순서대로 탐색하는 것으로 O(n)의 알고리즘을 만들 수 있지만, O(log..

문제 https://leetcode.com/problems/maximum-product-subarray/ Maximum Product Subarray - 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나 분할 정복으로 해결하려 했지만, 답을 알고 보니 사실 스위핑으로도 해결이 가능했다... 일단, 연속되는 부분 배열의 원소에 0이 포함된다면 다른 원소들의 값과는 상관없이 0이 된다. 따라서 최대 곱이 0이 아닌 이상, 0을 포함하지..