성장하는 코딩블로그

백준(C++) 시간초과 해결법 백준 알고리즘 문제를 풀다 보면 제출 시 시간초과가 뜨는 경우가 있다. 이 경우 코드 몇 개만 추가하거나 수정하거나 해서 시간초과를 해결할 수 있다. 아니면 문제 해결에 사용한 알고리즘의 시간복잡도를 고려해 볼 수도 있다. 오늘 시간초과 원인과 해결법에 대해서 알아보자. 1. ios::sync_with_stdio(false) 추가 C++에서 입력은 크게 printf와 cout 출력은 scanf와 cin이 있다. 여기서 cout와 cin은 printf, scanf에 비해 속도가 느리다. 그 이유는 cout와 cin는 실행 시 값의 자료형을 검사하기 때문이다. 속도가 좀 더 느리나 안정적이다. ios::sync_with_stdio(false); ios::sync_with_std..

C++ STL pair 클래스 총정리(vector, sort) C++ STL 중 라이브러리에 pair클래스가 있다. 오늘은 이 pair클래스에 대하여 알아보겠다. 추가로 알고리즘 문제를 풀 때 어떻게 응용되는지도 보자. pair를 사용하면 자료 두 개를 한 가지 자료에 저장할 수 있다. pair는 2차원 좌표 저장등 많은 곳에서 유용하게 쓰이므로 꼭 익혀두자. 일단 라이브러리에 있으니 추가해 준다. 이제 사용해 보자 생성 pair p; type1, type2 두 개의 데이터를 저장하는 pair p를 만든다. 예를 들어 좌표를 저장하려면 y좌표, x좌표 두 개를 저장할 int형 공간이 필요하므로 pair p;와 같이 선언해 주면 된다. int형뿐만 아니라 string, char, float 등을 자유롭게 ..

문제 링크 : https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인..