[프로그래머스 인공지능 스쿨]Day02:어서와! 자료구조와 알고리즘은 처음이지?(2)

8 minute read

12. 스택의 응용 - 수식의 후위 표기법(Postfix Notation)

중위 표기법과 후위 표기법

중위 표기법(infix notation) : 연산자가 피연산자들의 사이에 위치
```
(A+B)*(C+D)
```
후위 표기법(postfix notation) : 연산자가 피연산자들의 뒤에 위치
```
AB+CD+*
```

중위 표현식 -> 후위 표현식

[중위]AB+C -> [후위]ABC+
[중위]A+BC -> [후위]ABC+
[중위]A+B+C -> [후위]AB+C+

괄호의 처리

중위C -> [후위]AB+C
여는 괄호는 스택에 push
닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop
[중위]A(B+C) -> [후위]ABC+
연산자를 만났을 때, 여는 괄호 너머까지 pop하지 않도록
여는 괄호의 우선순위는 가장 낮게 설정

예제1

중위(C+D) -> [후위]AB+CD+
[중위]A(B-(C+D)) -> [후위]ABCD+-

알고리즘의 설계

연산자의 우선순위 설정

prec = {
    '*':3, '/':3,
    '+':2, '-':2,
    '(':1
}

파이썬의 사전이다~

중위 표현식을 왼쪽부터 한 글짜씩 읽어서 
피연산자이면 그냥 출력
'('이면 스택에 push
')'이면 '('이 나올 때까지 스택에서 pop 출력
연산자이면 스택에서 이보다 높(거나 같)은 우선순위 것들을 pop, 출력
그리고 이 연산자는 스택에 push
스택에 남아 있는 연산자는 모두 pop해서 출력

코드의 구현 - 힌트

스택의 맨 위에 있는 연산자와의 우선순위 비교
스택의 peek() 연산 이용
스택에 남아 있는 연산자 모두 pop()하는 순환문
while not opStack.isEmpty():

13. 스택의 응용 - 후위 표기 수식 계산

후위 표기식의 계산

(A+B)(C+D) -> AB+CD+

A push
B push
A pop
B pop
A+B 수행
A+B push
C push
D push
D pop
C pop
C+D 수행
C+D push
C+D pop
A+B pop
(A+B)*(C+D) 수행
(A+B)*(C+D) push
(A+B)*(C+D) return

알고리즘의 설계

후위 표현식을 왼쪽부터 한 글자씩 읽어서
    피연산자이면 스택에 push
    연산자를 만나면 스택에서 pop -> (1), 또 pop -> (2)
        (2)연산 (1)을 계산, 이 결과를 스택에 push
수식의 끝에 도달하면 스택에서 pop -> 이것이 계산 결과

큐(Queues)

큐(Queue) : 자료(data element)를 보관할 수 있는 (선형) 구조
단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고
-> 인큐(enqueue)연산
꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있음
-> 디큐(dequeue)연산
선입선출(FIFO - First In First Out)특징을 가지는 선형 자료구조
ex)영화관 입장줄

큐의 동작

Q = Queue()
Q.enqueue(A)
Q.enqueue(B)
r1 = Q.dequeue()
r2 = Q.dequeue()

큐의 추상적 자료구조 구현

배열을 이용하여 구현
- 파이썬 리스트와 메서드들을 이용
연결리스트를 이용하여 구현
- 이전 강의에서 마련한 양방향 연결 리스트를 이용해 구현

연산의 정의
- size() : 현재 큐에 들어 있는 데이터 원소의 수를 구함
- isEmpty() : 현재 큐가 비어 있는지를 판단
- enqueue(x) : 데이터 원소 x를 큐에 추가
- dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거(또한, 반환)
- peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환(제거하지 않음)

배열로 구현한 큐의 연산 복잡도

연산	복잡도
size()	O(1)
isEmpty()	O(1)
enqueue()	O(1)
dequeue()	O(n)
peek()	O(1)

from pythonds.basic.queue import Queue

위를 이용해 파이썬에서 제공하는 큐 라이브러리를 쓸 수 있다.

15. 환형 큐(circular queues)

큐의 활용

자료를 생성한는 작업과 그 자료를 이용하는 작업이 비동기적으로(asynchronously)일어나는 경우
자료를 생성하는 작업이 여러 곳에서 일어나는 경우
자료를 이용하는 작업이 여러 곳에서 일어나는 경우
자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우
자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

환형 큐(circular queue)

정해진 개수의 저장 공간을 빙 돌려가며 이용

Q.enqueue(A)
Q.enqueue(B)
Q.enqueue(C)
r1 = Q.dequeue()
Q.enqueue(D)
r2 = Q.dequeue()

큐가 가득 차면?
->더이상 원소를 넣을 수 없음(큐 길이를 기억하고 있어야)

