전체 글

슬라이딩 윈도우 슬라이딩 윈도우란 일정한 길이를 이동시키면서 조건에 맞는 값을 찾는 알고리즘입니다. 배열에서 일정 범위의 합을 비교할 때 매우 유용한 방법으로, 값을 이동시킬 때 배열의 처음 값을 제거하고 배열의 마지막 값을 더해주기만 하면 되는데, 배열의 모든 값을 불러와서 더하는 연산을 피할 수 있어 매우 효율적입니다. 양 옆에 지점을 둔다는 점에서 투 포인터와 비슷한 점이 있지만, 투 포인터는 범위가 유동적으로 변하지만, 슬라이딩 윈도우는 범위가 고정되어 있다는 점이 차이점입니다. 다음은 투 포인터를 그림으로 표현한 예시입니다. 조건에 따라 범위가 유동적으로 변경되는 것을 볼 수 있습니다. 다음은 슬라이딩 윈도우를 그림으로 표현한 예시입니다. 범위는 항상 고정되어 있고, 배열은 좌우로만 이동합니다.

투 포인터 투 포인터란, 배열에서 원래 이중 for문으로 O(N^2)으로 처리되는 작업을 2개의 포인터를 통해 O(N)으로 해결해주는 알고리즘입니다. 여기서의 포인터는 C언어에서의 포인터의 개념이 아니라, 해당 지점을 의미하기 위해 사용되는 개념입니다. 이중 for문으로 처리할 때 주로 i가 계산되고, 그 안에서 j가 계산되는데, j가 계산될 때 i에 대한 정보가 쓰이지 않습니다. 하지만 투 포인터 같은 경우에는 i에 대한 정보를 사용하여 포인터를 이동시킵니다. 투 포인터 문제는 이분 탐색으로도 풀 수 있는 경우가 많고, 그 반대의 경우 또한 많습니다. 투 포인터 문제는 크게 두 가지 유형이 있습니다. 정렬 후 양 옆에서 다가오는 것 left, right를 지정하고, 상황에 따라 left나 right가 ..

[Silver II] 스택 수열 - 1874 문제 링크 성능 요약 메모리: 75604 KB, 시간: 176 ms 분류 자료 구조, 스택 문제 설명 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 ..

[Silver I] 겹치는 건 싫어 - 20922 문제 링크 성능 요약 메모리: 84644 KB, 시간: 88 ms 분류 두 포인터 문제 설명 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. 100,000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자. 입력 첫째 줄에 정수 N(1≤N≤200,000)과 K(1≤K≤100)가 주어진다. 둘째 줄에는 a1,a2,...an{a_1, a_2, ... a_n}이 주어진다 (1≤ai≤100..

[Silver III] 블로그 - 21921 문제 링크 성능 요약 메모리: 84696 KB, 시간: 92 ms 분류 누적 합, 슬라이딩 윈도우 문제 설명 찬솔이는 블로그를 시작한 지 벌써 N일이 지났다. 요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다. 찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다. 찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자. 입력 첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다. 둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다. 출력 첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대..

[Silver IV] 스택 - 10828 문제 링크 성능 요약 메모리: 69500 KB, 시간: 28 ms 분류 자료 구조, 구현, 스택 문제 설명 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1..

[Gold V] 행복 유치원 - 13164 문제 링크 성능 요약 메모리: 100712 KB, 시간: 200 ms 분류 그리디 알고리즘, 정렬 문제 설명 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다. 이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자. ..

[Silver II] A → B - 16953 문제 링크 성능 요약 메모리: 81480 KB, 시간: 304 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색, 그리디 알고리즘 문제 설명 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. 입력 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. 출력 A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다. 풀이 i) 해당 문제는 BFS를 통해 해결하고자 하였습니다. 첫 번째 값에서 나타날 수 있는 값들을 추가하고, 방문 여부를 체크하면서 만약 구하고자 하는 값..