2. 최댓값 찾기

* 책: 모두의 알고리즘 with 파이썬

주어진 숫자 n개 중 가장 큰 숫자를 찾는 알고리즘을 만들어 보세요.

 

1. 관련 개념: python 리스트 다루기

 

# 리스트 개념 확인
 
a = [1,2,3,4,5,6,7,8,9,10]
a[0] # 1
a[9] # 10; n개 요소를 가진 리스트의 마지막 요소는 n-1 인덱스로 구할 수 있음
a[-1] # 10
a[-2] # 9
a[-10] # 마이너스 인덱스 사용 시 n개 요소를 가진 리스트의 첫번째 요소는 -n 인덱스
 
 
 
# 리스트에서 많이 쓰이는 함수들 
# len(a), a.append(x), a.clear()는 생략
 
# a.insert(i, x) # a 라는 리스트의 i번째에 x 요소를 끼워넣음
#a.insert(10, 11)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
 
# a.pop(i) # a 라는 리스트의 i번째 요소를 빼버리고 함수의 결괏값으로 돌려줌, 아무것도 없으면 마지막 요소를 빼버림 
a.pop() # 11 # a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
a.pop(8) # 9 # a = [1, 2, 3, 4, 5, 6, 7, 8, 10]
 
 
# x in a 리스트 a안에 x라는 값이 있는지 없는지 확인
9 in a # False
 
#a.insert(8,9) # [1, 2, 3, 4, 5, 6, 7, 8, 10, 9]
9 in a # True

 

2. 최댓값을구하는 알고리즘: O(n)

1. 숫자들을 리스트에 잘 싼다.
2. 리스트 첫번째 요소부터 순차적으로 비교한다.
3. 가장 큰 값이 나왔을 때 멈춘다.

v = [17, 92, 18, 33, 58, 7, 33, 42]
 
def  find_max(a):
    n = len(a) # n값 초기화
    max_nm = a[0] # max값 초기화
    for i in range(1, n):
        if max_nm < a[i]:
            max_nm = a[i] # max_nm 값을 if 조건에 따라 새로운 값으로 갱신
        
    return max_nm
 
find_max(v) # 92

 

 

3. 최댓값의 인덱스를 구하는 알고리즘 : O(n)

1. 숫자들을 리스트에 잘 싼다.
2. 리스트 첫번째 요소부터 순차적으로 비교하되 인덱스만 본다.
3. 가장 큰 값이 나왔을 때 멈추고 인덱스를 구한다. 

 

v = [17, 92, 18, 33, 58, 7, 33, 42]
 
# 복잡하고 사서 고생하는 코드 
def  find_max_idx(a):
    n = len(a) # n값 초기화
    max_nm = a[0] # max값 초기화, 초기화 했기 때문에 range가 1부터 시작
    for i in range(1, n):
        if max_nm < a[i]:
            max_nm = a[i]
            idx = i # 인덱스는 곧 i이니라
        
    return idx
    
find_max_idx(v) # 92의 인덱스인 1
 
 
# 더 간단한 방법이 있지롱
def find_max_idx(a):
    n = len(a)
    idx = 0 # 인덱스 초기화, 초기화 했기 떄문에 range가 1부터 시작 
    for i in range(1, n):
        if a[i] > a[idx]:
            idx = i # 조건에 맞는 인덱스로 교체
    
    return idx
 
find_max_idx(v) # 92의 인덱스인 1

 

<연습문제>

리스트에 숫자 n개가 있을 때 가장 작은값을 돌려주는 알고리즘을 만들어보세요. + 인덱스도

 

# max 구하는 것에서 if 연산자만 바꾸면 바로 최솟값 가능 
 
v = [17, 92, 18, 33, 58, 7, 33, 42]
 
def  find_min(a):
    n = len(a) # n값 초기화
    min_nm = a[0] # min값 초기화
    for i in range(1, n):
        if min_nm > a[i]:
            min_nm = a[i]
        
    return min_nm
 
find_min(v) # 7
 
 
 
# 그렇다면 인덱스 구하는 것도? 금방 가능
# 아래는 복잡한 버전 
v = [17, 92, 18, 33, 58, 7, 33, 42]
 
def  find_min_idx(a):
    n = len(a) # n값 초기화

    min_nm = a[0] # min값 초기화
    for i in range(1, n):
        if min_nm > a[i]:
            min_nm = a[i]
        
    return i 

 
find_min(v) # 7의 인덱스인 5
 
 
# 이게 심플한 버전
v = [17, 92, 18, 33, 58, 7, 33, 42]
 
def  find_min_idx(a):
    n = len(a) # n값 초기화
    idx = 0 # idx값 초기화
    for i in range(1, n):
        if a[i] < a[idx]:
            idx = i
            
    return idx
 
find_min_idx(v) # 7의 인덱스인 5