플랫폼: 프로그래머스
강의명: 어서와! 자료구조와 알고리즘은 처음이지?
강사명: 이시윤
1. Computational Thinking
2. 효율적인 솔루션이 필요할 때
오름차순 정렬될 리스트의 최댓값을 찾는 효율은 O(1)이다.
하지만 이해를 위해 아래 정의된 haystack 리스트의 요소들이 랜덤하게 정렬 돼 있다고 가정해 보자.
[1] N이 증가할수록 최댓값을 구하는 데 오랜 시간이 걸린다.
import time
n = int(input("Number of elements: "))
haystack = [i for i in range(n)]
ts = time.time()
maximum = max(haystack)
elapsed = time.time() - ts
print(f"Maximum element: {maximum}, Elapsed time: {elapsed:.2f}")
# 1,000개의 요소로 구성된 리스트
Number of elements: 1000
Maximum element: 999, Elapsed time: 0.00# 10,000개의 요소로 구성된 리스트
Number of elements: 10000
Maximum element: 9999, Elapsed time: 0.00# 100,000개의 요소로 구성된 리스트
Number of elements: 100000
Maximum element: 99999, Elapsed time: 0.00# 1,000,000개의 요소로 구성된 리스트
Number of elements: 1000000
Maximum element: 999999, Elapsed time: 0.02# 10,000,000개의 요소로 구성된 리스트
Number of elements: 10000000
Maximum element: 9999999, Elapsed time: 0.16# 100,000,000개의 요소로 구성된 리스트
Number of elements: 100000000
Maximum element: 99999999, Elapsed time: 1.81[2] 건초더미에서 원하는 바를 찾는다는 것은 쉽지 않다.
아래는 오름차순으로 정렬된 수들이다.
549를 찾기가 얼마나 편한가!
문제마다 최적의 해법이 있다.
최적의 해법을 위한 자료구조와 알고리즘을 알아야 자원을 아낄 수 있다.
