문제 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라고 할때, 두 ..

문제 https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 가장 큰 수와 가장 작은 수를 만드는 방법을 나누어서 생각해보자. 1. 가장 큰 수 만들기 (그리디) 가장 큰 수를 만들기 위해서는 무엇보다 수의 자릿수를 늘리는 게 최선이다. 예를 들어 성냥개비로 만들 수 있는 가장 큰 한자리 수인 9를 만들기 위해서는 6개의 성냥개비를 써야 한다. 하지만 성냥개비 6개로 1을 3개 만들어 3자리 수 111을 만드는 것..

문제 https://www.acmicpc.net/problem/2494 2494번: 숫자 맞추기 아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 역추적의 구현과 숫자 나사의 현재 상태를 구하는 것이 중요했던 DP 문제. 일단, 숫자나사는 최대 10,000개 존재할 수 있기 때문에 왼쪽으로 돌릴때 마다 하위의 나사들을 모두 변형해주는 것은 너무 비효율적이다. 사실 각 나사가 왼쪽으로 회전한 횟수만 알 수 있으면 현재의 상태를 구할 수 있다. 특히, 왼쪽으로 돌리는 것에 영향을 받지 않기..

문제 https://www.acmicpc.net/problem/1029 1029번: 그림 교환 첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 비트 마스킹을 DP에 적용하여 해결하는 문제. 외판원 순회 문제와 굉장히 비슷하니 먼저 풀어보고 오도록 합시다. 이번 문제를 외판원 순회와 같이 해결할 수 있는 이유는 문제를 약간 변형해 보면 알 수 있다. 각 예술가를 도시라고 생각하고 그림의 거래를 외판원이 도시 간의 이동하는 것으로 생각해보자. 외판원 순회 문제에서 1번 -> 2번 -..