알고리즘 1주차 - 개요/시간복잡도/공간복잡도

기술개발/Algorithm 2021. 1. 11. 15:17

반응형

본 포스팅은 스파르타코딩클럽 - 알고리즘 강의를 들으며 정리한 자료입니다.

 

진행 순서

  • 1주차: 시간/공간 복잡도, 알고리즘 구현력 기르기
  • 2주차: 어레이, 링크드 리스트, 이분탐색, 재귀
  • 3주차: 정렬, 스택, 큐, 해쉬
  • 4주차: 힙, BFS, DFS, 동적 프로그래밍
  • 5주차: 종합 알고리즘 문제 풀이

알고리즘 공부가 필요한 이유

  • 어떤 문제의 해결을 위하여, 입력된 자료를 토대로 원하는 출력을 유도하여 내는 규칙의 집합.
  • 여러 단계의 유한 집합으로 구성되며 각 단계는 하나 또는 그 이상의 연산을 필요로 한다.
  • 어떤 문제가 있으면 그것을 해결하기 위한 여러 동작들의 모임
  • 좋은 개발자=좋은 프로그램 구현=적은 공간을 이용해서 빠른 속도로 수행되는 프로그램=자료구조나 접근방법을 알아야함
  • 코딩테스트: 수많은 회사들이 코딩테스트를 통해 개발자를 구인. 개발자의 필수 관문
  • 현업에서는 알고리즘을 처음부터 구현할 필요보다는 이미 잘 만들어진 것을 이해하고 쓰면 됨

알고리즘을 학습하기 위한 기본 코드 구현력

개발환경 세팅

  • 파이참 세팅

파이참 열은 후 "새 프로젝트 클릭" → 프로젝트 저장 폴더 위치 선택 → 파이썬 3 버전 확인후 Create

  • 가상환경

각 프로젝트마다 요구되는 개발 환경(패키지 버전 등)을 독립적으로 관리하기 위해 venv라는 가상환경이 자동으로 생성되고 이곳에 환경 세팅을 함. 우리는 여기서는 사용안함.

  • 폴더 생성

week_1 디렉토리 생성 및 00_hello.py 라는 파일 생성

해당 문구 코딩

해당 편집기 안에서 마우스 우클릭 버튼 및 run 클릭

해당 콘솔에 이와 같이 노출된다면 성공

팁: 코드를 작성할 경우 띄어쓰기 등이 필요할 경우 언더바(_)로 대체함. 컴퓨터는 기본적으로 특수 문자를 싫어함.

연습문제 1

  • 최대값 찾기
input = [3, 5, 6, 1, 2, 4]

def find_max_num(array):
    return 1

result = find_max_num(input)
print(result)

해당 코드 스니펫을 기반으로 리스트에서 최대값 찾기

# 내 코드 
input = [3, 5, 6, 1, 2, 4]

def find_max_num(array):
    max_num = max(input)
    return max_num

result = find_max_num(input)
print(result)
# 튜터 방식1
def find_max_num(array):
    for num in array:
        for compare_num in array:
            if num < compare_num:
                break
        else:
            return num
# 튜터 방식2
def find_max_num(array):
    max_num = array[0]
    for num in array:
        if num > max_num:
            max_num = num
    return max_num

튜터의 방식 2가지 중에 어떠한 방식이 효율적인 방식일까?

본인의 생각은 1번 방식은 for문이 2번이기에 n^2, 2번 방식은 for문이 1번이기에 n일 것이다.

2번 방식일 것이다.

연습문제 2

  • 최빈값 찾기
input = "hello my name is sparta"


def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26
    # 이 부분을 채워보세요!
    return alphabet_occurrence_array


result = find_max_occurred_alphabet(input)
print(result)
# 내 코드
def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26
    # 이 부분을 채워보세요!
    for str in string:
        if str.isalpha():
            alphabet_occurrence_array[ord(str) - ord('a')] += 1
    max_idx = alphabet_occurrence_array.index(max(alphabet_occurrence_array))
    return chr(max_idx + 97)
# 튜터 방식1
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", "x", "y", "z"]
    max_occurrence = 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_occurrence:
            max_occurrence = occurrence
            max_alphabet = alphabet
    return max_alphabet
# 튜터 방식2
def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26
    # 이 부분을 채워보세요!
    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord("a")
        alphabet_occurrence_array[arr_index] += 1

    max_occurence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurence = alphabet_occurrence_array[index]

        if alphabet_occurence > max_occurence:
            max_alphabet_index = index
            max_occurence = alphabet_occurence
    return chr(max_alphabet_index + ord("a"))

튜터의 방식 2가지 중에 어떠한 방식이 효율적인 방식일까?

