sliding window
-
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) 달려라 홍준 (1306 번)알고리즘/백준 2021. 1. 26. 19:11
달려라 홍준 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 www.acmicpc.net 슬라이딩 윈도를 공부하기 위해 푼 문제였다. 슬라이딩 윈도는 주로 두 개의 네트워크 호스트간의 패킷의 흐름을 제어하기 위한 방법으로 사용된다. 고정된 크기의 윈도우가 전체 범위에서 움직이는 방식이다. 배열로 된 예시를 통해 이해하는게 더 수월했다. 위와 같은 배열에서 3의 크기로 전체를 탐색하는 경우 사용한다고 생각하면 편하다. 여러 블로그를 찾아봤는데, 슬라이딩 윈도의 핵심은 이전 값에 대해 중복되는 부분을 재사용한다는 것이..