본문 바로가기
728x90

슬라이딩 윈도우2

[python] 백준 2096 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 해결 사실 문제 자체는 매우 쉽다. (dp를 이용해서 0열, 1열, 2열에 각각 올 수 있는 이전 행 최고 누적합을 가져오서 더하면 되므로) 하지만 메모리가 4MB 밖에 안주어진다. 정확한 양은 체감을 못해도 평소 250~500MB 되는 문제도 많은 것을 보면 엄청 적다는 것을 알 수 있다. 따라서 리스트를 n행 모두 사용하는 것이 아니라(dp[0], dp[1], .... 사용하면 메모리가 커진다..) 한.. 2023. 3. 7.
[python] 백준 11003 최솟값 찾기 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 문제 해결 i~i+l-1 까지 리스트 원소중 최솟값을 찾는 것이다. 다른 수들은 고려할 필요가 없으므로 (value,index)를 deque를 이용해 저장하자. 원소를 0~n까지 돌면서 deque[-1][0]과 비교하여 원소가 더 작으면 deque[-1][0]을 빼준다. 이를 반복한다. 필요 없기 때문에... 그리고 deque[-1][0]이 더 커지는 때가 오면 오.. 2023. 2. 19.
728x90