[ALGORITHMS]문제 02 최댓값 찾기

문제 2

최댓값 찾기

- 주어진 n개의 숫자 중 가장 큰 숫자를 찾아보세요

1. 리스트

17, 92, 18, 33, 58, 7, 33, 42와 같은 숫자 여러 개는 파이썬의 리스트 기능을 이용하면 쉽게 관리 할 수 있습니다.

리스트(list)는 정보 여러 개를 하나로 묶어 저장하고 관리할 수 있는 기능입니다.

리스트를 만드려면 대괄호([]) 안에 정보 여러 개를 쉼표(,)로 구분하여 적어 주면 됩니다.

ex)

첫 번째 문장의 a=[5,7,9]는 5,7,9라는 정수 세 개를 묶은 리스트를 만들어 a에 저장합니다

두 번째 문장에서 a를 입력하면 [5,7,9]가 표시되면서 a가 5,7,9라는 정보 세 개를 묶어 놓은 리스트라고 알려줍니다.

파이썬 리스트에서 가장 주의할 점은 자료 위치를 1이 아닌 0부터 센다는 점입니다.

예를 들어 a[0]은 a의 0번 위치 값이므로 5가 표시됩니다.

a[-1]은 파이썬 리스트에서 위치번호 -1은 리스트의 끝에서 첫번째 값 즉 마지막값을 의미합니다.

len() 함수를 사용하면 어떤 리스트 안에 들어 있는 자료 개수를 알 수 있습니다.

*자주 쓰는 리스트 기능

2. 최댓값을 찾는 알고리즘

-17, 92, 18, 33, 58, 7, 33, 42에서 최댓값 찾기

1. 첫 번째 숫자 17을 최댓값으로 기억합니다(최댓값 : 17)

2. 두 번째 숫자 92를 현재 최댓값 17과 비교합니다.

92는 17보다 크므로 92로 바꿔 기억합니다(최댓값 : 92)

3. 이 과정을 일곱 번째 숫자까지 반복합니다

4. 마지막 숫자 42를 현재 최댓값 92와 비교합니다. 

42는 92보다 작으므로 지나갑니다.(최댓값 : 92)

5. 마지막으로 기억된 92가 주어진 숫자 중에 최댓값입니다.

*최댓값을 구하는 알고리즘 

3. 알고리즘 분석

최갯값 구하기 프로그램의 계산 복잡도(시간 복잡도)를 생각해 봅시다. 

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

그렇다면 최댓값을 구하는 데 컴퓨터가 해야 하는 가장 중요한 계산은 무엇일까요?

두 값중 어느것이 더 큰지를 판단하는 '비교'입니다

for i in range(1,n):에서 자료 n개중에서 최댓값을 찾으려면 비교를 n-1번 해야합니다

그래서 O(n)이 됩니다!

4. 응용하기

이번에는 문제를 살짝 바꿔 보겠습니다.

* 리스트에 숫자가 n개 있을 때 가장 큰 값이 있는 위치 번호를 돌려주는 알고리즘을 만들어 보세요.

[17,92,18,33,58,7,33,42]에서는 두 번째 나오는 값인 92가 최댓값이므로 이 문제의 결괏값은 1입니다.

* 최댓값의 위치를 구하는 알고리즘

* 연습 문제

숫자 n개를 리스트로 입력 받아 최솟값을 구하는 프로그램을 만들어 보세요

정답)