환형 큐의 추상적 자료구조 구현

연산의 정의
- size() : 현재 큐에 들어 있는 데이터 원소의 수를 구함
- isEmpty() : 현재 큐가 비어 있는지를 판단
- isFull() : 큐에 데이터 원소가 꽉 차 있는지를 판단
- enqueue(x) : 데이터 원소 x를 큐에 추가
- dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거(또한, 반환)
- peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환(제거하지 않음)

배열로 구현한 환형 큐

정해진 길이 n의 리스트를 확보해 두고
front와 rear를 적절히 계산하여 배열을 환형으로 재활용

16. 우선순위 큐

우선순위 큐(Priority Queue) : 큐가 FIFO(First In First Out) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식

Enqueue	Dequeue
6	2
7	3
3	6
2	7

우선순위 큐의 활용

운영체제의 CPU 스케줄러

우선순위 큐의 구현

서로 다른 두 가지 방식이 가능할 듯 :
1. Enqueue할 때 우선순위 순서를 유지하도록
2. Dequeue할 때 우선순위 높은 것을 선택 -> 어느 것이 더 유리할까?
서로 다른 두 가지 재료를 이용할 수 있음:
1. 선형 배열 이용
2. 연결 리스트 이용 -> 어느 것이 더 유리할까?

17. 트리(Tree)

트리 : 정점(node)와 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조
가장 최상단 노드가 루트 노드
가장 아래의 자식이 없는 노드가 leaf 노드
루트도 leaf도 아닌 노드는 internal node
부모노드와 자식 노드
부모의 부모(의 부모의…) - 조상(ancestor)
자식의 자식(의 자식의…) - 후손(descendant)
노드의 수준(Level)

root의 level은 0
한 노드씩 내려오며 level++ 부분트리(서브트리-Subtree)
노드의 차수(Degree) = 자식(서브트리)의 수

이진트리(Binary Tree)

모든 노드의 차수가 2 이하인 트리
재귀적으로 정의할 수 있음 : 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리(단, 이 때 왼쪽과 오른쪽 서브트리 또한 이진 트리)

포화 이진 트리(Full Binary Tree)

모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
(높이가 k이고 노드의 개수가 2^k-1인 이진 트리)

완전 이진 트리(Complete Binary Tree)

높이 k인 완전 이진 트리
레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리

18. 이진 트리(Binary Trees)

이진 트리의 추상적 자료구조

연산의 정의
- size() - 현재 트리에 포함되어 있는 노드의 수를 구함. 재귀적인 방법으로 쉽게 구할 수 있음.
  - 전체 이진 트리의 size() = left subtree의 size() + right subtree의 size() + 1(자기 자신)
- depth() - 현재 트리의 깊이(또는 높이; height)를 구함. 재귀적인 방법으로 쉽게 구할 수 있음!
  - 전체 이진 트리의 depth() = left subtree의 depth()와 right subtree의 depth()중 더 큰 것 + 1(루트개수~)
- 순회(traversal)

이진 트리의 순회(Traversal)

깊이 우선 순회(depth first traversal)
- 중위 순회(in-order traversal)
- 전위 순회(pre-order traversal)
- 후위 순회(post-order traversal)
넓이 우선 순회(breadth first traversal)

중위 순회(in-order traversal)

순회의 순서 :

Left subtree
자기 자신
Right subtree

전위 순회(pre-order traversal)

순회의 순서 :

자기 자신
Left subtree
Right subtree

후위 순회(post-order traversal)

순회의 순서 :

Left subtree
Right subtree
자기 자신

19. 이진 트리 - 넓이 우선 순회(breath first traversal)

넓이 우선 순회(Breath First Traversal)

원칙
- 수준(level)이 낮은 노드를 우선으로 방문
- 같은 수준의 노드들 사이에는,
  - 부모 노드의 방문 순서에 따라 방문
  - 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문
재귀적(recursive)방법이 적합한가?
한 노드를 방문했을 때,
- 나중에 방문할 노드들을 순서대로 기록해 두어야
- 큐(queue)를 이용하면 어떨까!

넓이 우선 순회 알고리즘 구현

(초기화)traversal <- 빈 리스트, q <- 빈 큐
빈 트리가 아니면, root node를 q에 추가(enqueue)
q가 비어 있지 않은 동안
- node <- q에서 원소를 추출(dequeue)
- node를 방문
- node의 왼쪽 오른쪽 자식(있으면)들을 q에 추가
q가 빈 큐가 되면 모든 노드 방문 완료

20. 이진 탐색 트리(Binary Search Trees)

이진 탐색 트리

모든 노드에 대해서,

왼쪽 서브 트리에 있는 데이터는 모두 현재 노드의 값보다 작고
오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진 트리(중복되는 데이터 원소는 없는 것으로 가정)

