슬라이딩윈도우

12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 풀이 """ DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다. 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 ..

11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 분석 일정 법위에서 최솟값을 찾는 문제 : 슬라이딩 윈도우/ 정렬 정렬 N과 L의 범위가 5,000,000인 문제에서 정렬 사용 불가 슬라이딩 윈도우 덱으로 구현하여 정렬 효과 i-L+1 ~ i 까지 이므로 윈도우 크기는 L로 생각 예시 N: 12, L : 3, A: 1 5 2 3 6 2 3 7 3 5 2 6 1. 새 노드 (3,2)가 저장될 때 뒤에서부터 비교 시작 : (2,5)는 (3,2)보다 숫자가 크므로 덱에서 제거 (최솟값..