본인의 생각은 1번 방식은 for문이 2번이기에 n^2, 2번 방식은 for문이 2번이지만 중첩되지 않기에 2n일 것이다.

(이 부분은 틀렸는지 맞는지 정확하게 모르겠다.)

2번 방식일 것이다.

시간 복잡도, 공간 복잡도

  • 시간복잡도란?

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

  • 이전의 '최대값 찾기 알고리즘'의 시간 복잡도 비교
    1. for문 2번이 중첩되었고 if문의 비교 연산 1번이 실행되었기에 N X N = N^2
    1. 대입 연산 1번 실행, for문 1번 실행, 비교 연산 1번 실행, 대입 연산 1번 실행이기에 1 + 2 X N = 2N + 1

    2번의 경우가 유리하다. 위에서 상수는 버리고 입력값에 비례해서 어느 정도 증가하는지만 판단하면 됨.

    예) 상수 연산량이 필요하다 → 1 만큼의 연산량이 필요하다.

  • 공간복잡도란?

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

  • 이전의 "최빈 알파벳 찾기 알고리즘"의 공간 복잡도 비교

    (저장하는 데이터의 양이 1개의 공간을 사용한다고 가정하고 계산)

    1. a-z까지 26개 공간, max_occurence에서 1개, max_alphabet에서 1개의 공간, for 문 속 occurence에서 1개의 공간을 사용하여 29공간
    1. alphabet_occurrence_list에서 26개, arr_index에서 1개, max_occurence에서 1개, max_alphabet_index에서 1개, alphabet_occurrence에서 1개를 사용하여 30공간

    그렇다면 공간을 더 적게 쓴 1번째 방법이 더 효율적인걸까?

    아니다.

    29와 30 모두 상수라 큰 상관이 없고 이때는 다시 시간 복잡도로 비교한다.

    대부분의 문제에서는 알고리즘의 성능이 공간에 의해서 결정되지 않으므로 공간복잡도 보다는 시간복잡도를 보다 중요하게 생각해야함.

  • 위 둘의 시간 복잡도 비교
    		 for alphabet in alphabet_array:    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
        occurrence = 0                  # 대입 연산 1번 실행
        for char in string:             # string 의 길이만큼 아래 연산이 실행
            if char == alphabet:        # 비교 연산 1번 실행
                occurrence += 1         # 대입 연산 1번 실행 

        if occurrence > max_occurrence: # 비교 연산 1번 실행
            max_alphabet = alphabet     # 대입 연산 1번 실행
            max_occurrence = number     # 대입 연산 1번 실행
    • alphabet_array의 길이 x 대입 연산 1
    • alphabet_array의 길이 x string의 길이 x (비교1 +연산1)
    • alphabet_array의 길이 x (비교1 + 연산1)

    26 * (1 + 2 * N + 2) = 52N + 104 → 계수와 상수를 버린다 → N만큼의 시간이 필요하다.

    2. 

        for char in string:        # string 의 길이만큼 아래 연산이 실행
        if not char.isalpha(): # 비교 연산 1번 실행
            continue
        arr_index = ord(char) - ord('a')         # 대입 연산 1번 실행 
        alphabet_occurrence_list[arr_index] += 1 # 대입 연산 1번 실행 

    max_occurrence = 0        # 대입 연산 1번 실행 
    max_alphabet_index = 0    # 대입 연산 1번 실행 
    for index in range(len(alphabet_occurrence_list)):    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
        alphabet_occurrence = alphabet_occurrence_list[index] # 대입 연산 1번 실행 
        if alphabet_occurrence > max_occurrence: # 비교 연산 1번 실행 
            max_occurrence = alphabet_occurrence # 대입 연산 1번 실행 
            max_alphabet_index = index           # 대입 연산 1번 실행
    • string의 길이 x (비교연산1, 대입연산 2)
    • 대입연산 2
    • albphabet_array의 길이 x (비교1 + 대입3)

    N * (1+2) + 2 + 26 * (1+3) = 3N + 106 → N만큼의 시간이 필요하다.

    • 둘다 N^2에 비해서는 매우 적다.
    • 공간 복잡도 보다는 시간 복잡도를 더 신경 써야 한다.
    • 그래도 2번이 더 좋은 알고리즘이다.

반응형

'기술개발 > Algorithm' 카테고리의 다른 글

알고리즘 2주차 - 숙제  (0) 2021.01.19
알고리즘 2주차 - 이진탐색, 재귀  (0) 2021.01.16
알고리즘 2주차 - 링크드리스트  (0) 2021.01.14
알고리즘 1주차 - 숙제  (0) 2021.01.13
알고리즘 1주차 - 점근표기법, 연습문제  (0) 2021.01.12