문제 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을 포함하지..

문제 https://leetcode.com/problems/maximum-subarray/ Maximum 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 풀이 난이도: Easy 부분배열[start, end]의 시작을 start, 끝을 end라고 하자. end를 +1씩 증가시켜 원소를 하나씩 부분 배열에 추가시킬때 사실 end가 음수의 값이더라도, 부분배열의 합(sum)이 여전히 양수라면 해당 음수는 부분 배열에 추가시켜 이어나갈 가치가 있다. ..

문제 https://leetcode.com/problems/product-of-array-except-self/ Product of Array Except Self - 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 주어지는 배열에서 자신(nums[i])의 값을 제외한 나머지 값을 곱한 값을 answer[i]로 구하는 문제이다. 단, 제한사항으로 풀이의 알고리즘은 O(n)의 시간 복잡도를 가지고 나눗셈 연산을 사용해서는 안된다. You ..

문제 https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ Best Time to Buy and Sell Stock - 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 간단한 배열 문제. 미래에 산 주식을 과거에 팔 수는 없으니 현재 시점(day)이나 그 이전에 구매한 주식을 미래에 팔아야 한다. 마지막 날을 Dday, 현재를 day라고 하고 배열을 역순으로 진행해보자. Dday에서..

문제 https://leetcode.com/problems/two-sum/ Two Sum - 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 브루트 포스로도 간단히 해결 가능한 문제이지만 정렬 후 스위핑 알고리즘을 적용하여 훨씬 빠르게 해결 가능한 문제이다. 주어진 배열을 오름차순으로 정렬하고 가장 왼쪽끝(left)은 가장 작은 수이고 가장 오른쪽 끝(right)은 가장 큰 수 일 것이다. 이 두 수를 합한 수 add_num라고 할때, 두 ..