목록DP (17)

Doby's Lab

[알고리즘] 백준 11659번: 구간 합 구하기 4 (C++), DP 개념

이 문제를 직관적으로 풀었을 때는 시간 초과가 발생한다. 구간이 예를 들어 1~100,000이고, 합을 구하는 횟수가 1~100,000이라면 어마한 양의 시간이 발생하기 때문에 다른 방법을 생각해내야 한다. DP (Dynamic Programming) 개념 DP란 큰 문제를 해결하기 위해 작은 문제들로 나누어 작은 문제들을 해결하여 큰 문제들 해결할 수 있도록 도와주는 알고리즘이다. 예를 들어 피보나치 수가 DP의 대표적인 문제라고 할 수 있다. 피보나치 4를 구한다고 생각해보자. 일반적으로 코드는 이렇게 짤 것이다. #include using namespace std; int fibo(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } ..
PS/BOJ 2021. 10. 5. 22:06
이전 Prev 1 2 3 Next 다음