📚 알고리즘
[백준 2212] 센서_greedy(C++)
[문제] https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1> K; for(int i = 0; i > sensor[i]; } sort(sensor, sensor+N); // 기지국들의 위치 정렬 vector dist(N-1,0);//초기화해주기 귀찮아서 벡터로 받았다 배열로해도 상관없음 for(int i = 0; i < N-1; i++){ dist[i] = sensor[i+1] - sensor[i]; } sort(dist.begin(), dist.end()); int ans = 0; for(int i = 0; i< N-K; i++) ans += dist[i]; cout
[알고리즘] 동적계획법
동적 계획법 ( Dynamic Programming ) 1. 개요 동적 계획법 ( Dynamic Programming, 줄여서 DP ) 은 프로그래밍 대회에서 출제되지 않으면 이상할 정도로 높은 출제빈도를 보이고 있을 만큼 중요한 알고리즘 설계 기법입니다. 동적 계획법은 주어진 문제를 여러 개의 하위문제들로 나누어 먼저 처리한 후 그 답들을 이용해 문제를 처리하는 방법을 뜻합니다. 하위문제들을 수행할 시에는 같은 문제를 여러 번 처리하는 경우가 발생하는데 이 때, 한번 수행한 문제들의 답을 저장해 놓으면 그 다음부터는 답을 바로 알아낼 수 있어 속도가 비약적으로 빨라지게 할 수 있습니다. 2. DP 기본 예제 – 피보나치 수열 피보나치 수열은 F[0] = 0, F[1] = 1, F[i] = F[i-1] ..