슬라이딩 윈도우
-
BOJ) 보석알고리즘/백준 2021. 2. 5. 00:16
보석 2492번: 보석 첫째 줄에 4개의 정수 N, M, T, K가 빈칸을 사이에 두고 주어진다. N은 지도의 너비를 나타내고, M은 지도의 높이를 나타낸다(1 ≤ N, M ≤ 1,000,000). T는 금강석의 개수를 나타내고, K는 정사각형의 크 www.acmicpc.net 정말 어려운 문제였다. M by N 크기의 map이 주어지는데, 이 맵에 금강석이 묻혀있는 정보가 주어진다. n과 m은 1 ~ 1,000,000의 숫자로 주어지고, 금강석은 최대 100개 까지 주어진다. 또한, 정사각형의 한 변의 길이가 되는 k가 주어지는데, 이 정사각형을 임의로 맵에 그렸을 때, 가장 많은 금강석을 갖게되는 정사각형의 왼쪽 위 꼭짓점의 위치와 금강석의 개수를 출력하는 문제다. 우선, 이 문제가 슬라이딩 윈도우로..
-
BOJ) 좋은 친구 (3078 번)알고리즘/백준 2021. 2. 2. 18:37
좋은 친구 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 문제다. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구 라고 정의하고 있다. 또한, 이름의 길이는 2 ~ 20 사이이다. 풀이 먼저, 이름의 길이에 따라 학생을 저장할 배열 bestFriends와 Sliding Window를 도와줄 Queue를 초기화했다. 위의 배열에는 이름의 길이가 2 ~ 20까지인 학생들이 몇명인지 ..
-
BOJ) 최솟값 찾기 (11003 번)알고리즘/백준 2021. 1. 29. 16:36
최솟값 찾기 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 슬라이딩 윈도우를 이용하는 문제로, N개의 수와 윈도의 크기 L이 주어진다. D(i) = A(i-L+1) ~A(i) 중의 최솟값이라고 할 때, D에 저장되는 값을 출력하는 문제다. 즉, 자신의 위치에서 L칸 앞선 칸들 중 최솟값을 찾는 문제다. 처음에는 우선순위 큐로 시도하다가, 시간초과가 떴다. 아무래도 최악의 경우에는 O(N)이 추가돼서 그런 것 같다. (while을 통해 인덱스 범위를 검증하는 과정) 그래서 Deq..