코딩테스트

코딩테스트 문제 풀이 전, 시/공간 복잡도 이해하기

복잡도 코딩테스트를 준비하기 전, 시간 복잡도와 공간복잡도 이해 해야한다. 대부분의 코딩테스트 문제에는 제한 시간과 메모리가 존재한다. 이를 바탕으로 적절한 시/공간 복잡도를 계산한 뒤 적절한 알고리즘을 사용할 필요성이 있다. 시간 복잡도 '제한시간'안에 알고리즘 문제를 해결하기 위해서는 시간복잡도를 이해해야 한다. 일반적으로 O(N)과 같은 빅오 표기법을 기준으로 연산 횟수를 계산한다. for 문으로 문제를 해결할 시 시간복잡도는 다음과 같다. 단일 for문: O(N) 이중 for문: O(N²) 삼중 for문: O(N³) N값이 어떻게 주어지냐에 따라 시간복잡도를 계산해보자면 N = 500 O(N³)일 경우 1.25 * 10⁸의 연산 횟수가 필요하다. O(N²)일 경우 2.5 * 10⁵의 연산 횟수가 ..

컴파일 속도 향상 (시간 초과 오류)와 Stream (스트림)

ios::sync_with_stdio, cin.tie, cout.tie란? ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); Stream 우선 stream에 대한 이해가 먼저 필요하다 우리가 c언어와 c++언어를 가장 처음 배울 때 적는 것은 사실 아래에 두 헤더파일이다 각각은 stdio: standard input output iostream: input output stream #include #include 표준 스트림(standard streams)은 특정한 프로그래밍 언어 인터페이스뿐 아니라 유닉스 및 유닉스 계열 운영 체제(어느 정도까지는 윈도에도 해당함)에서 컴퓨터 프로그램과 그 환경(일반적으로 단말기) 사이에 미리 연결된 입출력 통로를 가리킨다. 우리..