코딩 테스트 스터디 - 03 시간 복잡도

취업을 할지 안 할지 모르겠지만, 어쨌든 코딩 테스트가 취약점이긴 하니까 스터디에 들어가 보았다.
스터디에서 매주 내용을 블로그에 정리하기를 권장하고 있다.

알고리즘

정밀성 - 변하지 않는 명확한 작업 단계
유일성 - 명확한 다음 단계를 가져야 함
타당성 - 구현 가능해야 하고, 사용 가능해야 함
입력, 출력 - 입력을 받아들이고 출력을 내보내야 함
유한성 - 무한 루프 X, 특정 수의 작업 이후 정지
일반성 - 일반적으로 적용할 수 있어야 함 (테스트 케이스만 되는 거 말고..)

알고리즘의 성능

입력 -> 출력 간
구현된 코드 동작

• 절대 시간 측정
• 연산 횟수 측정

절대 시간 측정

입력값의 입력부터 출력값의 출력까지의 시간 측정.
PC마다 그 결과가 다르게 나올 확률이 높음

연산 횟수 측정

코드가 동일하면 연산 횟수는 모두 동일하므로 객관적 지표로 사용 가능하지만,
입력 값에 따라 연산 횟수는 달라질 수 있음
-> 최악의 경우를 기준으로 연산 횟수를 정해야 함
-> 시간 복잡도
매 코딩 테스트마다 연산 횟수를 매번 측정해야 하나? NO
연산 횟수의 추이 정도만 보면 됨 점근적 표기법 :
시간 복잡도가 대충 얼마 나오느냐에 따라서 적합한 자료 구조 or 알고리즘을 선택할 수 있음.

점근적 표기법

N이 무한대로 감에 따라 어떤 추이를 보이는지 (최고차항)
빅오 표기법으로 표기한다.

1차원 배열 탐색 O(N)
2차원 배열 탐색 O(N*M)
이진 탐색 트리에서 원소 탐색 O(logN): 매번 탐색 대상이 반으로 줄어드는 경우.
동전 N개를 던졌을 때 경우의 수 O(2^N)

활용할 때, 입력값의 크기를 통해 어느 시간복잡도까지 허용되는지 추측.
-> 알고리즘, 자료 구조 선택을 명확하게 할 수 있음.
초당 1000 ~ 2000만 정도의 연산

사용하는 메서드에도 시간 복잡도가 다를 수 있음 (vector, list)

: 문제 11, 문제 62

---

출처 : 코딩 테스트 합격자 되기