(정렬된) 배열을 이용한 이진 탐색과 비교

장점 : 데이터 원소의 추가, 삭제가 용이
단점 : 공간 소요가 큼
항상 O(log n)의 탐색 복잡도? -> 그렇진 않은 경우가 생길 수 있다!

이진 탐색 트리의 추상적 자료구조

데이터 표현 : 각 노드는 (key, value)의 쌍으로
키를 이용해서 검색 가능. 보다 복잡한 데이터 레코드로 확장 가능
연산의 정의
- insert(key, data) : 트리에 주어진 데이터 원소를 추가
- remove(key) : 특정 원소를 트리로부터 삭제
- lookup(key) : 특정 원소를 검색
- inorder() : 키의 순서대로 데이터 원소를 나열
- min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색. min은 왼쪽만 찾아가면 나오고, max는 그 반대의 경우로 완전히 대칭적이다.

코드 구현 - lookup()

입력 인자 : 찾으려는 대상 키
리턴 : 찾은 노드와, 그것의 부모 노드(각각, 없으면 None 으로)

코드 구현 - insert()

입력 인자 : 키, 데이터 원소
리턴 : 없음

21. 이진 탐색 트리(Binary Search Trees) (2)

이진 탐색 트리에서 원소 삭제

키(key)를 이용해서 노드를 찾는다.
- 해당 키의 노드가 없으면, 삭제할 것도 없음
- 찾은 노드의 부모 노드도 알고 있어야 함 (아래 2번 때문)
찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리한다.

인터페이스의 설계

입력 : 키(key)
출력 : 삭제한 경우 True, 해당 키의 노드가 없는 경우 False

이진 탐색 트리 구조의 유지

삭제되는 노드가

말단(leaf) 노드인 경우
- 그냥 그 노드를 없애면 됨. -> 부모 노드의 링크를 조정(좌/우 판단)
- 삭제되는 노드가 root node인 경우 : 트리가 사라짐
자식을 하나 가지고 있는 경우
- 삭제되는 노드 자리에 그 자식을 대신 배치 -> 자식이 왼쪽? 오른쪽?
  -> 부모 노드의 링크를 조정(좌/우 판단)
- 삭제되는 노드가 root node인 경우는 어떻게? -> 대신 들어오는 자식이 새로 root가 됨
자식을 둘 가지고 있는 경우
- 삭제되는 노드보다 바로 다음 (큰)키를 가지는 노드를 찾아 그 노드를 삭제되는 노드 자리에 대신 배치하고 이 노드를 대신 삭제

이진 탐색 트리가 별로 효율적이지 못한 경우

T= BinSearchTree()
T.insert(1, 'John')
T.insert(2, 'Mary')
T.insert(3, 'Anne')
T.insert(4, 'Peter')

T= BinSearchTree()
T.insert(4, 'John')
T.insert(3, 'Mary')
T.insert(2, 'Anne')
T.insert(1, 'Peter')

선형 탐색의 형태가 된다. 이진 탐색 트리의 제 기능을 발휘하지 못한다.

보다 나은 성능을 보이는 이진 탐색 트리들

높이의 균형을 유지함으로써 O(log n)의 탐색 복잡도 보장
삽입, 삭제 연산이 보다 복잡

22. 힙(Heaps)

힙(Heap) 이란?

이진 트리의 한 종류(이진 힙 - binary heap)
1. 루트(root) 노드가 언제나 최댓값 또는 최솟값을 가짐
최대 힙(max heap) : 재귀적으로도 정의됨(어느 노드를 루트로 하는 서브트리도 모두 최대 힙. 서브트리의 숫자 크기 순서는 상관없음. 느슨하게 정렬되어있음.)
최소 힙(min heap)

완전 이진 트리여야 함

이진 탐색 트리와의 비교

원소들은 완전히 크기 순으로 정렬되어 있는가?
- 이진 탐색 트리는 그렇다.
- 최소, 최대 힙은 느슨하게 정렬되어 있다.
특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가?
- 이진 탐색 트리는 키값을 가지고 빠르게 검색 가능
- 힙에서는 특정 키 값 검색하는 좋은 방법이 없다.
부가의 제약 조건은 어떤 것인가?
- 힙은 이진 탐색 트리와 달리 완전 이진 트리여야 한다는 제약 조건을 갖고 있다.

최대 힙(Max Heap)의 추상적 자료구조

연산의 정의

init() : 빈 최대 힙을 생성
insert(item) : 새로운 원소를 삽입
remove() : 최대 원소(root node)를 반환. 그리고 동시에 이 노드를 삭제. 이진 탐색 트리와 다르게 traverse, search 연산을 제공하지 않음.

데이터 표현의 설계

