728x90 반응형 슬라이딩 윈도우2 [백준] 11003번 : 최솟값 찾기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 일정 범위 안에서 최솟값을 구하는 문제로 슬라이딩 윈도우와 정렬을 사용하면 된다. 윈도우의 크기는 문제에서 최솟값을 구하는 범위가 i - L + 1부터 i까지이므로 L로 생각하면 된다. 최솟값을 찾기 위한 정렬을 O(nlogn)의 시간 복잡도를 가지므로 N과 L의 최대 범위가 5,000,000인 해당 문제에서는 정렬을 사용할 수 없다. O(n)의 시간 복잡도로 해결하기 위해 덱(deque).. 2024. 1. 10. [백준] 12891번 : DNA 비밀번호 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 1. 문제 설명 2. 풀이과정 P와 S의 길이가 1,000,000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 한다. 부분 문자열의 길이가 P이므로 슬라이딩 원도우의 개념을 이용해 문제를 쉽게 해결할 수 있다. 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결하는 알고리즘이다. 먼저 문자열의 시작 위치에 포인터를 하나 두고, 부분 문자열의 길이만큼 뒤에 포인터.. 2024. 1. 10. 이전 1 다음 728x90 반응형
