알고리즘 선택 트랙과정 [1일차]

1. (김민승)이 생각하는 알고리즘

: 어떤 문제를 효율적으로 해결하기 위한 방법

여기서 "효율적으로"라는 말이 애매하게 들릴 수 있다.

그래서 그 효율적이라는 것을 우린 시간복잡도를 통해서 확인할 수 있다.

시간복잡도란 알고리즘이 걸린 시간을 표기하는 방식으로 빅오 표기법와 빅큐 표기법이 있다.

여기서 우린 빅오 표기법을 자주 사용하며 빅오 표기법으로는 이런 식으로 설계되어있다.

 

 

2. (김민승)이 생각하는 자료구조란

: 자료구조는 알고리즘을 구현하는데 필요한 도구라고 생각한다.

우리가 어떤 알고리즘이 굉장히 빠른 알고리즘이라고 부른다.

내가 생각하는 빠른 알고리즘은 주어진 데이터를 빨리 가져오는 것이 빠른 알고리즘이라고 생각한다.

즉 결국엔 알고리즘을 잘 구현하기 위해서는 데이터를 잘 가져올 수 있도록 설계해야 한다.

그리고 이런 설계를 하는데 필요한 도구가 바로 자료구조라고 생각한다.

그래서 자료구조에 예시에는 스택,큐,리스트,딕셔너리,연결 딕셔너리 등이 있는 것이다.

 

[문제 1] 백준 알파벳 찾기

 

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

 

문제 풀이

1. 알고리즘 설계

#1.a~z까지 들어있는 리스트를 생성한다.

#2. 빈 딕셔너리를 생성한다.(자료구조)

#2. 주어진 리스트를 돌면서 주어진 문자열에 a~z가 있는지 확인한다.

#3. 만약 있다면 이전에 딕셔너리에 이미 저장되어있는지를 확인한다.

#4. 만약 없다면 딕셔너리에 해당 문자열은 -1로 저장한다.

# # 딕셔너러의 키값을 반환한다.

2. 자료구조 구현

(1) 사용할 자료 구조 = 딕셔너리

alphaList = ['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']

alphaDict = {}

sentence = int(input())

for alpha in alphaList:

if alpha in sentence and alphaDict.get(alpha) == None:

alphaDict[alpha] = sentence.index(alpha)

else:

alphaDict[alpha] = -1

print(alphaDict)

print(' '.join([str(value) for value in alphaDict.values()]))

시간 복잡도 계산 => 시간 복잡도 측면에서 본다면 크게 3가지 부분을 신경써야 한다. 첫번재는 for문

두번째는 index() 세번째는 마지막 for문이다. 검색을 통해 알아보니 index()함수의 시간복잡도는 o(k)이라고 한다.

그 이유는 주어진 문자열을 전부 탐색할 수 있기 때문에 즉 full scaning을 할수도 있기 때문에 결국 주어진 리스트나 문자열에 따라서 시간복잡도는 달라질 수 있다.