알고리즘 속도 체크 C++
·
C++/코딩 테스트
#include // 시간을 위해 사용하는 헤더 파일int main(){ clock_t start; clock_t end; start = clock(); // 시작 시간을 받아옴 /** 알고리즘 실행 */ end = clock(); // 마무리 시간을 받아옴 cout((end-start)/CLOCKS_PER_SEC); // 시간을 출력 return 0;}
코딩 테스트 주의점
·
C++/코딩 테스트
코딩 테스트는에서의 연산 횟수는 약 1억회C, C++은 1억회 연산에 1초 당 1억회 연산이 걸린다. 키워드를 얻기 위해 다양한 알고리즘을 학습해야한다.문제에서 키워드를 찾고 적합한 알고리즘을 구현해야한다.
알고리즘 공부
·
C++/코딩 테스트
1. 백트래킹- 보통 재귀 형태- 특정 파라미터 값에 따라 종료, 다음 재귀로 넘어가는 과정에서 값을 증가- 하노이탑(재귀 문제), 모든 경우의 수 출력 등 다양한 곳에서 사용 2. DFS : 재귀- 백트래킹의 형태로 보통 구현, 그래프 이론에서 사용되는 특수한 형태 3. BFS : 큐- 큐를 사용한 탐색- 모든 경우의 수를 탐색 -> 시간 복잡도가 큰 편- 간선의 가중치가 모두 동일한 경우 -> 시간 복잡도가 작거나, 최단 거리 탐색에도 사용 가능 4. 다익스트라 : 최단 거리 탐색- 가중치가 음이 아닌 경우만 사용 -> 벨만-포드 알고리즘 사- 시간 복잡도 O(ElogV)- V: 노드의 숫자, E: 간선의 숫자이다.- 간선이 10만개로 주어지는 문제는 보통 다익스트라 5. 플로이드 워셜 : 최단 거리..