반응형
11003번: 최솟값 찾기
N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.
www.acmicpc.net
슬라이딩 윈도우 문제.
매번 윈도우 위치를 변경할 때마다 min함수를 사용할 경우, 시간복잡도가 O(n**2)가 된다.
deque를 활용해 삽입/삭제를 빠르게 수행하되,
deque에 값을 저장하는 방식을 약간 변경하면 효율적으로 연산을 수행할 수 있다.
아래 풀이에서 더 상세한 해설을 볼 수 있다.
백준 11003번 문제 (최솟값 찾기) with Java · 쾌락코딩
백준 11003번 문제 (최솟값 찾기) with Java 03 Dec 2018 | algorithm java sliding_window 문제 11003 문제 접근법 슬라이딩 윈도우 기법을 이용해 접근했다. 우선 문제를 이해해 보면, 주어진 L 값 만큼을 범위로하
wooooooak.github.io
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 프로그래머스. 2019 카카오 recruit - 블록 게임 (Level 4) (0) | 2020.05.19 |
|---|---|
| [Python] 백준 15684. 사다리 조작 (0) | 2020.05.18 |
| [Python] 프로그래머스. 소수 만들기 (Level 2) (0) | 2020.05.11 |
| [Python] 프로그래머스. 점프와 순간이동 (Level 2) (0) | 2020.05.08 |
| [Python] 백준 17822. 원판 돌리기 (0) | 2020.05.07 |