배열을 이용한 이진 트리의 표현
노드 번호 m을 기준으로

왼쪽 자식의 번호 : 2*m
오른쪽 자식의 번호 : 2*m+1
부모 노드의 번호 : m//2 완전 이진 트리이므로 노드의 추가/삭제는 마지막 노드에서만

최대 힙에 원소 삽입

트리의 마지막 자리에 새로운 원소를 임시로 저장
부모 노드와 키 값을 비교하여 위로, 위로, 이동

최대 힙에 원소 삽입 - 복잡도

원소의 개수가 n인 최대 힙에 새로운 원소 삽입
-> 부모 노드와의 대소 비교 최대 회수 : log_2n
최악 복잡도 O(log n)의 삽입 연산

삽입 연산의 구현 - insert(item) 메서드

힌트 : 파이썬에서 두 변수의 값 바꾸기

a = 3; b=5
a,b=b,a

23. 힙(Heaps) (2)

최대 힙에서 원소의 삭제

루트 노드의 제거 - 이것이 원소들 중 최댓값
트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
자식 노드들과의 값 비교와 아래로, 아래로 이동
- 자식은 둘 있을 수도 있는데, 어느 쪽으로 이동?
- 자식이 둘 있으면 더 큰 값 쪽으로

최대 힙으로부터 원소 삭제 - 복잡도

원소의 개수가 n인 최대 힙에서 최대 원소 삭제
-> 자식 노드들과의 대소 비교 최대 회수 : 2 * log_2n
최악 복잡도 O(log n)의 삭제 연산

최대/최소 힙의 응용

우선 순위 큐(priority queue)
- Enqueue할 때 “느슨한 정렬”을 이루고 있도록 함 : O(log n)
- Dequeue할 때 최댓값을 순서대로 추출 : O(log n)
- 제 16강에서의 양방향 연결 리스트 이용 구현과 효율성 비교. 우선순위 큐가 더 효율성이 좋다.
힙 정렬(heap sort)
- 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 : O(log n)
- 삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제 : O(log n)
- 원소들이 삭제된 순서가 원소들의 정렬 순서
- 정렬 알고리즘의 복잡도 : O(nlogn)

Twitter Facebook LinkedIn

채린

12. 스택의 응용 - 수식의 후위 표기법(Postfix Notation)

중위 표기법과 후위 표기법

중위 표현식 -> 후위 표현식

괄호의 처리

예제1

알고리즘의 설계

코드의 구현 - 힌트

13. 스택의 응용 - 후위 표기 수식 계산

후위 표기식의 계산

알고리즘의 설계

큐(Queues)

큐의 동작

큐의 추상적 자료구조 구현

배열로 구현한 큐의 연산 복잡도

15. 환형 큐(circular queues)

큐의 활용

환형 큐(circular queue)

환형 큐의 추상적 자료구조 구현

배열로 구현한 환형 큐

16. 우선순위 큐

우선순위 큐의 활용

우선순위 큐의 구현

17. 트리(Tree)

이진트리(Binary Tree)

포화 이진 트리(Full Binary Tree)

완전 이진 트리(Complete Binary Tree)

18. 이진 트리(Binary Trees)

이진 트리의 추상적 자료구조

이진 트리의 순회(Traversal)

중위 순회(in-order traversal)

전위 순회(pre-order traversal)

후위 순회(post-order traversal)

19. 이진 트리 - 넓이 우선 순회(breath first traversal)

넓이 우선 순회(Breath First Traversal)

넓이 우선 순회 알고리즘 구현

20. 이진 탐색 트리(Binary Search Trees)

이진 탐색 트리

(정렬된) 배열을 이용한 이진 탐색과 비교

이진 탐색 트리의 추상적 자료구조

코드 구현 - lookup()

코드 구현 - insert()

21. 이진 탐색 트리(Binary Search Trees) (2)

이진 탐색 트리에서 원소 삭제

인터페이스의 설계

이진 탐색 트리 구조의 유지

이진 탐색 트리가 별로 효율적이지 못한 경우

보다 나은 성능을 보이는 이진 탐색 트리들

22. 힙(Heaps)

힙(Heap) 이란?

이진 탐색 트리와의 비교

최대 힙(Max Heap)의 추상적 자료구조

데이터 표현의 설계

최대 힙에 원소 삽입

최대 힙에 원소 삽입 - 복잡도

삽입 연산의 구현 - insert(item) 메서드

23. 힙(Heaps) (2)

최대 힙에서 원소의 삭제

최대 힙으로부터 원소 삭제 - 복잡도

최대/최소 힙의 응용

You May Also Enjoy

[프로그래머스]MySQL 문제

MySQL 정리

[프로그래머스 코딩테스트]Level03 - 네트워크

[Leetcode]85 - Maximul Rectangle