알고리즘

문제오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상..

알고리즘 문제를 해결하는 도중에 해결하기 어려운 부분이 있었습니다.하나의 1차원 배열을 예로 들어보겠습니다.[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]위처럼 1차원 배열이 존재합니다. 이 때, 구간별 변경값이 주어집니다.배열의 인덱스 2부터 7까지 3을 더한다.이 때 어떻게 계산해야할까요?for문을 통한 계산가장 먼저 드는 생각은 for문을 통해 2부터 7까지 각각 3을 더해주는 방법입니다. 배열의 길이가 N이고 변경값이 M회 주어진다면, 시간복잡도는 $O(N * M)$입니다.이를 더 빠르게 계산하는 방법은 없을까요?이런 경우, 누적합 을 이용할 수 있습니다.누적합을 이용한 구간 변화예시를 통해 설명해보겠습니다.array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]위 배열에 ..