안녕하세요 와우멍입니다.
오늘은 알고리즘 기초지식을 쌓기 위해 읽고 있는 '필수알고리즘 with 파이썬'을 이어서 정리하겠습니다.
이전글 링크
스택(Stack) 알고리즘
- 입력과 출력을 한 방향으로 제한한 알고리즘
(⇔ 배열은 인덱스를 통해 어느 곳이든 엑세스가 가능)
(⇔ 연결리스트는 링크 통해서 노드를 검색하고, 새로운 노드를 중간에 삽입하거나 기존의 노드를 삭제하는 것이 가능, 삽입될 위치를 검색하고 링크를 연결시켜야 하므로 간단하지는 않지만)
- 스택은 차곡차곡 쌓는 개념, LIFO(Last In First Out)
- 위(Back)에 쌓는 것이 push, 꺼내는 것이 pop.
* Undo (Ctrl + Z)할 때 사용하면 효율적이겠지
스택(Stack) 예제 - 1. 기본
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
def push(item):
stack.append(item)
def pop():
return stack.pop()
if __name__=='__main__':
stack=[]
push(1)
push(2)
push(3)
print("Stack now:", stack)
while stack:
pop()
print("Stack now: {}".format(stack))
|
cs |
⇒ __main__에서 빈 리스트인 stack에 1, 2, 3이 순서대로 쌓여서 [1, 2, 3]이 된 것을 확인
⇒ while문에서 stack의 원소가 있는 동안 pop을 하는데, 역순으로 3, 2, 1순으로 버려지는 것을 볼 수 있다.
스택 예제 - 2. 계산기
|
1
2
3
4
5
6
7
8
|
if operator == '+':
ret = operand_1 + operand_2
elif operator == '-':
ret = operand_1 - operand_2
elif operator == '*':
ret = operand_1 * operand_2
elif operator == '/':
ret = operand_1 // operand_2
|
cs |
- 계산기라는걸 단순히 생각해보면 다음과 같지만, 계산할 때 곱하기와 나누기가 먼저 수행되어야 하고 또 괄호가 있으면 괄호 안의 계산이 먼저 수행되어야 한다.
- 이 과정에서는 피연산자(operand)와 연산자(operator)를 나눠서 stack함. 첫 단계에서, 피연산자 2개와 연산자 1개를 각각 pop해서 계산 후 다시 stack, 다음에 피연산자 2개와 연산자 1개를 pop해서 결과 계산. 다만, 이러면 우선순위가 순서와 다른 1+2*3의 결과는 달라지겠지.
- stack할 때, 제일 위의 연산자와 push할 연산자를 비교하여 새로 저장할 연산자의 우선순위가 높으면 그대로 push하는 방식으로 연산자와 피연사자를 쌓는다. 자세한 건 아래 두 예제를 비교하면서 이해해봅시다.
예제) 2 * 3 + 1 과정
1. (2 * 3)을 피연산자와 연산자 그룹에 각각 push
- 피연산자(Operand): [2, 3]
- 연산자(Operator): [*]
2. 1과 +을 push하는데, +는 *보다 우선순위가 낮으니 있던 애들을 꺼내서 계산후 먼저 push
- 피연산자(Operand): [6, 1]
- 연산자(Operator): [+]
3. [6, 1]과 [+]가 꺼내서 계산
- 6 + 1 해서 7이 나옴.
예제) 2 + 3 * 1 과정
1. (2 + 3)을 피연산자와 연산자 그룹에 각각 push
- 피연산자(Operand): [2, 3]
- 연산자(Operator): [+]
2. *와 1을 push하는데, 우선순위 *가 높으니 그대로 push
- 피연산자(Operand): [2, 3, 1]
- 연산자(Operator): [+, *]
3. 위부터 차례대로 3, 1, *를 꺼내서 계산후 피연산자에 push
- 피연산자(Operand): [2, 3]
- 연산자(Operator): [+]
4. [2, 3]과 [+]를 꺼내서 계산
- 2 + 3 해서 5가 나옴.
**그럼 더 긴 경우에 대해서는 어떻게 되는거지? 연산자끼리만 말고 뒤에 괄호도 있고 하면..? (TBA)
큐(Queue) 알고리즘
- Stack와 비슷하지만, 큐(Queue)는 LIFO가 아닌 FIFO(First In First Out)
- 매표소에서 줄서는 것과 비슷, 데이터가 들어오는 위치는 뒤(Rear or Back), 나가는 부분은 앞(Front)라 정의.
- 입력은 Enqueue(파이썬에서 put): 매표소에 줄을 서는 것
- 출력은 Dequeue(파이썬에서 get): 온 순서대로 표를 사는 것
(보급창고가 생각나네요 ㅋㅋㅋㅋ 선입선출)
- 스택과 달리 배열에서 더 편리하게 이용
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
def put(item):
queue.append(item)
def get():
return queue.pop(0)
if __name__ == '__main__':
queue = []
put(1)
put(2)
put(3)
print('Queue Now: ', queue)
while queue:
get()
print("Queue now: {}".format(queue))
|
cs |
위의 stack에서의 pop에서와 달리, 먼저 입력된 순으로 1, 2, 3이 순차적으로 방출되는 것을 볼 수 있다.
** 여기서 get을 구현하기 위해서는 pop(0)로 해줘야 한다 (0번째 성분을 뽑는다는 뜻). 아니면 queue 모듈의 Queue()라는 Class를 이용하는 것으로 쉽게 할 수도 있다(put과 get이 Cython으로 자체구현되어 있음)
** 단순하게 생각하면 맨 앞의 한칸을 뺀다는 개념이지만, 실제 과정을 보면 맨앞의 한칸을 뽑으면서 비우고, 그 뒤의 데이터들을 한칸씩 앞으로 당기는 작업이 따르기 때문에, n번의 프로세스를 거치며 퍼포먼스가 떨어진다.
- 큐(Queue)는 미리 정해놓은 배열의 크기만큼으로 사용할 수 밖에 없음. 그런데 이걸 원형 큐(Circular Queue)의 형태로 사용하면, 배열 전체 크기와 상관없이 효율적으로 사용할 수 있다.
- 앞부분이 비는 것을 활용해서, 배열의 마지막 부분을 쓰면 다시 처음부터 큐를 채우기 시작하는 형태의 큐 (마지막 위치가 시작위치와 연결된다는 점에서 Ring Buffer라고도 함)
- dequeue(=get)을 하게 되면 front포인터가 뒤로 이동하고, enqueue(=put)을 하게 되면 rear포인터가 앞으로 이동하고, 이 두개의 포인터가 만나면 공간이 없다는 에러가 발생하니 잘 조절해서 떨어지게 컨트롤한다. (포인터는 위치를 지정한다고 생각하면 됨, C에서의 개념)
스택(Stack)와 큐(Queue)에 대해서는 이정도로 정리하겠습니다.
혹시 잘못된 것이나 추가하면 좋은 것이 있다면 편히 글 남겨주세요 :-)
'Hobby > Hobby_4 - Coding' 카테고리의 다른 글
| [코딩실전] 주식봇 도전 - 3. 크레온 및 코드 자동실행 (2) | 2021.01.31 |
|---|---|
| [코딩 실습] 네이버 크롤링을 통한 주식 종목별 검색량 확인하기 - 1 (2) | 2021.01.27 |
| [코딩실전] 주식봇 도전 - 2. 변동성돌파 전략 예제 구현 (0) | 2021.01.25 |
| [코딩 실전] 주식봇 도전 - 1.파이썬 및 기타 환경 구축 (8) | 2021.01.02 |
| [패스트캠퍼스 후기 1] Python Programming 기초 - 1 (2) | 2020.11.03 |
댓글