[Doit!] 알고리즘 평가 & 디버깅

do yeon kim·2022년 10월 16일

Doit

목록 보기

1/1

코딩문제를 풀면 사람들마다 해결하는 방법이 제각각이다.
코딩은 문제 해결에 있어서 정답은 없으나, 효율적인 것은 있다.

예를 들어 A와 B가 문제를 풀었고, 둘다 정답이다.
A는 문제를 푸는데, 1초가 걸렸고, B는 10초가 걸렸다.
누가 더 효율적으로 문제를 풀었다고 할 수 있을까? 정답은 A에이에이에이에이

코딩에도 위와 같이 정답은 없으나 효율을 따질 수 있다.
이렇듯 어느 알고리즘을 사용해서 문제를 풀때 더 효율적인지를 판단하는 척도가 알고리즘의 시간복잡도이다.

시간복잡도에는 3가지 종류가 있다.

빅-오메가
최선일때의 연산 횟수를 표기한다.

빅-세타
보통일때의 연산 횟수를 표기한다.

빅-오
최악일 때 연산 횟수를 표기한다.

보통 알고리즘 풀이에서는 빅-오 O() 표기법을 이용해서 알고리즘의 성능평가한다.

파이썬은 1초에 대략 2000만번의 연산을 수행한다고 기준을 잡는 것이 좋다.

import random

findNumber = random.randrange(1, 101)

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

위의 코드에서 시간복잡도 종류에 따라서 복잡도를 구해보자!!!
빅-오메가의 경우 최선의 경우이므로 findNumber = 1인 경우에 해당한다.
그렇기 때문에 1번만에 찾을 수 있다.

빅-세타의 경우는 보통인 경우이므로 findNumber 중간값이 50일때에 해당하고, 그렇기 때문에 50에 해당하는 N/2의 시간복잡도를 가진다.

빅-오의 경우는 최악의 경우이므로 findNumber가 마지막인 100일때에 해당하므로, N의 시간복잡도를 가진다.

빅-오 표기법은 코딩테스트 시 성능척도의 기준으로 삼아서 문제를 풀면 좋다.
빅-오 표기법은 데이터의 크기(N)이 증가할 수로 수행시간이 다르다.

위의 그래프를 참고해서 문제를 풀때 주의하도록 하자.

논리의 오류를 찾아 바로잡는 과정이 디버깅이다.
지금까지 특별히 디버깅을 한 기억이 없다. 없다기보다는 할줄 몰라서 않했는데, 문제를 풀거나, 코드를 구현하는데 있어서 디버깅은 빠질수 없는 요소이다.

코딩테스를 하며 실수하기 쉬운 4가지 오류