DeFacto-Standard IT

- 문제 다음 배열이 있다고 가정해보자. [-2, 1, -3, 4, -1, 2, 1, -5, 4] 이 때, 배열 내부의 연속된 서브 배열 중 합이 가장 큰 경우를 리턴 예를 들어, [4, -1, 2, 1]의 합은 6으로 서브 배열 중 합이 가장 크다. - 풀이 우선 for문을 1자리 중에서 최대값을 찾고, 2자리 중에서 내부 for문을 돌면서 찾으면 성능이 나오지 않는다. 여기서 카데인 알고리즘을 적용하면 배열을 한 번만 순회하여 O(n)의 시간복잡도로 해결할 수 있다. 일반적으로 배열을 순회하면서 1. 1자리의 합을 모두 구해서 최대값을 구함 2. 2자리의 합을 모두 구해서 최대값을 구함 ... n. n자리의 합을 모두 구해서 최대값을 구함 등과 같이 생각했다면, 이 문제는 정답은 나올지언정 성능은 나..

- 개념 계산한 결과가 이후에 또 다시 필요할 경우, 재계산하지 않고 저장해놨다가 다음 계산에 재사용하는 알고리즘. - 대표적인 문제 LeetCode - 53. Maximum Subarray