알고리즘 코딩테스트 - 코딩테스트 기본

 

진짜 오늘부터 코딩테스트 공부 안하면 진짜 진짜 쓰레기 입니다 ....

 

 

1. 시간복잡도 표기법

(1) 시간복잡도 유형

• 빅 - 오메가 : 최선일 때의 연산 횟수를 나타낸 표기법 (즉, 가장 운이 좋을 때)
• 빅 - 세타 : 보통일 때의 연산 횟수를 나타낸 표기법
• 빅 - 오 : 최악일 때의 연산횟수를 나타낸 표기법 (즉, 가장 운이 안 좋을 때)

코딩테스트에서는 빅 - 오 표기법으로 계산하는 것이 좋음 ( 왜냐 ? - 최악의 케이스를 염두에 둬야하기 때문 )

import random
findNumber = random.randrange(1,101)

for i in range(1,101) :
  if i == findNumber :
    print(i)
    break

 

 

 

 

---

2. 시간복잡도 활용하기

 

백준 2750번 : 수 정렬하기에서 연산횟수 계산하기

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

 

연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출

• 시간 제한이 2초임으로 4000만 번 이하의 연산 횟수로 문제를 해결해야 함 (N의 범위가 1,000,000까지이기 때문)
• 버블정렬 Ω(n^2)
   
  : (1,000,000)^2 > 40,000,000 -> 적합하지 않음
• 병합정렬 Ω(nlogn) : 1,000,000*log(1,000,000) = 약 20,000,000 

 

---

3. 코드의 논리오류를 잡는 법

(1) 디버깅 

• 코딩테스트에서 정말 중요, 일할때도 중요 !
• 디버깅이란 논리 오류를 찾아 바로잡는 과정을 말함

(2) 코딩테스트를 하면서 실수하기 쉬운 오류

• 변수 초기화 오류 : 두번째 테스트 케이스부터 통과되지 않을 때, 변수가 정상적으로 초기화되었는지 디버깅을 이용해 확인해보기
• 인덱스 범위 지정 오류 : 비교 연산자 및 N-1 혹은 N 잘 구별하기
• 잘못된 변수 사용 오류  : 변수들 혼동하지 않게 변수명 잘 구별하기
• 파이썬 자동변환형 조심

 

(추가) 연산자 주의

• / : float형으로 출력하며 소수점의 결과까지 보여줌
• // : int형으로 출력하며 몫의 결과만 보여줌
• % : 나눗셈을 한 후 나눈 나머지 값을 보여줌

 

 

* do it 알고리즘 코딩테스트 내용을 참고하였습니다.