연속 부분 최대합으로 알아보는 완전탐색과 시간복잡도

완전 탐색이란?

가능한 모든 경우를 살펴보는 과정.

주어진 문제에 대한 해결책을 찾기 위해 가능한 모든 경우를 시도하고, 그 중에서의 최적의 해결책을 찾는 알고리즘

모든 가능성을 다 검토하기 때문에 확실한 정확도를 가지지만, 경우의 수가 많은 경우 계산 시간이 길어질 수 있다.

 

연속 부분 최대합 문제

숫자의 리스트가 있을 때 연속된 부분을 선택할 때 그 최대합 출력하기

1

2

-4

5

 

먼저 연속된 부분의 길이가 한 칸인 경우는 4가지 (1 / 2 / -4 / 5) 그래서 연속된 부분의 합은 각각 1, 2, -4, 5가 가능하다.

연속된 부분의 길이가 두칸인 경우는 3가지 (1, 2 / 2, -4 / -4, 5) 그래서 합은 각각 3, -2, 1이 가능하다.

연속된 부분의 길이가 세칸인 경우는 2가지 (1, 2, -4 / 2, -4, 5) 그래서 합은 각각 -1, 3이 가능하다.

연속된 부분의 길이가 네칸인 경우는 1가지 (1, 2, -4, 5) 그래서 합은 4가 된다.

 

그렇기 때문에 연속된 부분의 합 중 가장 큰 값은 5가 된다.

위처럼 4 + 3 + 2 + 1 총 10가지의 경우가 가능한 걸 모두 확인했는데

이렇게 가능한 모든 경우를 확인하는 과정은 완전 탐색이라고 한다.

 

이를 코드로 표현하면

function maxSubarraySum(arr) {
    let maxSum = -Infinity;

    // i는 연속 부분의 시작 인덱스
    for (let i = 0; i < arr.length; i++) {
        // j는 연속 부분의 끝 인덱스
        for (let j = i; j < arr.length; j++) {
            let currentSum = 0;

            // 현재 부분 리스트의 합 계산
            for (let k = i; k <= j; k++) {
                currentSum += arr[k];
            }

            // 최대값 갱신
            maxSum = Math.max(maxSum, currentSum);
        }
    }

    return maxSum;
}

 

이 코드는 세개의 중첩된 반복문을 사용하지만, 이 방법은 시간 복잡도가 매우 비효율적이므로 문제에 따라 더 효율적인 알고리즘을 사용하는 것이 좋을 수도 있다.

 

시간 복잡도

시간 복잡도는 코드가 동작하는데 걸리는 시간을 수학식으로 표현한 것으로 낮은 시간 복잡도를 가질 수록 좋다.

 

상수 시간 복잡도(O(1))

알고리즘 실행 시간이 입력 크기에 영향을 받지 않고 항상 일정한 시간이 걸리는 경우를 의미.

실행이 단번에 완료된다면, 상수 시간 복잡도라고 한다.

 

 

로그 시간 복잡도(O(log N))

알고리즘 실행시간이 입력의 로그에 비례하여 증가하는 경우.

주로 정렬된 배열에서 특정 값을 찾는데 사용한다.

 

 

선형 시간 복잡도(O(N))

알고리즘 실행 시간이 입력 크기에 선형으로 비례하여 증가하는 경우.

입력이 N개인 경우 행 시간은 대략 N에 비례한다. 배열의 각 요소를 한 번씩 확인하는 간단한 반복문이 선형 시간 복잡도를 갖는다.

 

 

선형 제곱 시간 복잡도(O(N^2))

알고리즘 실행 시간이 입력 크기의 제곱에 비례하여 증가하는 경우.

이는 보통 중첩된 반복문이 사용되는 경우 발생한다.

선형적 시간 복잡도와 비슷해보이지만, 선형 제곱 시간 복잡도는 선형적 시간 복잡도의 제곱만큼 시간이 걸린다.

 

 

 

시간 복잡도는 이 4가지만 있는것은 아니지만,

상수, 로그, 선형, 선형제곱 총 4개의 시간 복잡도 중에서 상수 시간 복잡도가 가장 낮고,

로그, 선형, 선형제곱 순서로 높아진다.

 

높은 시간 복잡도의 알고리즘은 느리고 비효율적,

낮은 시간 복잡도의 알고리즘은 빠르고 효율적이라는 점 기억하기!

 

 

 

Reference 엘리스