PS 풀이 및 정리 (4) 썸네일형 리스트형 C++언어의 빠른 입출력 및 내가 사용하는 코드 기본 템플릿 C언어의 형식지정자 외우기 싫어서 C++의 cin,cout을 표준 입출력을 사용하는데, 사용하다보면 분명 알고리즘 시간복잡도는 시간초과가 안나야 정상인데 시간초과가 나는 경우가 있다. https://www.acmicpc.net/problem/15552 15552번: 빠른 A+B 첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다. www.acmicpc.net 여기 설명이 잘 되어있고 문제를 풀어보면 된다. 그래서 나도 웬만한 코드 짤때는 기본적으로 ios::sync_with_stdio(false),cin.tie(NULL) 이거 2개 int main 안 맨위에 적어두고 코드를 짠다. 단, .. POI Deque 문제(BOJ 8201번 Pilots , 10129번 작은 새) 먼저 Deque dp나 Deque를 이용한 테크닉에 잘 모르거나 익숙하지 않다면 다음 글을 보고 오자. https://chpark1111.tistory.com/8 자료구조 덱(deque)의 활용 덱은 앞뒤에서 빼고 넣을 수 있는 자료구조로, 처음 배울 때는 왜 배우지... 이거 과연 쓸데가 있을까?라고 생각했다. 하지만 이 자료구조를 이용하면 \(A_1,A_2,...,A_N\)이 주어질 때 임의의 상수 B에 대해 \(A_.. chpark1111.tistory.com 8201번 Pilots https://www.acmicpc.net/problem/8201 풀이 : 최솟값, 최댓값 덱을 만들고 덱에서 최댓값, 최솟값들의 인덱스 차이가 t 이상 나지 않도록 관리해주면서 가능한 구간의 최댓값을 갱신해주면 된다... 자료구조 덱(Deque)의 활용 (feat. Priority Queue) 덱은 앞뒤에서 빼고 넣을 수 있는 자료구조로, 처음 배울 때는 왜 배우지... 이거 과연 쓸데가 있을까?라고 생각했다. 하지만 이 자료구조를 이용하면 \(A_1, A_2,..., A_N\)이 주어질 때 임의의 상수 B에 대해 \(A_{i-B}\) ~ \(A_i\) 의 최대, 최소 같이 데이터를 가진 정보들을 특정한 기준에 따라 나열할 때 가장 우선순위가 높은 값을 모든 i에 대해 시간 복잡도 O(N)으로 찾아줄 수 있다. 위와 같은 상황에서 A라는 배열의 각 원소에 \(V_i\)라는 우선순위가 주어져 있다고 하자. 우리는 덱에 다음과 같은 성질을 만족시키도록 자료들을 넣고 뺄 것이다. 성질 : \(I_i\)를 덱의 앞에서부터 i번째에 있는 원소가 가지는 배열 A에서의 인덱스라고 했을 때, i>n>>l; .. POI Ice Skates (BOJ 8177번) 문제는 https://www.acmicpc.net/problem/8177 링크에서 풀어볼 수 있다. 문제 설명: 초기에 1~n 크기의 신발들이 각각 k쌍 씩 있다. 그리고 신발의 크기가 r인 사람은 r~r+d 크기의 신발을 신을 수 있다. 이때, m개의 상황이 생기는데, 각각의 상황은 2가지 종류 중 하나이다. (1) 신발 크기가 \(r_i\)인 사람 \(x_i\) 명이 온다. (2) 신발 크기가 \(r_i\)인 사람 \(x_i\)명이 나간다. (당연하지만 안 들어온 사람은 못 나간다.) 들어오는지 나가는지는 \(x_i\)의 부호로 구별할 수 있다. 각각의 상황이 발생했을 때, 현재 있는 모든 사람에게 위 조건을 만족하도록 신발을 분배할 수 있는지 여부를 묻는 문제이다. (들어오는 사람에게 신발을 주는 .. 이전 1 다음