슬라이딩 윈도우 슬라이딩 윈도우란 일정한 길이를 이동시키면서 조건에 맞는 값을 찾는 알고리즘입니다. 배열에서 일정 범위의 합을 비교할 때 매우 유용한 방법으로, 값을 이동시킬 때 배열의 처음 값을 제거하고 배열의 마지막 값을 더해주기만 하면 되는데, 배열의 모든 값을 불러와서 더하는 연산을 피할 수 있어 매우 효율적입니다. 양 옆에 지점을 둔다는 점에서 투 포인터와 비슷한 점이 있지만, 투 포인터는 범위가 유동적으로 변하지만, 슬라이딩 윈도우는 범위가 고정되어 있다는 점이 차이점입니다. 다음은 투 포인터를 그림으로 표현한 예시입니다. 조건에 따라 범위가 유동적으로 변경되는 것을 볼 수 있습니다. 다음은 슬라이딩 윈도우를 그림으로 표현한 예시입니다. 범위는 항상 고정되어 있고, 배열은 좌우로만 이동합니다.
[Silver II] 스택 수열 - 1874 문제 링크 성능 요약 메모리: 75604 KB, 시간: 176 ms 분류 자료 구조, 스택 문제 설명 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 ..
[Silver IV] 스택 - 10828 문제 링크 성능 요약 메모리: 69500 KB, 시간: 28 ms 분류 자료 구조, 구현, 스택 문제 설명 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1..
[Gold IV] 스카이라인 쉬운거 - 1863 문제 링크 성능 요약 메모리: 79648 KB, 시간: 24 ms 분류 자료 구조, 스택 문제 설명 도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다. 정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ..
[Gold V] 탑 - 2493 문제 링크 성능 요약 메모리: 106148 KB, 시간: 380 ms 분류 자료 구조, 스택 문제 설명 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에..
[Silver IV] 괄호 - 9012 문제 링크 성능 요약 메모리: 69100 KB, 시간: 8 ms 분류 자료 구조, 스택, 문자열 문제 설명 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 V..
