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

문제 https://www.acmicpc.net/problem/11570 11570번: 환상의 듀엣 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 A(상덕이)가 부른 마지막 음을 a, B(희원이)가 부른 마지막 음을 b라고하자. dp[a][b]에는 a와 b일때의 힘든정도의 최솟값을 저장하자. 이때 현재까지 두 명이 부른 음은 a와 b 중에 더 큰 값(악보상에서 더 뒤에 있는 음)이라고 할 수 있다. (모든 음은 순서대로 불러야 하므로 이는 성립할 수밖에 없다.) 그렇다면 다음으로 불러야 ..

문제 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 연속된 순서의 파일끼리만 합쳐야 한다는 조건이 없다면 우선순위 큐로 간단히 풀 수 있지만, 연속된 파일끼리 합치기 위해 다이나믹 프로그래밍(DP)를 사용해야 한다. dp[start][end]를 start ~ end까지의 파일을 연속되게 합칠 때(하나의 임시 파일로 만들 때) 최소 비용이라고 하자. 이를 구하기 위해서는 start~end 파..

문제 https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 자신의 직속 부하가 최고 상관인 서브 트리들에서의 최소 전파 시간을 구한 값을 배열에 저장한다 생각해보자. 부하의 서브 트리들 중에서 가장 전파 시간이 오래 걸리 트리는 언제 방문해야 최단 시간을 구할 수 있을까? 조금만 생각해보면 당연히 전파 시간이 오래 걸리는 순서대로 먼저 방문해야 항상 이득임을 알 수 있다. (오래 걸리는 트리를 늦게 방문할수록 ..