COMITO

문제 N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다. 입력 첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두 번째 줄에 n개의 정수가 주어진다. 출력 연속된 부분을 선택하였을 때의 최댓값을 출력한다. 예제 입력 8 2 3 -5 8 -3 4 2 -9 예제 출력 11 예제 입력 5 -1 -2 3 -2 4 예제 출력 5 문제해결의 절차 1. 문제를 정확히 이해한다. 2. 문제를 해결하는 알고리즘을 개발한다.(설계) 3. 알고리즘이 문제를 해결한다는 것을 수학적으로 증명한다. 4. 알고리즘이 제한 시간내에 동작한다는 것을 보인다.(시간복잡도) ..

- 동적 계획법(Dynamic Programing) -> 입력 크기가 작은 부분의 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분문제를 해결하여 최종적으로 전체 문제를 해결하는 알고리즘. -> 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 -> Memorization 기법을 사용 : 프로그램 실행 시 이전 단계에서의 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행속도를 빠르게하는 기술. -> 문제를 잘게 쪼갤 때, 부분문제는 중복되어 재활용됨. ex)피보나치 수열 - 분할정복(Divide and Conquer) -> 문제를 나눌 수 없을 때까지 나누어서 각각 풀면서 다시 합벼하여 문제의 답을 얻는 ..