구간 최대합 구하기

문제.

(특정 회사의 코딩테스트 문제 중 하나였는데 문제 유출은 처벌 받을 수 있다고하여 정확한 문제를 복사하지도 않았고, 그래서 적을 수도 없다. 대강 적음…) 양수의 int 숫자로 이루어진 배열이 주어지고, 배열의 요소를 순서대로 k 개씩 짝을 지어 합을 구한다. 이때 합의 최대값을 return 해라.

나의 풀이.

import java.lang.Math;

class Solution {
    public long solution(int[] numbers , int k) {
        int answer = 0;
        int length = numbers.length;
        int sum = 0;
        
        for(int i=0; i<=length-k; i++) {
            sum = 0;
            for(int j=i; j<i+k; j++) {
                sum += numbers[j];
                answer = Math.max(sum, answer);
            }
        }   

        return answer;
    }
}

코멘트.

이렇게 하니까 풀이는 통과했는데 효율성에서 빵점 맞았다. 그래서 최종 스코어는 100점 중 75점… 처음에는 첫 번째 for문을 for(int i=0; i<=numbers.length-k; i++) 이런식으로 돌렸는데 이렇게 하면 numbers.length API 호출을 매번 하게되는 비효율이 발생한다고 해서 그나마 고쳤다. 하지만 그래도 효율성 점수는 빵점…

무엇이 가장 문제였을까? 잘은 몰라도 이중 for 문을 돌리는 것 자체가 문제인 것 같긴한데… 그럼 이걸 어떻게 개선할 수 있을까?

프로그래머스에서 가장 비슷한 문제 유형을 살펴보며 대충 통밥(?)을 때려보니 탐욕 알고리즘 또는 Dynamic Programming, 동적계획법으로 해결했어야 하는 것 같은데…

그리하여 공부해보는,

탐욕알고리즘.

탐욕이라는 이름은 각 단계의 부분 문제를 풀 때 근시안적으로 최적해를 구한다고 해서 붙여진 것이다.

동적 계획법은 최적의 해를 구하긴 하지만 탐욕 알고리즘보다는 덜 효율적(대개 더 많은 수행 시간 요구)이다. 반면에 탐욕 알고리즘은 동적 계획법보다 효율적이기는 하지만, 동적 계획법처럼 반드시 최적이 해를 구해준다는 보장은 하지 못한다.

탐욕 알고리즘은 다음의 3단계로 동작한다.

해 선택
실행 가능성 검사
해 검사

ㅠㅠ 소화하는 데 시간이 좀 필요하다 ing