07.11 TIL

오늘은 알고리즘을 배웠다.

점근 표기법
알고리즘의 성능을 수학적으로 표기하는 방법입니다. 알고리즘의 “효율성”을 평가하는 방법입니다.
빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지,
빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기합니다.

 

시간 복잡도

- 입력값과 문제를 해결하는데 걸리는 시간과의 상관관계

- 입력값이 2배로 늘어났을때 문제를 해결하는데 걸리는 시간은 몇 배로 늘어났는지 파악

 

공간 복잡도

- 입력값과 문제를 해결하는데 걸리는 공간과의 상관관계

- 입력값이 2배로 늘어났을때 문제를 해결하는데 걸리는 공간은 몇 배로 늘어났는지 파악

 

- 상대적으로 시간복잡도가 조금더 중요

문제
알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다.

출력
각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다.

만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다.

import string
def get_idx(word):
    # point 1. ord
    # point 2. O(n^2) -> O(n)
    result = [-1]*len(string.ascii_lowercase)
    for i in range(len(word)):
        idx = ord(word[i]) - 97
        if result[idx] == -1:
            result[idx] = i
    print(' '.join([str(num) for num in result]))

get_idx('baekjoon')

 

 

 출력값 = 1 0 -1 -1 2 -1 -1 -1 -1 4 3 -1 -1 7 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

 

이렇게 나온다.

 

여기서 배운건 아스키코드이다. 

 

요렇게 생겼다. 그것도 아주 복잡하게.

result = [-1]*len(string.ascii_lowercase)

이 코드는 소문자 아스키코드를 a ~ z 까지 -1 이라는 리스트에 넣어준다.

 

for i in range(len(word)):
        idx = ord(word[i]) - 97
        if result[idx] == -1:
            result[idx] = i
    print(' '.join([str(num) for num in result]))

get_idx('baekjoon')

솔직히 여기서 부터는 머리로는 이해를 하는데 뭔가 설명을 못하겠다. 하지만 일단 머리로라도 어느정도 이해를 했으니 만족한다.

 

ord = 문자를 인지하고 그 문자에 해당하는 아스키코드로 변환

 

오늘도 고생했다!!