[삼성역량테스트PRO] Pro시험 팁

시험에앞서 공부를 별로 못했다

그래서 몇년전 붙은 선배에게 팁을 몇가지 물어봤다

---

글에 앞서 이 팁은 정말 급할때만 보길 권하며

코딩실력에는 1도 도움이 되지않는 오로지 시험만 보는 팁이다..

---

 

1. 더 빠른속도 위해 merge sort 구현해야됨?

C++의 경우 algorithm 헤더의 sort()함수는 quick sort의 단점을 보완한 intro sort 방법으로 구현되어 있다.
quick sort 는 일반적으로 O(nlogn) 이지만 최악의 경우에 O(n^2) 의 시간 복잡도를 가진다.
하지만 intro sort 는 어떤 상황에서도 O(nlogn)의 시간 복잡도를 가진다.

-> 급하면 일단 sort() 쓰자

[개념정리] STL라이브러리 - sort()2

 

2. 메모리 POOL 방식으로 구현해야됨?

우린 기본적으로 동적할당 malloc, calloc, free, new 등을 사용하곤 한다.
하지만 메모리가 터지는걸 방지하기 위해 memory pool 방법을 권하곤 하는데
물론 효과는 있겠지만 모든 문제에 효과가 극적이지는 않기 때문에 아는걸로 사용

-> 모르면 malloc 사용해도 풀리긴함

 

3. 1억 - 1초

A(Advanced)형 준비할때도 많이 들어봤겠지만 B형 Pro는 구현+최적화가 중요하다.
메모리에 접근하는 횟수를 다져봤을 때 시간제한이 10초라면 대충 계산해보자.
내가 짠 코드가 10억횟수 이하의 메모리접근을 하는지!

4. DFS 사용 X

재귀 사용하면 많이들 터진다.
따라서 DFS사용보단 BFS 사용권유.

[백준문제풀이] 1260 DFS와 BFS

 

5. O(nlogn) O(n) 구현 필요

O(N^2) 나오는순간 게임끝이다.
다만 케이스 자체가 적은 경우 가능할수도있다.
문제받고 바로 풀기보다 최대한 생각하면서 시간복잡도를 줄여보자

[개념정리] Big - O 시간복잡도 표기

이상 벼락치기 팁 끝