TIL

누적합

누적합이란?

나열된 수의 누적된 합.
수가 구간 [1,n]에 나열되어있으면 그 수열에대해서 구간 [1,1],[1,2],[1,3]…[1,n]을 저장하는 리스트에 저장한 후 index로 접근해 차이를 이용해 구간합을 계산
ex) 1-n까지 항이 있을 때, 5번째부터 10번째를 구하고싶으면 [1,10]에서 [1,4]를 빼면 된다.

사용 예시

• 구간합 구할 때
  시간을 줄일 때 누적합을 이용하기도 한다.
  수열에서
  Sn-Sn-3 = an + an-1 + an-2
  0으로 패딩을 줘서 사용하면 불필요한 분기점이 생기는 것을 막을 수 있다.
• 카운팅 정렬

탐색의 순서를 고려

반드시 앞에서부터 탐색할 필요는 없다.
BOJ-2493-탑
문제는 앞에서부터 접근하는 방법도 있지만, 뒤에서부터 접근하는 방식도 좋아보인다.

재귀호출을 다룰 때

재귀호출 스택 트리를 그려볼 때, 매개변수를 통해서 살펴보고 중복을 제거해줘야한다.

visited로 체크할 때

방문함을 체크해서 불필요한 연산을 줄이는 것 이외에도 불필요한 연산을 줄이는 과정에서 생기는 값들까지 이용해서 memoization을 적용하면 코드를 최적화 할 수 있다.