하수하따 록기장

Maximum Contiguous Subsequence Sumn개의 정수 a1, a2, ..., an이 주어졌을 때 연속적인 부분수열의 합이 최대가 되는 구간의 합을 계산하시오.리트코드 사이트의 문항을 이용해 코드로 연습해보았다.https://leetcode.com/problems/maximum-subarray/📍 [방법1] Brute-force가능한 모든 부분 수열에 대해서 계산을 하고 이 중 가장 큰 합을 찾는다. index i는 부분 수열의 시작 인덱스를, j는 마지막 인덱스를 의미한다. 단순하지만 O(n^3)만큼의 시간복잡도를 가진다. 매우 효율적이지 않다.class Solution {public: int maxSubArray(vector& nums) { int n = nums..

📍알고리즘 분류: DP 동적 프로그래밍큰 문제를 작은 문제로 나눌 수 있으며 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 경우 DP를 사용한다.📍문제 풀이:처음에는 조합(Combination)을 이용한 수식으로 문제에 접근했다. 문제에서 높이는 2로 고정되어 있으므로 2xn 타일을 쪼개보면 타일을 구성할 수 있는 경우는 '2x1' 혹은 '1x2 두개를 위아래로 붙인 2x2' 뿐이다. 그래서 2x1의 모양을 A, 2x2의 모양을 B라고 하자.A는 가로를 1만큼 차지하고 B는 한번에 2만큼 차지한다. 따라서 2xn의 모양에서 n = (1 x A의개수) + (2 x B의개수)라는 수식을 세울 수 있다. A와 B의 범위는 0과 자연수이다. 따라서 A와 B의 순서쌍 조합을 구하면 이 과정에..