차곡차곡

https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 2차원 배열에 두 좌표(r1,c1) (r2,c2)사이의 값을 type에 따라 감소 또는 회복 시켜야한다. type == 1 이면 degree만큼 감소한다. type == 2 이면 degree만큼 회복한다. 모두 마친 후 0 이상인 좌표의 갯수를 return해준다. 시간 복잡도는 O(1)로 해결해야 한다. 접근법 브루토 포스로 해결할 경우 시간 복잡도가 O(N*M*K)이므로 시간초과 발생..

누적합 구간의 누적합을 구하는 문제이다. 배열의 각 원소까지의 누적 합을 미리 계산해 놓은 배열을 생성하는 기법이다. 장점 배열 특정가간의 합을 빠르게 계산할 수 있다. 이론 구간 합 알고리즘을 활용하려면 우선 누적 합 배열을 구해야 한다. 0번 인덱스에는 0을 저장하고 1번 인덱스 부터 배열을 담아야 한다. 누적 합 배열 arr를 구할 때 아래와 같이 구한다. // 1차원 배열 arr[i] = arr[i-1] + inputArr[i] // 2차원 배열 arr[i][j] = inputArr[i][j] + arr[i-1][j] + arr[i][j-1] + arr[i-1][j-1] 누적 합 배열 arr를 이용해 구간 합을 구하자고 할때에는 아래와 같이 구한다. // 1차원 배열 arr[end] - arr[s..