슬라이딩 윈도우를 이용한 최댓값 찾기(sliding window maximum, Deque Range Maximum Trick)

1. 문제 배열 A에서 길이가 K인 모든 연속하는 부분배열내에서 최댓값을 찾는 문제 [1,2,3,1,4,5]이고 K = 3인 경우를 생각해보자. [1,2,3]에서 최댓값은 3 [2,3,1]에서 최댓값은 3 [3,1,4]에서 최댓값은 4 [1,4,5]에서 최댓값은 5 배열의 크기가 작으면 매우 쉬운 문제지만, 배열의 크기가 크면 상당히 어려운 문제다. 투포인터로 구간의 시작과 끝을 잡고 첫 구간에서는 어떻게 O(K)로 최댓값을 찾아 놓은 다음.. 다음 구간으로 이동할텐데, 시작과 끝의 위치를 아니까, 시작 쪽의 원소를 버릴거고 끝의 원소를 추가할거고... 그런다고 하더라도 최댓값이 뭔지를 어떻게 알지? 운 좋게 시작과 끝에 최댓값이 있다고 하더라도... 구간 중간에 최댓값이 있는거라면 어쨌든 매 구간마다 ..

• format_list_bulleted 슬라이딩 윈도우
• · 2024. 5. 8.
• textsms

ABC 335 C번 복기 - 놓치기 쉬운 deque를 사용할 때 주의할 점(deque indexing is O(N)) + 배열과 연결리스트 접근 시간복잡도 차이

1. 문제 C - Loong Tracking (atcoder.jp) C - Loong Tracking AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 1번부터 N번까지 좌표가 있고, 1번 좌표는 쿼리에 의해 움직이게 된다. 1번 좌표가 움직이면, 2번,3번,4번,...,N번 좌표는 각각 1번,2번,3번,...,N-1번 좌표가 된다. 쿼리가 20만개이고 좌표수도 최대 100만개라 단순하게 접근하면 시간초과를 받을 것인데 그림으로 생각해보면 접근법을 생각할 수 있다 처음에 배열에 1번부터 N번까지 좌표가 있는데, ..

• format_list_bulleted Atcoder
• · 2024. 1. 7.
• textsms

자바 자료구조3 -자바에서 스택, 큐, 덱 사용법-

1. Stack import java.util.Stack Stack (name) = new Stack(); 여기서 (type)은 reference type으로 스택 안에 들어갈 원소의 타입 import java.util.Stack; public class Main { public static void main(String[] args){ Stack s = new Stack(); } } 2. stack 핵심 메소드 2-1) push(E) 맨 위에 데이터 E를 추가 2-2) size() stack에 들어있는 데이터 수를 반환 2-3) isEmpty() stack이 비어있다면 true, 아니라면 false를 반환 2-4) peek() stack의 가장 위에 있는 데이터를 반환 2-5) pop() stack의 ..

• format_list_bulleted Java 기초
• · 2023. 3. 4.
• textsms

3차원 BFS에서 조금은 섬세한 디테일 -공주님을 구해라!-

1. 문제 17836번: 공주님을 구해라! (acmicpc.net) 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net (1,1)에서 용사가 (N,M)에 있는 공주님을 구하고자 움직일 수 있는 최단 시간을 구하는 프로그램을 작성 맵에 반드시 하나가 있는 전설의 명검 그람을 획득하였으면 제한 없이 벽을 부수고 이동할 수 있다 2. 풀이 분명 쉬운 문제지만... 너무 쉽게 생각하면 틀리기 쉽다고 해야하나.. 잘못된 생각 >> 그람이 반드시 하나가 있다면, 그람을 획득하고 이동해야 최단시간? >> 하지만..

• format_list_bulleted DFS BFS 정복기
• · 2022. 11. 13.
• textsms

프로그래밍으로 뱀을 만드는 방법? -뱀-

1. 문제 3190번: 뱀 (acmicpc.net) 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 규칙에 따라 움직이는 뱀의 이동경로가 주어질때, 언제 게임이 끝나는지 구하는 프로그램을 작성 2. 풀이 뱀이 이동할때, 먼저 머리를 다음 칸에 위치시키고 사과가 있으면 사과를 먹고 그대로 두거나 사과가 없으면 꼬리가 위치한 칸을 비우므로 deque를 이용해서 뱀의 자취를 표현할 수 있을 것 같다 꼬리를 비울때는 deque의 0번째 원소를 제거하고, 머리를 넣을때는 deque의 마지막 원소를 넣어주고 ----------..

• format_list_bulleted 구현,시뮬레이션
• · 2022. 11. 13.
• textsms

주사위를 구현하는 방법 - 주사위 굴리기 -

1. 문제 14499번: 주사위 굴리기 (acmicpc.net) 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 지도 위에 주사위를 향하는 방향으로 반복적으로 굴리면서, 숫자를 주사위로 복사하거나 지도로 복사하는 명령을 반복적으로 수행할때, 각 명령마다 윗면에 쓰인 숫자를 출력하는 문제 2. 풀이 주사위를 굴릴때 생각해보면 위, 아래로 굴리냐, 아니면 오른쪽 왼쪽으로 굴리냐에 따라 사용하는 면이 정해져있다 위,아래로 굴리는 경우는 아래와 같고 오..

• format_list_bulleted 구현,시뮬레이션
• · 2022. 11. 12.
• textsms