개발일지

개요누적 합 알고리즘을 이해하고 이를 사용해서 구간 합 문제를 시간초과 없이 해결해보자. 첫번째 요소는 무조건 0으로 시작합니다. (ex. prefixSum(0, 0), arr[0][0])prefixSum(i): arr[0]~arr[i] 누적합rangeSum(i, j): arr[i]~arr[j] 구간합, 2차원 배열의 경우 rangeSum(i1, j1, i2, j2) 누적 합/구간 합 이해하기1차원 배열 누적 합/구간 합구간 합다음과 같은 배열이 존재할 때 arr[3]부터 arr[5]까지의 합을 구해보자.rangeSum(3, 5)는 prefixSum(5)에서 prefixSum(2)을 뺀 값과 같다.rangeSum(i, j) = prefixSum(j) - prefixSum(i-1) 따라서, 구간합을 빠르게..

🔗 https://www.acmicpc.net/problem/2579  동적 프로그래밍 - 타뷸레이션 방법을 사용했다. 문제 이해지켜야할 규칙은 다음과 같다.한 번에 한 계단 또는 두 계단을 오를 수 있다.연속된 세 계단을 밟을 수 없다.  마지막 도착 계단(20)을 기준으로 생각해보자. 이전 계단에서 해당 계단까지 올 수 있는 경로는 두 가지이다.  첫 번째는 이전 계단(10)을 밟지 않고 한 번에 두 계단을 오르는 경우이다.  두 번째는 이전 계단(10)을 밟을 경우다. 이 경우에는 전전 계단(25)을 밟게 되면 세 계단(25-10-20)을 연속으로 밟게 되므로 규칙을 위반하게 된다. (파란 경로) 따라서 전전전 계단(15)에서 두 계단 → 한 계단씩 오를 수 있어야한다. (빨간 경로)  구현let..

🔗 https://www.acmicpc.net/problem/24511 내장함수 pop, push, shift 사용하면 간단하겠지만 당연히 시간초과가 발생한다. stack, queue 특성 고려해서 시간초과 없이 해결해보기문제 이해.40 1 1 01 2 3 432 4 7  다음과 같이 두 개의 큐와 두 개의 스택으로 이뤄진다.A: [1] // A큐B: [2] // B스택C: [3] // C스택D: [4] // D큐 첫 번째 원소 ‘2’를 삽입 했을 때의 과정을 알아보자.‘2’를 A큐에 push A: [1, 2] → 큐이므로 ‘1’ pop A: [2]반환된 ‘1’을 B스택에 push B: [2, 2] → 스택이므로 ‘두번째 2’ pop B: [2]반환된 ‘2’를 C큐에 push C: [3, 2] ..