[210628]

Hello Coding 알고리즘

1장. 알고리즘의 소개

들어가는 글

• 알고리즘 : 어떤 일을 하기 위한 명령의 집합

• 성능

  • 여러 알고리즘들의 장단점과 차이점을 이해하고 쓸 줄 알아야 한다.
  • 다른 자료구조 / 알고리즘을 쓰는 것만으로도 성능이 크게 달라질 수 있다.

단순 탐색 simple search

탐색 문제를 풀 때 사용.

• 동작 : 단순히 원소 하나하나를 맞는지 아닌지 일일이 확인하는 방식
• n개의 원소 리스트에서 최대 n번만에 정답을 찾음

이진 탐색 binary search

탐색 문제 search 를 풀 때 사용.

이진 탐색은 매 단계마다 절반의 후보들을 없앨 수 있다.

• input : 정렬된 원소 리스트
• output : 원하는 원소가 있으면 그 위치를 반환. 아니면 null 반환.
• 동작
  • 정렬된 리스트의 중간값부터 탐색 시작.
    • 홀수일 떄는 (홀수 + 1) / 2 로 계산
  • 탐색대상이 중간값보다 작은지 큰지 판단
  • 작은/큰 나머지 절반 리스트의 중간부터 다시 탐색 시작 - 이 과정을 반복
• n개의 원소 리스트에서 최대 log2n번 만에 정답을 찾음

이진 탐색 코드

def binary_search(list, item):
    low = 0
    high = len(list)-1
    
    while low <= high:
        mid = (low + high) / 2
        guess = list[mid]
        
        if guess == item: ## 추측한 값이 정답임 
            return mid
        if guess > item: ## guess가 너무 큼 - 탐색 천장을 mid-1로 설정
            high = mid - 1
        else:   ## guess가 너무 작음
            low = mid - 1
    return None ## 아이템이 리스트에 없음

my_list = [1, 3, 5, 7, 9]

print binary_search(my_list, 3) ## return = 1
print binary_search(my_list, -1) ## return = None

로그의 개념

• 로그는 거듭제곱의 반대말이다.
• 빅오 표기법에서 - 모든 log함수는 log2를 뜻한다 (밑이 2인 로그).
• 밑이 10인 로그에 대해서는 밑을 생략한다.
• logb(a) = b를 몇 번 거듭제곱해야 a가 나올까요?

실행 시간 running time

시간 또는 저장공간 면에서 가장 효율적인 알고리즘을 나타낼 수 있다

• 선형 시간 linear time
  • O(n)
  • n개의 원소가 있다면 n번 추측해야 함 (ex. 단순탐색)
• 로그 시간 logarithmic time
  • O(log n)
  • n개의 원소가 있다면 log n번 추측해야 함 (ex. 이진탐색)

빅오표기법 Big O notation - 기초

어떤 알고리즘이 얼마나 빠른지 표기하는 방법. (시간복잡도 표기)

왜 쓰는가?

• 단순한 '알고리즘의 실행 시간' 이 아닌 '리스트 크기에 따른 알고리즘 실행시간 증가율'을 파악하기 위해.

특징

• 알고리즘의 속도는 '연산 시간'이 아닌 '연산 횟수 증가율'로 측정한다.
  • 입력 데이터의 크기가 늘어날 때, 실행속도가 얼마나 증가하는지 알 수 있다.
• 언제나 최악의 경우를 가정한다.
  • = 최악의 경우라도 탐색이 그 시간보다 느려지지 않음을 보장한다.

많이 쓰이는 빅오 실행시간 5가지

위쪽일수록 빠르고, 아래쪽일수록 느림

• O(log n) 로그 시간 (ex. 이진 탐색)
• O(n) 선형 시간 (ex. 단순 탐색)
• O(n * log n) (ex. 퀵 정렬)
• O(n제곱) (ex. 선택 정렬)
• O(n!) (ex. 외판원 문제)

O(n!) - 외판원 문제 traveling salesperson problem

실행시간이 O(n!)인 알고리즘. (외판원=세일즈맨)

• 문제 : 세일즈맨이 가장 짧은 거리로 n개의 도시를 모두 방문하려 할 때, 도시를 방문하는 모든 경로를 살펴보아야 한다.

• 도시의 수가 n개일 때, 경로 탐색을 위한 연산 횟수는 n!로 증가율이 엄청나게 높다.

  • 1개 = 1
  • 2개 = 2! = 1x2 = 2
  • 3개 = 3! = 1x2x3 = 6
  • 4개 = 4! = 1x2x3x4 = 24
  • 5개 = 5! = 1x2x3x4x5 = 120
  • ...