양양의 게임개발

슬라이딩 윈도우(Sliding Window) 알고리즘 투 포인터의 일종으로 윈도우(Start~End 구간)을 한칸씩 이동하며 문제를 해결하는 알고리즘이다. 슬라이딩 윈도우 알고리즘의 두 포인터는 배열 전체를 최대 한번씩만 이동하기 때문에 시간 복잡도는 O(n)이다.윈도우의 크기는 고정일수도 있고 가변일 수도 있다. 고정 윈도우(Fixed Window)윈도우 크기 K가 고정되어있어 K 크기 만큼의 윈도우를 한칸씩 밀며 탐색을 수행한다. End - Start + 1 = K의 관계가 유지되며 보통 슬라이딩 윈도우 라고 하면 고정 윈도우를 의미한다.가변 윈도우(Variable Window조건에 따라 Start와 End가 자유롭게 움직이며 윈도우의 크기가 변할 수 있다. 조건에 만족할 때 까지 end를 늘..

큐 (Queue)큐는 FILO(First In First Out, 선입선출) 구조로 가장 먼저 넣은 데이터가 먼저 나오는 자료구조이다. std::deque기반의 컨테이너 어댑터로 list, vector등 다른 컨테이너로 변경해서 사용하는 것도 가능하다. 삽입과 삭제 연산은 항상 front, back위치에서 이루어지기 때문에 모든 연산의 시간 복잡도는 O(1)이다.멤버함수설명push(const T& value)큐의 맨 뒤에 데이터 추가pop()큐의 맨 앞 요소 제거 (리턴값 없음)front()맨 앞 요소 참조 반환back()맨 뒤 요소 참조 반환empty()큐가 비었는지 확인size()큐 크기 확인emplace(args...)새 요소를 생성 후 큐의 맨 뒤에 삽입 (C++11) 큐 기본 코드#includ..