Python algorithm 개념 및 실습 - 최댓값, 최솟값

알고리즘이란 ?

• 어떤 일을 하기 위한 명령의 집합
• 문제 해결 방법을 추상화하여 각 절차를 논리적으로 기술해 놓은 것
• 어떤 문제를 해결하기 위한 절차나 방법

 

알고리즘 복잡도

• Complexity
  • 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한가?
• 알고리즘의 성능을 객관적으로 평가하는 기준
  • 시간복잡도(time complexity) : 실행 횟수로 판단
  • 공간복잡도(space complexity) : 기억공간과 파일 공간의 사용량
• 빅오 표기법 ( Big O Notation)
  • 알고리즘이 얼마나 빠른지 표시하는 방법
  • 입력 데이터 크기 증가할 때 알고리즘 연산 시간(횟수)의 증가 방식
  • 연산의 횟수를 비교함
  • O(n) : 계산 복잡도 
    • O : 빅 O
    • n : 연산 횟수
    • O(1) : 입력 크기 n과 계산 복잡도가 무관 할때 ex) n(n+1)/2
    • O(logn) : 입력 크기 n의 로그 값에 비례하여 증가 ex) 이분탐색
    • O(n) : 입력 크기 n에 비례하여 복잡도 증가 ex) 최댓값, 순차탐색
    • O(nlogn) : 입력 크기 n과 로그 n 값의 곱에 비례하여 복잡도 증가 ex) 병합정렬, 퀵정렬
    • O(n²) : 입력 크기 n의 제곱에 비례하여 복잡도 증가 ex) 선택정렬, 삽입정렬
    • O(n₂) : 입력 크기가 n 일 때, 2의 n 제곱 값에 비례하여 복잡도 증가 ex)하노이의 탑

 

 

리스트 안에서 가장 큰 숫자 찾기(= 최대값구하기)

 [17,92,18,33,58,7,33,42]

def find_max(list1):

# 리스트 크기 ==루프

    size = len(list1)

    # 리스트 첫번째 요소 max에 담기

    max = list1[0]

    for i in range(1, size):

        if max < list1[i]:

            max = list1[i]

    # for문이 끝난 후에 max값을 돌려주면 됨

    return max

# 가장 큰 값이 있는 위치 번호 돌려받기

def find_max1(list1):

    size = len(list1)

# 리스트 0번 index 를 max_idx 에 담기

    max_idx = 0

    for i in range(1, size):

        if list1[max_idx] < list1[i]:

            max_idx = i

    return max_idx

# 테스트

if __name__ == "__main__":

    list1 = [17, 92, 18, 33, 58, 7, 33, 42]

    print("가장 큰 숫자", find_max(list1))

    max_idx = find_max1(list1)

    print("가장 큰 숫자가 있는 위치 {}, 가장 큰 숫자 {}".format(max_idx, list1[max_idx]))

 

 

숫자 n개를 리스트에 입력받아 최솟값 구하기

# 숫자 입력 받은 후 list1에 추가

# q라는 문자가 입력되면 리스트 추가하는걸 종료

def num_input(list1):

    i = 1

    print("리스트에 추가할 숫자를 입력하세요\n 숫자 추가를 끝내기 위해서는 q를 입력하세요")

    while True:

        print(str(i), ": ", end="")

        num = input()

        if num != "q":

            list1.append(int(num))

        else:

            break

        i = i + 1

# 최소값 구하기

def find_min(list1):

    # 리스트 첫번째 요소 min에 담기

    min = list1[0]

    size = len(list1)

    for i in range(1, size):

        if min > list1[i]:

            min = list1[i]

    # for문이 끝난 후에 min값을 돌려주면 됨

    return min

if __name__ == "__main__":

    list1 = list()  # 비어있는 리스트 생성

    num_input(list1)

    print("최소값 : ", find_min(list1))