[수업목표]
1. 개발자들에게 알고리즘 공부가 필요한 이유 이해
2. 알고리즘을 학습하기 위한 기본 코드 구현력 높이기
3. 시간 복잡도 및 공간 복잡도에 대한 이해

알고리즘이란?

  • 문제의 해결을 위해 입력된 자료를 토대로 하여 원하는 답의 출력을 유도하는 규칙의 집합.
  • 하나의 문제에 대해 여러가지 답이 존재할 수 있음.

시간 복잡도란?

  • 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계.
  • 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘.

공간 복잡도란?

  • 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계. (컴퓨터 내 저장공간의 활용적 측면)
  • 입력값이 늘어나도 할당해야하는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘.


시간 복잡도 vs 공간 복잡도

예제 : 다음과 같은 문자열을 입력 받을 때, 어떤 알파벳이 가장 많이 포함되어있는지 반환하시오.

input = "Hello My name is Nathan"

답안 1 (26개의 알파벳에 대한 횟수 적을 공간을 직접 리스트 내에 마련하기 + 최빈값을 그때 그때 비교하기)

def find_max_occurred_alphabet(string):
    alphabet_array = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
    max_occurence = 0
    max_alphabet = alphabet_array[0]
    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:
            if char == alphabet:
                occurrence += 1
                
        if occurrence > max_occurence:
            max_occurence = occurrence
            max_alphabet = alphabet

    return max_alphabet
  • 위의 코드를 연산한 횟수 (주요 연산만 포함)
    1. alphabet_array의 길이 X 대입 연산 1회
    2. alphabet_array의 길이 X string의 길이 X (비교연산 1회 + 대입 연산 1회)
    3. alphabet_array의 길이 X (비교연산 1회 + 대입 연산 2회)

  • 연산 횟수 결과 : 26 * (1 + 2*N + 3) = 52N + 104 [N만큼의 시간 소요]

답안 2 (for 반복문과 ASCII CODE를 이용하여 리스트 마련하기)

def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26
    for i in string:
        if i.isalpha() is True:
            alphabet_occurrence_array[ord(i)-ord('a')] += 1

    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]
        
        if alphabet_occurrence > max_occurrence:
            max_alphabet_index = index
            max_occurrence = alphabet_occurrence
    return chr(max_alphabet_index + ord('a'))
  • 위의 코드를 연산한 횟수 (주요 연산만 포함)
    1. string의 길이 X (비교 연산 1번 + 대입 연산 1번)
    2. 대입 연산 2번
    3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)

  • 연산 횟수 결과 : N * (1 + 1) + 2 + 26 * (1 + 3) = 2N + 106 [N만큼의 시간 소요]

비교 (답안1, 답안2, N^2)

N의길이답안1(52N + 104)답안2(2N+106)N^2
11561081
10624126100
1005304306100000
10005210421061000000
  • 이 표를 통해 알 수 있는 2가지 사실
    1. (52N + 104)(2N+106)이든 N^2에 비해서는 아무 것도 아니다.
    2. 공간 복잡도보다는 시간 복잡도를 더 신경써야 한다.


점근 표기법(Asymptotic notation)이란?

  • 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법.
  • ~한 방법은 N정도의 시간이 걸리겠구나 -> 점근 표기법의 일종

점근 표기법의 종류

  1. 빅오(Big-O)표기법
    • 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지 나타냄
    • O(N)과 같이 나타냄

  2. 빅 오메가(Big-Ω) 표기법
    • 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지 나타냄
    • Ω(1)과 같이 나타냄
  • 보통은 최악의 성능을 나타내는 빅오(Big-O) 표기법을 사용하여 알고리즘의 효율성을 판단한다.
profile
나는 날마다 모든 면에서 점점 더 나아지고 있다.

0개의 댓글