190115 알고리즘-자료구조

자료구조에서 배운 것은 크게

1. 스택 Stack
2. 큐 Queue
3. 덱 Deque

이 세 가지를 배웠다. 그 중 가장 크게 사용하는 것은

import collections
deq = collections.deque()

collections 패키지의 deque를 이용해서 덱을 만들고 매서드인 deq.append()나 deq.pop(), dep.extend(), dep.rotate()를 사용한다.

1. 스택은 Last In First Out 이다.

따라서 맨 뒤에 요소를 넣고 뺄 때 사용한다. 마지막 요소만으로 무언가를 해야할 때 사용한다.

2. 큐는 First In First Out 이다.

따라서 맨 앞에 요소를 넣고 뺄 때 사용한다. 맨 앞 요소만으로 무언가를 해야할 때 사용한다.

3. 덱은 양 끝에서만 자료를 넣고 뺄 수 있다.

따라서 스택과 큐의 개념을 가지고 있으며, collections.deque()를 이용하여 덱을 만든 뒤에, append(), pop(), extend(), rotate() 등의 메서드를 사용한다.

python skill

• 문자열의 대수 비교는 아스키코드를 가지고 한다. 맨 앞 문자가 서로 같으면 사전적으로 자동 비교해준다. ex) apple < application
• 1~100중에서 30~50 구간을 로테이션하고 싶을 때는 나머지 연산을 통해서 로테이션을 구현한다.

for i in range(len(deq)):
    if ord(deq[i]) in range(65, 91):
        result.append(chr(((ord(deq[i]) -65 + 13) % 26) + 65))
    elif ord(deq[i]) in range(97, 123):
        result.append(chr(((ord(deq[i]) + -97 + 13) % 26) + 97))
    else:
        result.append(deq[i])

• 한 리스트(덱)안에서의 대수 비교는 버블 정렬을 통해 구현할 수 있다.
• 버블 정렬은 O(N²) time 이다.