본문 바로가기

슬라이딩 윈도우

[BOJ] 백준 1593번 문자 해독 (Java)
Dot Algo∙ DS/PS 2022. 3. 15. [BOJ] 백준 1593번 문자 해독 (Java) #1593 문자 해독 난이도 : 골드 4 유형 : 문자열 / 슬라이딩 윈도우 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net ▸ 문제 마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다. 마야 문자는 소리를 나타내는 여러 종류의 그림글자로 구성되는데, 이 글자들이 여러 위치에서 결합함으로써 단어를 형성한다. 마야 문자 해독을 어렵게 하는 요인 중 하나는 바로..
[알고리즘] 투 포인터와 슬라이딩 윈도우 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 7. 7. [알고리즘] 투 포인터와 슬라이딩 윈도우 (Java) 투 포인터 투 포인터는 주어진 배열에서 두 개의 포인터를 조작해가며 원하는 것을 얻는 기법이다. 투 포인터 알고리즘 문제 유형 포인터 2개가 같은 방향으로 진행 포인터 2개가 양끝에서 시작하여 반대로 진행 1. 포인터 2개가 같은 방향으로 진행 백준 2003번: 수들의 합2 해당 문제 예제 2번을 통해 시뮬레이션을 돌려보자. n = 10, m=5, 원소의 갯수가 10개인 배열에서 구간 합이 5인 구간을 찾으면 된다. 빨간색은 s이고, 파란색은 e인 두 포인터는 시작점 0에서 같이 탐색을 시작한다. e를 한 칸씩 움직여 s~e사이에 있는 원소들의 구간합을 구한다. sum :1 sum의 값이 m보다 크게 될 경우 e의 값을 조정하면 값이 더욱 커지기 때문에 s의 값을 이동해서 앞에 있는 원소들을 하나씩 빼준..
[BOJ] 백준 11003번 최솟값 찾기 (Java)
Dot Algo∙ DS/PS 2021. 7. 7. [BOJ] 백준 11003번 최솟값 찾기 (Java) #11003 최솟값 찾기 난이도 : 플레 5 유형 : 슬라이딩 윈도우 / Deque 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net ▸ 문제 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. ▸ 입력 첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000) 둘째 줄에는 N개의 수 Ai가 주어진..

티스토리툴바

티스토리툴바