목록슬라이딩 윈도우 (6)

1일1알

백준 12847번 꿀 아르바이트 C++

https://www.acmicpc.net/problem/12847 12847번: 꿀 아르바이트 월세를 내기 바로 전 날 까지 인 n (1 ≤ n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다. 그 다음 줄 에는 1일부터 n일 까지 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000) www.acmicpc.net 정해진 구간만큼의 합을 슬라이딩 윈도우로 구하면서 최대값을 찾았다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using nam..
알고리즘 2023. 3. 19. 10:06
백준 21921번 블로그 C++

https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 누적 합, 슬라이딩 윈도우 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, x; vect..
알고리즘 2023. 2. 11. 14:06
백준 10025번 게으른 백곰 C++

https://www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 슬라이딩 윈도우 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; vector v(1000001, 0); int main() { io..
알고리즘 2022. 11. 24. 19:46
백준 15565번 귀여운 라이언 C++

https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 슬라이딩 윈도우 큐를 이용하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, k; v..
알고리즘 2022. 11. 15. 10:09
백준 1644번 소수의 연속합 C++

에라토스테네스의 체를 이용해서 소수만 들어가있는 배열을 만들고 그 배열에서 투 포인터를 이용해서 누적합이 n보다 작으면 오른쪽 포인터를 증가시키고 반대면 왼쪽 포인터를 증가시키면서 누적합이 n과 같은 경우의 수들을 찾았다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n; vector isPrime; vector primes; int main() { ios_base::sync_with_stdio(false)..
알고리즘 2022. 7. 19. 10:48
백준 2531번 회전 초밥 C++

연속으로 k개의 초밥을 먹고 쿠폰에 쓰여있는 초밥까지 먹었을 때 최대 몇 가지의 초밥을 먹을 수 있는지를 구하는 문제이다. 우선 마지막 초밥에서 처음 초밥으로 이어지기 때문에 초밥의 정보를 저장하는 배열에 처음부터 k-1개만큼 더한 배열을 만들었다 예제의 입력을 예로 들면 7 9 7 30 2 7 9 25 의 배열에 k-1 즉 3개를 처음부터 더한 배열 7 9 7 30 2 7 9 25 7 9 7 을 만들었다. 이렇게 하면 마지막 원소 25부터 4개를 먹었을 때 25 7 9 7로, 마지막에서 처음으로 돌아가는 것과 같다. 그리고 unordered_map을 로 만들고 k개만큼을 슬라이딩 윈도우 방식으로 탐색하면서 새로운 초밥이 들어오면 초밥을 추가하고, 원래 있던 초밥이 또 들어오면 해당 초밥의 개수를 증가시..
알고리즘 2021. 11. 6. 16:07
이전 Prev 1 Next 다음