전체 글 (5) 썸네일형 리스트형 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\)의 부호로 구별할 수 있다. 각각의 상황이 발생했을 때, 현재 있는 모든 사람에게 위 조건을 만족하도록 신발을 분배할 수 있는지 여부를 묻는 문제이다. (들어오는 사람에게 신발을 주는 .. 블로그 소개(Blog Introduction) 안녕하세요 거의 아무도 보지 않을 블로그에 소개글을 적자니 웃기지만... 아마 제가 PS(problem solving) 공부한 것, 알고리즘 문제 풀이 위주로 적고 대회 참가 후기(codeforces 등등)를 조금씩 올릴 예정입니다. 앞으로 다른 글들은 제가 겪은 시행착오, 코드, 최종풀이 및 배운점등 제 생각을 적을것이기 때문에 아마 존댓말보다는 반말을 쓸것 같습니다. 현재 머신러닝을 조금씩 공부하고 있긴한데, 기초가 쌓이면 머신러닝 관련한 글도 적을 계획입니다. 블로그를 만든 이유는 제가 생각했던 점, 공부해왔던 것들을 정리하고자는 마음도 있지만 제가 글을 너무 못써서 많이 적어보고 다른 사람들과 소통하면서 많은 것을 배울 수 있다고 생각하기 때문입니다. 글이 이해가 안된다던지 문장구조가 이상하다 또.. 이전 1 다음