[알고리즘] 복잡도, 코테 기초

복잡도

알고리즘의 성능을 나타내는 척도. 낮을수록 좋은 알고리즘

- 시간 복잡도: 특정한 크기의 입력에 대한 알고리즘의 수행 시간 분석. 높으면 오래 걸린다.

- 공간 복잡도: 특정한 크기의 입력에 대한 알고리즘의 메모리 사용량 분석. 높으면 많은 메모리 필요하다.

 

빅오 표기법(Big-O notatino)

가장 빠르게 증가하는 항만을 고려하는 표기법

• O(1): 상수 시간. 가장 좋다.
• O(logN): 로그 시간
• O(N): 선형 시간
• O(NlogN): 로그 선형 시간

 

시간 복잡도 예시

array = [3, 5, 1, 2, 4]

for i in array:
	for j in array:
    	temp = i * j
        print(temp)

위의 2중 반복문의 시간 복잡도는 O(N^2)이다. (모든 2중 반복문이 그런건 아니다. 반복문 내에서 다른 함수를 호출하면 그 함수의 시간 복잡도까지 고려해야 한다.

 

알고리즘 설계 Tip

1. 파이썬 <-> pypy 로 제출을 시도해라.

2. 시간제한(수행시간 요구사항)을 가장 먼저 확인해야 한다.

 

해결과정은 다음과 같다.

1. 지문 읽기 및 컴퓨터적 사고
2. 요구사항(복잡도) 분석
3. 문제 해결을 위한 아이디어 찾기 - 핵심만 찾으면 간결한 코드 작성 가능
4. 소스코드 설계 및 코딩

문제를 풀면서 수행 시간 측정 소스코드를 활용할 수도 있다.

import time
start_time = time.time() #측정 시작

#소스코드
end_time = time.time() #측정 종료
print("time:", end_time - start_time) #수행시간 출력

---

 

본 포스팅은 하단의 책(2021)과 유튜브 강의를 참고하여 정리한 포스팅입니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24