분류 전체보기

[알고리즘] 슬라이딩 윈도우(Sliding Window)

소개슬라이딩 윈도우(Sliding Window)란?슬라이딩 윈도우(Silding Window)는 배열이나 리스트와 같은 자료구조 내에서 일정한 크기의 서브 리스트나 서브 배열을 이동시키며 문제를 해결하는 기법이다. 이 방법은 연속적인 데이터 구간을 효율적으로 처리할 수 있게 한다. 정의슬라이딩 윈도우는 고정된 크기의 윈도우(부분 집합)를 자료구조(주로 배열이나 문자열)에 적용하며, 윈도우를 한 칸씩 이동시키며 각 위치에서의 부분 집합을 처리하는 알고리즘 기법이다. 주로 배열의 특정 구간에 대한 합, 평균, 최대/최소 값을 구하거나 문자열의 패턴 매칭 등에 사용된다. 기본 개념슬라이딩 윈도우의 핵심 개념은 다음과 같다. 윈도우 설정 : 초기 윈도우를 설정한다. 이 윈도우는 처리할 데이터의 부분 집합을 나타..

[백준(BOJ) / C++][Silver Ⅳ] 1940번 : 주몽

문제https://www.acmicpc.net/problem/1940풀이정렬 알고리즘으로 계산하기 편하게 정렬한 후 start_point 하고 end_point 의 합을 M과 비교하며 크면 end_point를 줄이고 작다면 start_point를 올리며 만약 M과 같았을때 count에 1를 더하며 start_point, end_point 각각을 +1, -1을 해준다.소스코드 #include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; int count, start_point, end_point; cin >> N >> M; vect..

[백준(BOJ) / C++][Silver Ⅴ] 2018번 : 수들의 합 5

문제https://www.acmicpc.net/problem/2018풀이1. 숫자를 가리키는 포인터 두개(start_index, end_index)를 준비한다.2. 해당 포인터 사이의 값(sum)에 따라 포인터를 옮겨준다.2-1. sum > Nsum의 값이 N 보다 높을 경우 sum의 값을 현재 start_index 값만큼 줄여주고 start_index 값을 올려준다.sum = sum - start_index;start_index++;2-2. sum sum의 값이 N 보다 작을 경우 end_index 를 높여주고 그 후 end_index의 값을 더해준다.end_index++;sum = sum + end_index;2-3. sum == Nsum의 값이 N과 같을 경우 해당 합은 맞다는 뜻이므로 count를..

[백준(BOJ) / C++][Gold Ⅲ] 10986번 : 나머지 합

문제https://www.acmicpc.net/problem/10986풀이해당 문제는 구간 합, 경우의 수를 알고있다면 풀 수 있는 문제 입니다.소스코드#include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; cin >> N >> M; vector S(N, 0); vector C(M, 0); long answer = 0; cin >> S[0]; for(int i = 1; i > temp; S[i] = S[i-1] + temp; } for(int i = ..