본문 바로가기

Algorithm/백준

 (3)
[백준] 입출력 시간 줄이는 방법 (c++) 백준 문제를 풀다 보면 입력과 출력의 수가 많은 문제들이 있다.    예시로 위 문제는 최대 100만번의 입력과 50만번의 출력이 수행되어야 한다. C++에서 이런 문제를 cin, cout으로 풀면 코드를 잘 짜더라도 시간 초과가 뜬다. 코드에 두 줄만 추가해주면 된다.  코드#include int main { std::ios::sync_with_stdio(false); std::cin.tie(NULL) // code return 0;} 의미를 살짝 보면std::ios_base::sync_with_stdio(false); 원래 의 cin, cout은 의 printf 등에서 사용하는 입출력 버퍼와 동기화되어 있다. 이를 false로 설정하면 동기화 과정이 생략되고 빠르게..
[백준] 10845번: 큐 (직접 구현과 비교, c++) https://www.acmicpc.net/problem/10845큐 자료구조를 구현하는 문제인데, C++의 STL 라이브러리 를 이용해도 되지만, 직접 구현해보고 속도를 비교해보았다.방법 1: 직접 구현일반 큐 혹은 원형 큐로 구현하는 선택지가 있었다. 명령어가 N개라면 배열의 크기를 N개로 설정하면 되니 구현이 더 쉬운 일반 큐 방법을 선택했다.#include #include class Queue {private: int *queue; short front = 0, back = 0;public: Queue(short max_size) { queue = new int[max_size]; } short get_size() { return back - front; } bool is_..
[백준] 7568번: 덩치 (빠른 풀이, C++) https://www.acmicpc.net/problem/7568평균 시간 복잡도 O(N^2)으로 푸는 문제인데, O(NlogN)의 풀이 방법이 생각나서 직접 풀어보았다.미리 말하자면, 입력 숫자의 제한이 작기 때문에 O(N^2)로 풀어도 충분한 문제이다.채점 결과에서도 더 빠른 풀이가 눈에 띄는 속도 차이를 보이진 않는다.문제 설명질문 게시판을 봐도 같은 내용의 질문이 많은데,문제의 순위 세는 방식은 문제 속 자신보다 더 "큰 덩치"의 사람의 수를 센다.이 방식은 2등이 3명이라고 꼭 3, 4등이 없으리란 보장이 없다.[예시 (키, 몸무게)]A: (80, 180): 1등B: (70, 170): 2등C: (60, 170): 2등D: (50, 170): 2등E: (65, 165): 3등방법 1: Brute..

티스토리툴바