[Coding Test] 기본

알고리즘 선택의 기준

• 입력값 개수를 확인해 사용할 알고리즘을 선정
• C++에서는 1억 번의 연산을 1초의 수행 시간으로 예측 가능

시간 복잡도

• 빅-오메가 : 최선일 때의 연산 횟수를 나타낸 표기법
• 빅-세타 : 보통일 때의 연산 횟수를 나타낸 표기법
• 빅-오 : 최악일 때의 연산 횟수를 나타낸 표기법

※ 코딩 테스트에서는 최악의 경우를 고려한 빅오 표기법을 기준으로 계산

활용법

• 주어진 실행 제한 시간을 1초로 가정
• C++ 기준 100,000,000 번 이하의 연산을 수행해야 함
• 입력값 개수의 최대가 1,000이라면,  O(n^2)의 시간 복잡도를 가진 알고리즘을 사용 가능
• 입력값 개수의 최대가 10,000,000이라면, O(nlogn)의 시간 복잡도를 가진 알고리즘 사용 가능
• 입력값 개수의 최대가 100,000,000이라면, O(n)의 시간 복잡도를 가진 알고리즘 사용 가능

디버깅

• 문법 오류는 컴파일 과정에서 발견 가능하나, 논리 오류는 사용자가 직접 찾아야 함

논리 오류 종류

• 변수 초기화 오류
• 반복문에서 인덱스 범위 지정 오류
• 잘못된 변수 사용 오류
• 자료형 범위 오류

※ int형은 -2,147,483,648 ~ 2,147,483,648(2^31) 범위 저장 가능

※ long long형은 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,808 범위 저장 가능

Conference

• Do it! 알고리즘 코딩 테스트 C++편 - 김종관