누적합3 [백준 1806] 부분합 / 자바 / 투포인터 && 누적합 문제 레벨: G4알고리즘: 투포인터 && 누적합풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/18061 번째 시도 입력값을 보면 O(NS)의 시간복잡도는 안 된다는 것을 알 수 있다.그렇다면 가능성 있어 보이는 건 최대 O(NlogN) 정도이다.(일종의 꼼수) 여기서 얻을 수 있는 점은 배열을 1 ~2번 순회(적은 순회라고 생각하면 됨)정도로 답을 구해야 한다. [아이디어]나는 한 번의 배열 순회로 알아낼 수 없을까 라는 생각에서 출발했다.배열을 전부 순회할 때까지 이 과정을 반복한다.1. 15이하라면 다음 숫자를 합에 포함시킨다.2. 15이고 기존 값보다 작다면 값을 갱신한다.3. 15이상이라면 시작숫자를 합에서 제외시키고 시작숫자+1을.. 2024. 6. 13. [백준 11660] 구간 합 구하기 5 / 자바 / 누적합 문제 레벨: 알고리즘: 누적합풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/116601 번째 시도 이 문제는 이차원배열의 누적합이다.알고 가야 할 것은 일차원 배열의 누적합과 배열에 담기는 값이 다른 거이다. 혹시 O 위치의 담길 값이 ---->를 다 더한 값이라고 생각할 수 있다. 그건 틀렸다. ----------->O우린 1,1,를 좌상 꼭지점으로 O을 우하 꼭지점으로 삼는 직각삼각형의 합으로 생각해야 한다.합을 화살표 표시하고 그림으로 나타내면 아래와 같다------ --->O 위 그림을 보면서 배열에 들어가는 값을 이해해보자.빨간색 위치에 배열값은 초록색 + 파란색 - 노란색(겹치는 부분)이다. 이 공식으로 배열을 채우면 된다. .. 2024. 6. 12. [백준 11659] 구간 합 구하기 4 / 자바 / 누적합 문제 레벨: S3알고리즘: 누적합풀이시간: 16분힌트 참조 유무: 무https://www.acmicpc.net/problem/116591 번째 시도 문제를 보고 엥 이거 너무 기초적인 문제 아니야? 라고 생각했다가 제한을 보고 생각을 바꿨다. 100,000(N의 최댓값) x 100,000(M의 최댓값) = 100,000,000,000(1억 초과)이기 때문에 O(n^2) 시간복잡도로는 풀 수 없다. [아이디어]O(N) 시간복잡도를 생각해봤다. 한번에 탐색으로 1 ~ arr[i]까지 담길 배열을 만드는 것이다. 만약 3~5까지 합을 구하고 싶다면 5인덱스에 있는 값(1~5) - 2인덱스에 있는 값(1 ~ 2)로 구하면 되는 것이다.import java.util.*;import java.. 2024. 6. 12. 이전 1 다음
