알고리즘 입문 - 최댓값 찾기

파이썬의 리스트 기능

리스트(list)는 정보 여러 개를 하나로 묶어 저장하고 관리할 수 있는 기능입니다. 리스트를 만들려면 대괄호([ ]) 안에 정보 여러 개를 쉼표(,)로 구분하여 적어 주면 된다.

>>> a = [5, 7, 9]
>>> a
[5, 7, 9]
>>> a[0]
5
>>> a[2]
9
>>> a[-1]
9
>>> len(a)
3

주어진 숫자 n개 중 가장 큰 숫자를 찾는 알고리즘

주어진 숫자 n개 중에서 가장 큰 숫자(최댓값)를 찾는 문제

• 17, 92, 18, 33, 58, 7, 33, 42와 같이 숫자가 여덟 개가 있을 때 최댓값 찾기

1. 첫 번째 숫자 17을 최댓값으로 기억 (최댓값: 17)
2. 두 번째 숫자 92를 현재 최댓값 17과 비교
   92는 17보다 크므로 최댓값을 92로 바꿔 기억 (최댓값: 92)
3. 세 번째 숫자 18을 현재 최댓값 92와 비교
   18은 92보다 작으므로 지나감 (최댓값: 92)
   4~7. 네 번째 숫자부터 일곱 번째 숫자까지 같은 과정 반복
4. 마지막 숫자 42를 현재 최댓값 92와 비교
   42는 92보다 작으므로 지나감 (최댓값: 92)
5. 마지막으로 기억된 92가 주어진 숫자 중 최댓값

# 최댓값 구하기
# 입력: 숫자가 n개 들어 있는 리스트
# 출력: 숫자 n개 중 최댓값

def find_max(a):
	n = len(a)				# 입력 크기 n
    max_v = a[0]			# 리스트의 첫 번째 값을 최댓값으로 기억
    for i in range(1, n):	# 1부터 n-1까지 반복
    	if a[i] > max_v:	# 이번 값이 현재까지 기억된 최댓값보다 크면
        	max_v = a[i]	# 최댓값을 변경
    return max_v
    
v = [17, 92, 18, 33, 58, 7, 33, 42]
print(find_max(v))			# 실행결과: 92

최댓값 구하기 계산 복잡도(시간 복잡도)

• 입력 크기가 n일 때, 즉 숫자 n개 중에서 최댓값을 구할 경우 자료 개수 n은 리스트 a의 크기인 len(a)로 쉽게 구할 수 있습니다.

for i in range(1, n):
반복문 안에 크기를 비교하는 판단 구문(if a[i] > max_v:)이 있어 자료 n개 중에서 최댓값을 찾으려면 비교를 n-1번 해야 합니다.

이때 계산 복잡도는 n이 굉장히 커질 때는 n번과 n-1번의 차이가 무의미하므로 간단히 O(n)으로 표현한다.

계산 복잡도 O(n)의 가장 중요한 특징

• 입력 크기와 계산 시간이 대체로 비례한다는 것
  바꿔 말하면 숫자 10,000개 중 최댓값을 찾는 데 걸리는 시간이 10초였다면 20,000개를 입력할 때는 대략 20초가 걸릴 것으로 예상할 수 있다.

병렬적 복잡도의 경우

위와같이 n이 8일 때 멀티 프로세스일 경우 3번의 복잡도를 갖기 때문에 O(log2n)으로 표현할 수 있다.