https://school.programmers.co.kr/learn/courses/30/lessons/92344?language=java 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr   이 문제를 접하고 우선 구현가능한지 시간복잡도 계산을 해보았고 최대 1000*1000 배열에 1000*1000 size의 skill 25만개 기준 2500억즉 시간초과로 불가능할것 같아 여러 방면으로 고민하고 문제 풀이방법을 찾아보았지만 찾을 수 없었다. 그러던 와중 아래의 블로그를 참고하여 풀이방법을 알아낼 수 있었고아래의 블로그에서 제시한 '누적합' 알고리즘을 활용하여 쉽게 풀이할 수 있었다. '누적합' 알고리즘..

https://www.acmicpc.net/problem/1806   이번 문제는 배열에서 연속 부분합이 SSS 이상이 되는 최소 길이를 구하는 문제다.먼저 배열의 크기 NNN과 목표 합 SSS를 입력받고 배열 arr를 생성한다.이후 배열의 최댓값을 maximum에 저장하고,누적 합을 계산할 배열 dp를 초기화한다. 누적 합 배열은 0부터 iii까지의 합을 저장하며, 이를 이용해 특정 구간의 합을 빠르게 계산할 수 있다고 생각했다.find 메서드는 연속 부분합의 길이를 1부터 NNN까지 늘려가며 모든 구간을 탐색한다. 탐색 중 누적 합이 SSS 이상이 되는 구간이 발견되면 해당 길이를 반환하고 종료한다.만약 모든 구간을 탐색해도 조건을 만족하는 구간이 없다면 0을 반환한다.마지막으로 계산된 최소 길이를 ..