모두의 알고리즘 문제 02. 최댓값 찾기

def find_max (a):
    n=len(a) # 입력받은 리스트의 길이를 변수n에 저장
    max_v = a[0] #최대값 변수에 리스트에 첫번째 원소를 넣음
    for i in range (1, n): # 0번째 원소는 최대값 변수에 넣었으니 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

위는 리스트의 최댓값을 구하는 프로그램이다.

 

최댓값 구하기 프로그램의 시간복잡도를 생각해보자.

 

최댓값 구하기 프로그램은 입력받은 리스트의 길이가 1 늘어날수록 비교 횟수도 1 늘어난다. 자료 n개 중에서 최댓값을 찾으려면 비교를 n-1번 해야한다(첫 번째 값은 변수에 넣어서 비교할 기준이 되어야하므로 n번이 아니라 n-1번 비교한다).

 

즉 자료값의 크기와 계산 횟수가 정비례 관계이므로 시간복잡도는 O(n)으로 표현한다.

 

O(n)의 가장 중요한 특징은 입력 크기와 계산 시간이 대체로 비례한다는 것이다.

 

def find_max_idx(a):
    n=len(a) # 리스트a의 길이변수 n
    max_idx=0 # 리스트 중 0번 위치를 최대값 위치로 기억
    for i in range (1, n):
        if a[i] > a[max_idx]: # 만약 i번째 원소가 max_idx번째 원소보다 크다면
            max_idx=i # max_idx에 i를 저장한다
    return max_idx

v=[17, 92, 18, 33, 58, 7, 33, 42]
print(find_max_idx(v))
# 출력: 1

위는 최댓값의 위치를 구하는 알고리즘이다. 상술한 최댓값 구하기 알고리즘을 약간 변형했다.