[알고리즘 코딩테스트](1):코딩 테스트 준비하기

1. 시간 복잡도 

1) 정의 : 주어진 문제를 해결하기 위한 연산 횟수, 1초동안 2,000만번~1억번의 연산을 수행함

2) 유형

 

1~100 사이의 무작위값을 찾아 출력하는 코드

import random
findNumber =random.randrange(1,101) // 1~100 사이의 랜덤값 생성
for i in range(1,101):
	if i == findNumber:
    	print(i)
        break

 

(1)빅 오메가: 최선일 때의 연산 횟수를 나타내는 표기법 =>예제의 시간 복잡도 1

(2)빅 세타: 보통일 때의 연산 횟수를 나타내는 표기법=>예제의 시간 복잡도 n/2

(3)빅 오: 최악일 때의 연산횟수를 나타내는 표기법 =>예제의 시간 복잡도 n

=>코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산

 

2.시간 복잡도 활용하기

문제: n개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오

입력: 1번쨰 줄에 수의 개수 n(1<=N<=1,000,000), 2번째 줄부터는 N개의 줄에 숫자가 주어진다. 이 수는 절대값이 1,000,000보다 작거나 같은 정수다. 수는 중복되지 않는다.

시간 제한: 2초

예제 입력1

5

5

2

3

4

1

예제 출력2

1

2

3

4

5

1. 연산 횟수는 1초에 2,000만번 연산하는 것을 기준으로 생각함
시간 제한 2초이기 때문에 4,000만 번 이하의 연산횟수로 문제를 해결해야 함 
=> 버블정렬의 경우 1,000,000,000,000 => 부적합한 알고리즘
=> 병합정렬의 경우 20,000,000 => 적합한 알고리즘

2. 코딩테스트에서는 일반적으로 상수를 무시함
예제1) 연산 횟수 = N
N =100000
cnt=1
for i in range(N):
     print ("연산횟수" + str(cnt))
     cnt +=1

예제2) 연산 횟수 =3N
N =100000
cnt=1
for i in range(N):
     print ("연산횟수" + str(cnt))
     cnt +=1
for i in range(N):
     print ("연산횟수" + str(cnt))
     cnt +=1
for i in range(N):
     print ("연산횟수" + str(cnt))
     cnt +=1

두 예제 코드의 연산 횟수는 3배 차이가 나지만 코딩 테스트에서는 일반적으로 상수를 무시하기 떄문에 두 코드 모두 시간 복잡도가 O(n)으로 같음

3.시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출함
예제3) 연산 횟수 = N^2
N=100000
cnt=1
for i in range(N):
     fof j in range(N):
          print("연산 횟수" +str(cnt))
          cnt +=1

만약 예제 3에 일반 for문이 10개 더 있어도 시간 복잡도의 변화는 없음

 

3. 디버깅

:프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정

방법: 코드에서 디버깅하고자 하는 줄에 중단점을 설정하고 IDE의 디버깅 기능을 실행해 진행함

(=>실제 문제 풀면서 진행해 보기)

1. 변수 초기화 오류 찾아보기

2. 반복문에서 인덱스 범위 지정 오류 찾아보기

3. 잘못된 변수 사용 오류 찾아보기