🫂 Prefix Sum
1D Prefix Sum✊🏻 구간 합 문제는 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 계산하는 문제 유형을 뜻한다. ✊🏻 예를 들면, 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정했을 때, 2번째 수부터 4번째 수까지의 합은 20 + 30 + 40인 90이 된다. ✊🏻 N개의 정수로 구성된 수열이 있고, M개의 query 정보가 주어진다. 각 query는 left와 right로 구성. 각 query에 대하여 [left, right] 구간에 포함된 데이터들의 합을 출력해야 한다. (수행 시간 제한은 O(N+M)) → 위 예와 접목하자면, 5개의 데이터 (N=5)로 구성된 수열에서 매번 새로운 query 구간마다 해당 합을 구한다면 시..
Computer Science/Algorithms
2024. 9. 6.
🍣 Fibonacci Sequence
🍣 유명하고 유명한 피보나치 수열(Fibonacci Sequence)은 아래와 같이 표현할 수 있다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 ...① Recursive Definition🍣 즉, Fn을 n번째 피보나치 수라고 한다면 재귀 방식으로 Fn을 아래와 같이 표현할 수 있다. F(n) = F(n-1) + F(n-2)with initial conditions F(0) = 0 and F(1) = 1 : 즉, Fn을 구할 때 Fn-1과 Fn-2를 사용해 재귀적 호출로 Fn을 정의할 수 있다. Fn을 재귀적으로 구하는 알고리즘의 시간복잡도는 O(2^n). Fn 호출에 동일 재귀함수 ..
Computer Science/Algorithms
2024. 6. 26.
