[알고리즘][누적합] 슬라이딩 윈도우 알고리즘(Sliding Window Algorithm), 카데인 알고리즘(Kadane`s Algorithm), 원형 배열 부분집합 최대 합 구하기 - 컴도리돌이

반응형

---

오늘 기업 코테를 보았다.

누적합에 대해 2문제씩이나 출제가 되었다.

문제를 다 풀긴 했지만

효율성에서 어떻게 될지 모르겠다.

오늘 코테 풀이에 아쉬움이 남아서

누적합에 대해 

다시 돌아보는 시간을 가져보자.

---

코테의 첫 번째 누적 합의 문제는

연속된 k개의 값들의 합 중에서 가장 큰 값을 출력하는 문제였다.

나는 해당 문제를

슬라이딩 윈도우 알고리즘으로 해결하였다.

슬라이딩 윈도우 알고리즘(Sliding Window Algorihtm)은 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 유용한 알고리즘이다.

예르 들어 정수로 이루어진 배열 {1, 4, 2, 5, 1}에서 길이가 2인 서브 배열의 합계가 가장 큰 서브 배열을 구할 때, 해당 알고리즘을 이용해서 해결한다.

슬라이딩 윈도우는 크기가 고정적인 창문(특정 범위)을 옆으로 밀면서 이동하는 방식이다. 그리고 매 순간 창문을 통해 보이는 세상 속에서 정보(합)를 유출한다.

 

유사한 문제가 백준에 존재하기에

링크를 아래에 걸어놓았다.

 

21921번: 블로그

 

백준 21921 문제의 해결 코드는 다음과 같다.

 

---

두 번째 문제는 연속하는 부분집합의 합 중에서 

가장 큰 값을 출력하는 문제였다.

특이한 점은 주어진 배열이 

원판형으로 이루어져 있다.

 

주어진

배열 [-1, 3, 2, -6 , 4]에서

연속한 부분집합 합에서 가장 큰 값은

[-1, 3, 2, -6, 4]

강조된 연속된 부분집합 [-1, 3, 2, 4]의 합인

8을 출력해야 했다.

 

해당 문제는 코테를 끝나고서

구글링을 해보니

카데인 알고리즘(Kadane`s Algorithm)을

이용하면 쉽게 해결할 수 있었다.

 

지금까지

알고리즘 문제를 많이 풀었다고 

생각했지만,

늘 새로운 알고리즘이 

날 맞이해준다.

너무 기쁘다.🥲

---

최대 합 원형 부분배열