반응형 Kadane's algorithm1 Kadane's algorithm 이란? (설명) 코딩 문제를 풀다보면 이런 문제가 나옵니다. "배열 A의 요소들 중 연속된 합이 가장 큰 수를 구하시오" "배열 A의 요소들 중 연속된 합이 가장 큰 배열 요소의 범위를 구하시오" 배열 요소중 양수만 있을 경우 모두 다 더해주면 되지만 음수가 들어가면 머리가 복잡해 집니다. 직관적으로 풀어버리면 이중 for문을 사용해 각 범위마다 값을 구한 후 구한 값들 중 가장 큰 값을 구해야 합니다. 하지만 이는 O(n^2)이 되버리며 코딩 문제에서도 이러한 답은 원하지 않습니다. 그리고 이러한 문제는 흔히 볼 수 있으며, 코딩 테스트를 준비하고 있는 분들이라면 기본적으로 손쉽게 풀 수 있어야 한다고 생각합니다. 위 문제들은 O(n)으로 풀 수 있는데 Kadane's algorithm을 사용하면 됩니다. 위 식이 K.. 2019. 11. 19. 이전 1 다음 728x90 반응형
