알고리즘 분류
: 연속적인 방법으로 처리하자.
최근 풀이 : 240111 목
: 문제를 읽으면서 연속적인 데이터를 만든 후에 k번 만큼의 횟수를 반복적으로 진행하는 것이기 때문에 누적합으로 접근함.
- 일반적으로 하기에는 10만 * 10만으로 데이터 초과함.
풀이
처음에는 psum을 이렇게 만들려고 했는데 , 이런식으로 하면
-
3과 -2의 연속값인 1을 구할 수 없음. 바로 위의 그림에 있는 주석을 보자.
뭔가 규칙식을 더 생각해봄.
- 그래서 psum 인덱스를 한칸 더 당김.
: 이런식으로 구성해보면, k 값이 만약 2라고 한다면, (연속된 원소는 2개일 경우)
psum[2] - psum[0] -> 1 // psum[3] - psum[1] -> -6 ??
위의 점화식으로 진행하면 밑의 그림과 같이 표현이 가능함.
-
즉 psum만드는 점화식을 이렇게 함.
-
그리고 연속된 데이터 구하는 거를
psum[i] - psum[i - k] : k는 연속된 갯수를 의미함.
이런식으로 처리함!
- 그래서 psum 인덱스를 한칸 더 당김.
#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <map>
#include <future>
#include <thread>
#include <numeric>
#include <stack>
#include <queue>
#include <memory>
#include <set>
#include <string>
#include <stack>
#include <mutex>
#include <ostream>
int main()
{
int n, k;
cin >> n >> k;
// n은 10만 , k는 10만
// 최악의 시간복잡도는
// k는 연속적인 날짜 수 이고,
// n은 전체 날짜의 수
// 시간 복잡도는 일반적으로 하면
// 연속적인 최소 2일부터, 진행하는 것이니까
// , 여기서부터 k(10만 까지.)
/// for(int i = 0번 인덱스 ~ i < n번 인덱스(10만)
// for(int j = i + 1; j <
// 10만 * 10만 이니까
// 더하는 연속적인 수 지정할 때마다 다시 합 처리할 것임.
// -> 일반적인 생각으로는 1초안에 불가.
// 연속적인 것이기 때문에
// 누적합을 이용해볼까?
// 데이터를 넣을 때 어쩔수 없이 발생하는 n번 만큼
// 10만 넣을 때, pSum을 만들어놓고
// 빠져나와서 for문으로 k번 , 즉 10만번 만큼 돌리면서
// 2번 연속으로 진행할지?
// index 0 1 2 3 4 -> 이걸로?
// psum :3 1 -3 -12 -12
// 아래의 것으로 진행하자.
// index 0 1 2 3 4 5 -> 이걸로?
// psum : 0 3 1 -3 -12 -12
// psum[] 을 어떻게 만들것인가
// psum[i] - psum[i - j] 가 의미하는 것은
// k번째 차이인가??
// 1 이 나오멸면 psum[1]
// -6 은 psum[2] - psum[0]
// -13 나오게 하려면 psum[3] - psum[1]
// 10번 인덱스에서 5개 연속 진행하면, 반절로 줄어드니까
// 이렇게 해도 시간복잡도 성공할 듯함.
// k - 1번 연속으로 진행할지를 하면
// -> 문제에서 k번째만큼 할 것인지 정해져 있어서
// 괜한 걱정 안해도 됨.
//= ===== 이걸로
// 아래의 것으로 진행하자.
// index 0 1 2 3 4 5 -> 이걸로?
// psum : 0 3 1 -3 -12 -12
// v 3 -2 -4 -9 0 3 7 13 8 -3
vector<int> v(n);
vector<int> psum(n + 1);
for (int i = 0; i < n; ++i)
{
cin >> v[i];
psum[i + 1] = psum[i] + v[i];
}
//for (int i = 0; i < n + 1; ++i)
//{
// cout << psum[i] << " ";
//}
int ret = INT_MIN;
for (int i = k; i < n + 1; ++i)
{
// 확인용
//cout << psum[i] - psum[i - k] << " ";
if (ret < psum[i] - psum[i - k])
{
ret = psum[i] - psum[i - k];
}
}
cout << ret << endl;
}
최근 풀이 : 231122 수
- 놓친 부분
: 마지막 인덱스 계산 처리를 못함.
-> 그래서 sum 할 때마다 출력하면서 확인해서 for 문 바깥에서 한번더 max 처리 함.
알아야 할 부분 : limits.h 추가하자.
int의 최소값 표현하기 위해서 INT_MIN 을 작성했는데,
백준에서는 헤더를 추가해야 함.
필요한 헤더는 limits.h 파일임
반드시 include 하도록!
- 누적합 공식이 아니라, 그냥 내 생각대로 풀어봄.
#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <limits.h>
#include <algorithm>
int main()
{
// 10만
// k 는 10만 이하
// 5만 이라고 한다면
// 5만 * 5만임.
// 10000 10000 * 25
// 100000000
// 대충 20억임.
// startIndex = size - k 까지만 진행하자.
// 할때마다 초기화가 아니라
// 이미 누적된 값에서 처음 인덱스 변경시에
// 이전 값을 빼고, 새롭게 추가된 뒤에 놈을 추가하는
// 방법으로 접근하자.
// 이렇게 하면
// 효율적일 것 같음
int n, k;
cin >> n >> k;
vector<int>v(n);
for (int i = 0; i < n; ++i)
{
cin >> v[i];
}
int sum = 0;
int cnt = 0;
int startIndex = 0;
int result = -987654321;
for (int i = 0; i < n; ++i)
{
if (cnt == k)
{
result = max(result, sum);
//cout << sum << endl;
// max 계산 후에 맨 앞의 인덱스값 제거하자.
sum -= v[startIndex++];
}
else
{
++cnt;
}
sum += v[i];
}
//cout << sum;
result = max(result, sum);
cout << result;
}첫번째 코드
#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <algorithm>
int main()
{
// 10만
// 연속 값이 2개라고 하면 20만임.
// 비용 10만 * k임 => 입력 예제는 문제 없으나.
// 이중 포문으로 처리하면 안됨.
int n , k;
cin >> n >> k;
vector<int>v(n);
for (int i = 0; i < n; ++i)
{
cin >> v[i];
}
int mmax = -1000000;
//for (int i = 0; i <= n - k; ++i)
//{
// int temp = 0;
// for (int j = i; j < i + k; ++j)
// {
// temp += v[j];
// }
// mmax = max(temp, mmax);
//}
//cout << mmax;
int sum = 0;
vector<int>psum(n);
for (int i = 0; i < k; ++i)
psum[0] += v[i];
// i 는 1임.
// psum[i] = psum[i - 1] - v[i - 1] + v[i + k - 1];
for(int i = 1; i <= n - k; ++i)
psum[i] = psum[i - 1] - v[i - 1] + v[i + k - 1];
// 출력용임.
//for (int i = 0; i <= n - k; ++i)
// cout << psum[i] << endl;
cout << *max_element(psum.begin(), psum.end() -1);
}
// 반례 5 2
// -1 -1 -1 -1 -1 ->
-> 40% 끝남.
최종 코드
#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <algorithm>
int main()
{
int n, k;
cin >> n >> k;
vector<int>v(n + 1);
vector<int>psum(n + 1);
// 누적합을 사용하자.
for (int i = 1; i <= n; ++i)
{
cin >> v[i];
psum[i] = psum[i - 1] + v[i];
}
// 출력용 . [0]은 처리 안됨.
//for (auto iter : psum)
//{
// cout << iter << " ";
//}
//cout << endl;
// 문제를 보고 작성한 임시 코드
//int sum = psum[3] - psum[1];
//cout << sum << endl;
//
//sum = psum[2] - psum[0];
//cout << sum << endl;
int mmax = -100000000;
for (int i = 0; i <= n - k; ++i)
{
int sum = psum[k + i] - psum[i];
// 출력용
//cout << sum << endl;
mmax = max(mmax, sum);
}
cout << mmax;
}
🔥🔥🔥