꽤 유명하고 쉬운 알고리즘인데, 백준의 단계별로 풀어보기에는 이 항목이 없다. 그 이유는 투 포인터나 얘나 그놈이 그놈이고 투 포인터가 슬라이딩 윈도우의 상위호환느낌이라 그런 것 같다
슬라이딩 윈도우라는 단어는 컴퓨터 네트워크 과목에서 이미 접한 적이 있다. TCP통신을 할 때, 패킷을 주고받기 위해서는 버퍼가 필요하고 그 버퍼를 window라고 부른다. congestion control을 위해 window의 크기는 늘어나기도 하고 줄어들기도 한다
그렇지만 컴퓨터 알고리즘에서 말하는 슬라이딩 윈도우는 window의 크기가 변하지 않는다는 점에서 컴퓨터 네트워크 과목의 sliding window와 다른 듯 하다
그런데 그러면 투 포인터라는 슬라이딩 윈도우의 상위호환이 있는데, 슬라이딩 윈도우라는 용어가 컴퓨터 알고리즘에 필요할까 싶다
그래서 백준의 단계별로 풀어보기에는 슬라이딩 윈도우라는 항목이 없는 것 같다.
투 포인터는 지금까지의 경험상 그리디 알고리즘이나, 이분탐색(매개변수탐색) 이랑 많이 엮였다(이분탐색의 경우 l과 r 두개의 포인터를 이용) 누적합 문제도 좌측 포인터와 우측 포인터를 이용해 구간의 합을 계산한다는 점에서 투 포인터로 볼 수 있겠다.
관련 문제
블로그 : 슬라이딩 윈도우의 정석문제이다. 투포인터로도 풀린다. 2중 loop로는 풀리지 않는다. 시간복잡도를 계산해보자
https://www.acmicpc.net/problem/21921
21921번: 블로그
첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다
www.acmicpc.net
용액 시리즈 : 투 포인터 하면 딱 이녀석들부터 생각난다
https://www.acmicpc.net/problem/2470
2470번: 두 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00
www.acmicpc.net
https://www.acmicpc.net/problem/2467
2467번: 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -
www.acmicpc.net
https://www.acmicpc.net/problem/2473
2473번: 세 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상
www.acmicpc.net
11003:최솟값 찾기(쉬운 플래5) https://www.acmicpc.net/problem/11003 풀이 : https://odongfolio.tistory.com/47
[BOJ 11003, 약간 쉬움] 최솟값 찾기 (C++)
개인적인 난이도 약간 쉬움 플래 5치고 매우 쉽게 풀었다 정해를 몰라도 우선순위 큐를 사용해 500B정도의 코드로 구현이 가능하기에 약간 쉽다고 난이도를 매겼다 문제를 읽고 알아낸 특징은 이
odongfolio.tistory.com
deque를 이용해 투 포인터를 보완하는 방법을 알아내는 매우 좋은문제라고 함.
'C++ > 가이드' 카테고리의 다른 글
| 내 알고리즘 독학 순서(계속 업데이트) (0) | 2022.12.30 |
|---|