백준 온라인 저지(BOJ)를 통한 코딩 테스트 이해 하기
BOJ 동작 원리 : https://www.acmicpc.net/blog/view/55
BOJ 채점 결과 : https://www.acmicpc.net/board/view/23037
BOJ 채점 결과 FQA : www.acmicpc.net/board/view/4206
어떤 코딩 테스트 사이트를 이용하는지에 따라 조금씩 차이가 있겠지만, 대부분은 위 내용과 비슷합니다.
코딩 테스트를 위한 C++ 입출력 이해하기
입출력 방식에 따라 성능의 차이가 발생하기 채점 결과가 달라질 수 있습니다.
=> 코딩 테스트를 위해서 입출력에 대한 이해를 할 필요
저는 C++ 언어를 사용할 것이기 때문에 C++에서 코딩 테스트를 위한 입출력 방식에 대해 말씀 드리겠습니다.
C언어에서 사용하는 입출력 방식인 scanf(), printf() 함수는 충분히 빠릅니다. 그렇기 거의 대부분의 상황에서 속도 고민은 크게 안하셔도 됩니다.
참고)
- 빠른 입출력
C++ 입출력 속도 향상 방법
- scanf(), printf() 사용하기
- endl 절대 사용 금지!!
- ios_base::sync_with_stdio(false) , cin.tie(NULL) 사용하기
[1] C스타일 입출력 사용하기
#include <cstdio>
int main(void)
{
int n;
scanf("%d", &n);
printf("%d\n", n);
}
[2] C++ 입출력 사용하기
#include <iostream>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(false); // c와 c++의 표준 입출력 스트림을 동기화를 하지 않겠다는 의미
cin.tie(nullptr); // cin사용시 출력 버퍼를 비우지(flush) 않는다.
int n;
cin >> n;
cout << n << "\n";
}C 스타일 입출력 함수 scanf(), printf() 사용
<cstdio> , <stdio.h>, <iostream> 중 어떤 헤더를 include해도 사용 가능하지만, 보통 <cstdio>를 많이 사용합니다.
C++ 입출력 함수 cin, cout 사용
1) endl 대신 개행 문자("\n")를 사용
- 설명
endl은 개행문자를 출력할 뿐만 아니라 출력 버퍼를 비우는 역할까지 합니다.
온라인 저지는 화면에 바로 보여지는 것은 중요하지 않고 무엇이 출력되는지가 중요하기 때문에 endl을 '\n'으로 바꾸는 것만으로도 굉장한 시간 향상이 나타납니다.
정리하자면 다음과 같습니다.
- 버퍼를 비우지 않아도 되므로 속도가 향상된다.
2) 입출력이 많은 문제에서 cin, cout을 사용해야 하는 경우
=> ios_base::sync_with_stdio(false), cin.tie(nullptr) 사용
(1) ios_base::sync_with_stdio(false)
의미 : C Stream과 C++ Stream 사이의 동기화를 끊는다.
- 설명
C Stream과 C++ 스트림은 서로 분리 되어 있습니다. 그리고 기본적으로 이 둘은 서로 동기화 되어 있습니다. 동기화를 할 경우 C++ 스트림은 스레드로부터 안전(Thread Safe)합니다.
그렇기 때문에 동기화를 끊는다면, Stream들은 독립적인 버퍼를 갖게되어 속도 향상이 있지만, C와 C++의 입출력방식을 혼용해서 쓰는 것이 굉장히 위험해집니다.
- 결론
ios_base::sync_with_stdio(false)가 동기화를 끊는 의미라고 했으니 이것을 해석해보면 다음과 같습니다.
- 동기화할 필요가 없으므로 속도가 향상된다.
- 동기화 하지 않고 독립적인 버퍼를 사용하게 되므로 C Stream과 C++ Stream을 혼용해서 사용하면 안된다.
예를 들어 다음과 같이 스트림을 혼용해서 사용할 경우 출력 순서를 보장할 수 없습니다.
cout << "Hello";
printf("C++");
cout << "Programming";
"C++HelloProgramming", "HelloProgramming", "HelloC++Programming" 과 같이 출력 순서를 보장할 수 없습니다.
2) cin.tie(nullptr)
의미 : cin과 cout의 묶음(tie)을 푼다.
- 설명
기본적으로 cin과 cout은 묶여(tie)있습니다. 스트림이 묶여 있을 경우, I/O작업 변경 시 자동으로 버퍼를 비웁(flush)니다.
합리적인 사용자 상호 작용을 보장하기 위해 기본적으로 cin은 cout에 연결되어 있습니다.
예를 들면 다음과 같습니다.
std::cout << "Enter name:";
std::cin >> name;
- tie 되어 있을 경우 : "Enter name:" 이라는 출력 문구가 출력 된 이후 입력이 가능
- untie 되어 있을 경우 : 입력 전 출력을 보장할 수 없으므로 Enter name이 버퍼에서 출력되기 이전에 입력이 먼저 될 수 있다.
- 결론
- 코딩 테스트와 같이 사용자와의 상호작용이 필요 없고 출력만을 중요시 하는 상황에서 사용하면 속도 향상을 기대할 수 있다.
입출력 관련 내용
입출력 속도 비교
https://www.acmicpc.net/blog/view/56
입출력 함수 구현
cstdio (stdio.h) 관련 내용 정리글
iostream 관련 내용 정리글
표준 라이브러리의 공부하기
표준 라이브러리로 제공되는 자료구조, 함수, 알고리즘 등을 직접 구현해서 사용하려고 하는 것은 대표적인 시간 낭비 일 수 있습니다. 그렇기 때문에 문제 풀이를 할 때 유용하게 사용하려면 자료구조나 표준 라이브러리에 대해서 미리 공부를 하는 것이 좋습니다.
표준 라이브러리에는 굉장히 많은 것이 존재 하지만 다음과 같은 것들은 자주 사용됩니다.
- STL 의 특정 컨테이너 : pair, list, vector, stack, queue, deque, priority_queue, set, map 등
- 표준 입출력 : C 또는 C++ 표준 입출력 사용법
표준 라이브러리에 대해 추후 다룰 예정
코딩 테스트가 실제 개발과 다른점
일반적으로 사용하는 코딩 습관들을 지키다 보면 코드가 길어지고 불편한 경우가 있습니다. 그래서 간결함과 편의성을 위해 코딩 테스트만을 위한 코드를 작성하는 경우가 있는데, 아래 내용은 그런 내용의 예시를 든 것입니다.
- 전역 변수의 사용
- 동적 할당 대신 배열(또는 stl vector) 사용하기
- 미리 계산한 상수값 사용하기
- 가독성 좋은 알고리즘 대신 성능에 유리한 알고리즘 사용하기
자주 하는 실수
- 산술 오버플로 (정수 자료형 표현, 실수 자료형 표현)
- 산술 언더플로 ( 오버플로랑 다름에 유의! )
- 배열 범위 밖의 원소 접근 (대표적인 런타임 에러)
- off-by-one : 하나가 많거나 모자라는 실수를 가리키는 말로 <, > 연산자와 <= , >= 연산자를 쓸때 자주 발생
실수를 줄이기 위해서는 하한값, 상한값, 중간값을 입력해보고 정상 동작하는지 확인하는 과정이 필요합니다.
복잡도 계산
| N입력 크기 | 복잡도 |
| - (왠만해선 신경 안써도 됨) | O(1) 또는 O(lgN) |
| 1억 | O(N) |
| 5백만 | O(NlgN) |
| 1만 | O(N^2) |
| 500 | O(N^3) |
| 23 | O(2^N) |
| 10 | O(N!) |
배열이 사용한 공간 : 배열의 크기 X 자료형의 크기(B)
int a[10000]; → 10000×4B = 40,000B = 39.06KB
int a[100000]; → 100000×4B = 400,000B = 390.62KB
int a[1000000]; → 1000000×4B = 4,000,000B = 3.814MB
int a[1000][1000]; → 1000×1000×4B = 4,000,000B = 3.814MB
int a[10000][10000]; → 10000×10000×4B = 400,000,000B = 381.469MB
int a[100000][100000]; → 100000×100000×4B = 40,000,000,000B = 37.25GB
코딩 테스트 및 프로그래밍 대회에서 배울 수 있는 것들
- 문제 해결하는 데에만 집중할 수 있다. 그래픽 인터페이스 등을 전혀 사용하지 않고, 큰 프로젝트 환경에서처럼 큰 그림을 위한 코드를 작성을 해야 하는 것이 아니기 때문에, 문제 해결을 위한 좋은 코드를 작성하는 연습이 된다.
- 정답과 오답 여부가 명확히 가려진다. 그렇기 때문에 빠르고 객관적인 피드백을 받을 수 있고, 예외 없는 좋은 프로그램을 짜는데 도움이 된다.
- 다양한 알고리즘 설계 기법과 자료구조를 직접 사용해 볼 수 있는 계기가 된다. 명시적인 시간 제한과 메모리 제한이 있기 때문에, 알고리즘에 사용된 원칙들을 이해하고 변형해서 풀어야 한다. 이런 학습이 되어 있으면 실무에서도 성능을 예측하고 좋은 퍼포먼스를 낼 수 있도록 설계할 수 있다.
- 자신의 코드 고수들의 코드를 비교해 볼 수 있는 기회가 된다. 소스 코드를 대부분 공개하기 때문에, 자신의 코드와 다른 사람의 코드를 비교해보면서 개선해 나갈 수 있다.
문제 해결 학습 방법
- 필요 배경 지식 : C++, STL, 자료구조, 고등 수학
- 추천 서적
- C++로 쉽게 풀어쓴 자료구조 (생능 출판사)
- 종만북 : 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (1,2권)
- Introduction to Algorithms (한빛미디어)
- 가능한 한 많은 문제 풀기
복잡한 알고리즘을 하나 더 아는 것보다 실제로 자신이 아는 것을 이용해 문제를 풀 수 있는 능력이 훨씬 중요하다.
<참고>
- 문제 해결 단계
- 문제를 읽고 정확하게 이해한다. (잘못 이해하면 반드시 큰 대가를 치르게된다.)
- 익숙한 용어로 재정의한다.
- 어떻게 풀지 계획을 세운다. (해결 방향 결정, 사용할 알고리즘 및 자료구조 선정)
- 계획을 검증한다. (시간/메모리 제한이나 상한/하한 값과 같은 요구 조건을 모두 만족하는지 검증)
- 프로그램을 구현한다.
- 회고하기. (개선 사항을 찾아본다)
- 문제 해결 학습의 목표
- 문제 푸는 것을 목표로 두는 것이 아니라 , 문제 푸는 기술을 연마하는 것을 목표로 해라
- 초보 시절에는 너무 한 문제에만 매달리는 것도 좋지 않으므로, 문제를 풀지 못했을 때 다른 사람의 답안을 참고하여 문제 해결할 때 취했던 접근들을 되새겨 본다.
- 체계적인 접근을 위한 질문들
- 단순화 할 수 있는가? (알고리즘 단순화, 문제 단순화)
- 수식화 할 수 있는가?
- 도식화 할 수 있는가?
- 문제를 분해할 수 있을까?
- 뒤에서부터 생각해서 풀 수 있을까?
- 순서를 강제할 수 있을까?
- 그룹화 할 수 있을까?
References
https://blog.encrypted.gg/923?category=773649
프로그래밍 대회에서 배우는 알고리즘 문제해결 전략
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
| Union-Find (0) | 2020.07.01 |
|---|---|
| 그래프 순회(Graph Traversal) - BFS , DFS (0) | 2020.07.01 |
| 반복과 재귀 (0) | 2020.06.30 |
| 알고리즘 문제 풀이를 위한 C++ 개발 환경 (0) | 2020.06.10 |
| 알고리즘 Orientation (0) | 2020.06.10 |
