[AI class day 2] 파이썬 자료구조와 알고리즘 TIL

* 첫째날과 이어서 자료구조를 공부하고 있다.

선형 자료구조인 연결리스트, 스택, 큐

이차원 자료구조인 트리

의 개념에 대해 정리하고, 구현하는 실습을 했다.

OOP에 자신이 없어서 한참을 헤매고 있다.

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

• 중위 표기법 (infix notation) : 우리가 일상에서 사용하는 수식 표기법 연산자를 가운데에 ex. A+B
• 후위 표기법 : 연산자를 뒤에 ex.AB+

--> 후위 표기법을 이용하면 괄호를 쓰지 않고 연산의 우선순위 표현이 가능함

ABC*+

--> B*C를 먼저하고 그다음에 +A 하라는 뜻 = A+(B*C)

1) 중위 표기법으로 쓰인 수식을 후위 표기법으로 변환

2) 후위 표기법으로 쓰인 수식 계산

--> 각각 스택을 활용

1)의 알고리즘 설계하기

• 연산자의 우선순위 설정
• 중위 표현식을 왼쪽부터 하나씩 읽으면서
  • 피연산자면 그냥 출력
  • 여는 괄호면 스택에 push
  • 닫는 괄호면 여는 괄호가 나올때까지 pop &출력
  • 연산자를 만나면 스택에서 이보다 높거나 같은 우선순위의 것들을 pop&출력, 이 연산자는 스택에 push
• 수식의 끝에 닿으면 남아있는 연산자는 모두 pop&출력

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

이번에는 후위 표기 식을 계산하는 알고리즘을 스택을 활용해 만들기

알고리즘 설계

수식을 왼쪽부터 시작해서 오른쪽으로 차례대로 읽어들이면서

• 피연산자면 스택에 push
• 연산자가 나타나면, 스택에 들어 있는 피연산자 2개를 pop -> 연산을 적용 -> 연산 괄과를 스택에 push
• 수식의 끝이면, 스택 안에는 하나의 item 만 있고 이를 pop하면 계산 결과 return

* 뺄셈 나눗셈은 순서가 중요하기 때문에 주의! -> 나중에 pop한 피연산자가 수식의 앞에 와야 된다

*실제 숫자로된 수식을 계산할 수 있어야 하므로 스트링으로 된 식을 숫자와 연산자로 분리하여 리스트로 만드는 과정을 거친다.

14. 큐 (Queues)

• 선형 배열, 연결리스트, 스택과 같은 선형 구조
• 스택과는 반대인 특성 : 선입선출 FIFO(first in first out)

1) 인큐 연산 enqueue : 데이터 원소를 큐에 넣기

2) 디큐 연산 dequeue : 데이터 연소를 큐에서 꺼내기

큐의 동작

• #1: 초기상태 : 비어있는 큐(empty queue) Q = Queue()
• #2: 데이터 원소 A, B를 큐에 추가 Q.enqueue(A) / Q.enqueue(B)
• #3: 데이터 원소 꺼내기 r1 = Q.dequeue( ) --> r1 == A / r2 = Q.dequeue() --> r2 == B

큐의 추상적 자료구조 구현

• 배열 array : 파이썬의 리스트와 메서드 이용
• 연결리스트 linked list : 양방향 연결 리스트 이용
• 연산의 정의
  • size(): 현재 스택에 들어있는 데이터 원소의 수를 구함
  • isEmpty(): 현재 스택이 비어있는지를 판단
  • enqueue(x): 데이터 원소 x를 스택에 추가 (stack의 push()에 대응)
  • dequeue(): 스택의 맨 앞에 저장된 데이터 원소를 제거& 반환) (stack의 pop()에 대응) (stack과 반대)
  • peek(): 스택의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음)(stack과 반대)
• 스택처럼 선형 배열을 이용할 수도 연결 리스트를 이용할 수도 있음
• 선형 배열을 이용하면 디큐 연산이 큐의 길이에 비례하는 만큼의 시간 걸림 (배열에 저장된 데이터 원소들을 하나하나 앞 칸으로 당겨서 위치를 조정해야 하기 때문)
• 연산의 시간 복잡도 측면에서는 연결 리스트로 큐를 구현하는 것이 유리

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

• size() :O(1)
• isEmpty() :O(1)
• enqueue() :O(1)
• dequeue() :O(n)
  • 큐의 길이에 비례하는 복잡도
  • 배열에 저장된 데이터 원소들을 하나하나 앞 칸으로 당겨서 위치를 조정해야 하기 때문
  • 연산의 시간 복잡도 측면에서는 연결 리스트로 큐를 구현하는 것이 유리함
• peek() :O(1)

라이브러리도 있음

from pythonds.basic.queue import Queue

from pythonds.basic.queue import Queue 

15. 환형 큐 (Circular Queues)

큐(Queue)의 활용

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

환형 큐란?

• 정해진 개수의 저장 공간을 빙 돌려가며 이용
• 큐에 담을 수 있는 데이터의 양(데이터 원소의 개수)이 무한할 수는 없다.
• 만약 큐에 담을 수 있는 원소의 개수 상한을 미리 정하고, 이를 지킬 수 있다면선형 배열을 이용해서 큐를 효과적으로 구현할 수 있다.
• enqueue에서 큐의 길이에 따라 복잡도가 증가하기 때문에 이 문제를 해결하기 위해 환형 큐를 이용함
• 선형 배열의 한쪽 끝과 다른 쪽 끝이 서로 맞닿아 있는 모습(원형, 환형)으로 생각하고, 큐의 맨 앞과 맨 뒤를 가리키는 즉, 원소를 넣을 쪽의 배열 인덱스와 꺼낼 쪽의 배열 인덱스를 기억해 두면 데이터 원소가 빠져 나간 쪽의 저장소를 재활용하면서 큐를 관리할 수 있다.

큐의 동작

• #1 : Q.enqueue(A)
• #2 : Q.enqueue(B)
• #3 : Q.enqueue(C)
• #4: r1= Q.dequeue() --> r1 = A
• #5 : Q.enqueue(D)
• #6: r2=Q.dequeue() --> r2 = B
• ...
• 데이터가 들어가는 쪽 : rear
• 데이터가 빠지는 쪽 : front

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

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

• 연산의 정의:isFull()을 제외하고는 queue와 동일
  • size()
  • isEmpty()
  • isFull(): 큐에 데이터 원소가 꽉 차 있는지를 판단
  • enqueue(x)
  • dequeue()
  • peek()
• 배열로 구현한 환형 큐
  • 정해진 길이 n의 리스트를 확보
  • Q.enqueue(A) ->rear가 A를 가리킴
  • Q.enqueue(B) - >rear가 B를 가리킴
  • Q.enqueue(C) - >rear가 C를 가리킴
  • Q.enqueue(D) - >rear가 D를 가리킴
  • r1 = Q.dequeue() ->front는 A를 가리키게 하고 dequeue
  • r2 = Q.dequeue() ->front는 B를 가리키게 하고 dequeue
  • 최대 길이에 도달하면 그 다음은 +1이 아니라 0이 됨 dequeue된 A 자리에 새 원소가 들어감

16. 우선순위 큐 (Priority Queues)

원소를 꺼낼 때 FIFO가 아니라 우선순위를 정해서 따르는 것

ex> 작은 수부터 순서대로 dequeue하기

구현 방법

1. 큐에서 원소를 넣을 때 우선순위가 순서대로 정렬해 두는 방법
2. 큐에서 원소를 꺼낼 때 우선순위가 가장 높은 것을 선택하는 방법

--> 1번이 더 유리하다 (2번은 찾을 때 마다 원소를 다 살펴봐야 한다)

1. 선형 배열 이용
2. 연결 리스트 이용

--> 시간적으로 2번이 더 유리 (enqueue할 때 중간에 삽입할 때 유리하기 때문) 메모리 공간적으로는 1번이 더 유리

1번 방법을 양방향 연결 리스트로 구현하면,

1. 양방향 연결 리스트를 이용하여,
2. enqueue 할 때 우선순위에 따라 정렬하고,
3. 꺼낼 때 한쪽 끝에서 꺼내기

--> enqueue의 연산 복잡도는 O(n) dequeue의 연산 복잡도는 O(1)이 됨

17. 트리(Trees)

스택, 큐는 1차원 선형 자료구조라면 트리는 2차원, 일렬로 늘어서 있지 않다

트리(Tree)란?

• 순환하는 길이 없는 그래프(graph)
• 정점(node)에서 간선(edge)들이 마치 나무에서 뿌리로부터 잔가지로 뻗어나가듯이 가지치기 된 구조

용어설명

• 노드 (nodes)
  • 종류 :부모(parent)노드, 자식(child) 노드
  • 부모부터 그 위로는 조상(ancestor)
  • 자식부터 그 아래로는 후손(descendant)
• 간선 (edges) : 노드 사이를 연결하는 선
• 루트 노드 (root node): 맨 위
• 리프 노드 (leaf node): 맨 아래
• 내부 노드 (internal node): 루트와 리프 사이
• 노드의 수준 (level)
  • 루트 노드는 level 0 --> 아래로 내려가며 +1 씩
  • 노드에 도착하기 위해서 지나치는 간선의 수
• 트리의 높이 (height) 또는 깊이 (depth) : 최대 레벨 + 1
• 부분 트리 (서브트리, subtree) : 트리에서 어느 한 노드를 기준으로 잘라낸 부분
• 노드의 차수(degree) : 서브 트리의 수 (리프 노드는 degree = 0)
• 이진 트리 (binary tree)
  • 모든 노드의 차수가 2 이하인 트리
  • 재귀적으로 정의할 수 있음
  • 빈 트리이거나, 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리
    • 단, 이 때 왼쪽과 오른쪽 서브트리 또한 각각 이진 트리
• 포화 이진 트리 (full binary tree)
  • 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
  • 높이가 k이고 노드의 개수가 2^k - 1
• 완전 이진 트리 (complete binary tree)
  • 높이 k인 완전 이진 트리는
  • 레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리이고
  • 레벨 k-1 (마지막 레벨) 에서는 노드가 순차적으로 채워져 있음

18. 이진 트리 (Binary Trees)

이진 트리(Binary Tree)란?

• 모든 노드의 차수가 2 이하인 트리
• 즉, 모든 노드는자식이 없거나(리프 노드의 경우),하나만 있거나, 아니면둘 있는세 경우 중 하나에 해당
• 트리는 정의 자체가 재귀적이기 때문에, 이를 대상으로 하는 연산들도 대부분 재귀적으로 구현이 가능하다
  • size() - 현재 트리에 포함되어 있는 노드의 수를 구함
  • depth() - 현재 트리의 깊이 (또는 높이)를 구함
  • 순회 연산 (traversal, search) : 트리의 각 노드를 정해진 순서로 방문하는 것

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

• node 정의
  • data
  • left child
  • right child
• 연산의 정의
  • size() :
    • 재귀적 방법으로 구현
    • 전체 이진 트리 size() = left subtree size + right subtree size + 1 (자기 자신)
  • depth()
    • 재귀적 방법으로 구현
    • 전체 이진 트리 depth() : left subtree depth / right subtree depth 중 더 큰것 + 1
  • 순회(traversal, search)
    • 깊이 우선 순회(Depth First Search, DFS)
      • 중위 순회 (In-order Traversal)
        • left subtree -> 기준 -> right subtree
      • 전위 순회 (Pre-order Traversal)
        • 기준 -> left subtree -> right subtree
      • 후위 순회 (Post-order Traversal)
        • left subtree-> right subtree -> 기준
  • 넓이 우선 순회(Breadth First Search)

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

넓이 우선 순회

• node의 level에 따라 순서를 정해서 순회하는 방식
• level이 낮은 노드 우선 -> 같은 level일 때는 부모 노드가 먼저 방문된 순서부터 / 왼쪽부터
• 재귀적 방법 x -> queue 활용
• 노드의 자식 노드를 방문하는 것이 아니라 같은 수준의 다른 노드를 방문하고 자식 노드는 나중에 방문하도록 기록해 두어야 때문

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

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

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

이진 탐색 트리란?

 

• 모든 노드에서 left sub tree data는 현재 노드의 값보다 작고 right sub tree data는 큰 이진 트리 (중복되는 데이터 없다고 가정)
• 검색의 용이성이 뛰어남
• 탐색 순서: root node에서 시작해서 한 번에 한 단계씩 edge를 따라 아래로 내려가
• 찾고자 하는 키가 어떤 node에서 그 노드의 데이터보다 작으면 left sub tree, 크면 right sub tree 선택
• leaf node까지 찾지 못하면, 이 이진 탐색 트리에는 그 값이 없는 것임
• 재귀적임

 

* array binary search와 비교하면 데이터 추가, 삭제가 용이하다 (array는 다 밀고 그래야 되니까) but 공간 소요 큼

 

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

 

• - 데이터 표현
• - 각 노드는 (Key, Value)
  - Key를 이용해서 검색 가능, 보다 복잡한 데이터 레코드로 확장 가능\
•  

 

- 연산의 정의

 

• - insert(key, data) : 트리에 주어진 데이터 원소를 추가
  - remove(key) : 특정 원소를 트리로부터 삭제 (복잡한 편)
  - lookup(key): 특정 원소를 검색*중요 (입력인자: 찾으려는 키 리턴 : 찾은 노드와 그것의 부모 노드(원소 삭제 때문에 필요))
  - inorder() : 키의 순서대로 데이터 원소를 나열
  - min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색

 

 

remove() 연산

• 연산을 구현할 때 트리를 조정함에 있어서 이진 탐색 트리의 모습을 유지하도록 알고리즘을 구성해야 한다.
  
  

1. 키(key)를 이용해서 노드를 찾는다.
   • 해당 키의 노드가 없으면, 삭제할 것도 없다
   • 찾은 노드의 부모 노드도 알고 있어야 한다(2번 때문)
2. 찾은 노드를 제거하고도 이진 탐색 트리의 성질을 만족하도록 트리의 구조를 정리한다.
   • 삭제되는 노드가말단 (leaf) 노드인 경우
     • 그냥 그 노드를 없애면 됨
     • 부모 노드의 링크를 조정(삭제 되는 노드가 부모노드의 좌 / 우 인지 알아야)
     • 삭제되는 노드가 root node인 경우?
       • 말단 노드가 루트 노드인 경우는 루트 노드가 하나인 트리, 이 때는 트리 전체가 없어진다
   • 자식을 하나 가지고 있는 경우
     • 삭제되는 노드 자리에 그 자식을 대신 배치
     • 자식이 왼쪽 / 오른쪽 subtree
     • 부모 노드의 링크를 조정(삭제되는 노드가 부모 노드의 좌 / 우 인지 알아야)
     • 삭제되는 노드가 root node인 경우?
       • 대신 들어오는 자식이 새로 root가 된다
   • 자식을 둘 가지고 있는 경우
     • 삭제되는 노드보다 바로 다음 (큰) 키를 가지는 노드를 찾아 그 노드를 삭제되는 노드 자리에 대신 배치하고 이 노드를 대신 삭제

* 트리가 한 줄로 늘어서 있으면 이진 탐색 트리의 의미가 없다 (그냥 선형 탐색과 연산의 복잡도가 동일)

--> 높이의 균형을 유지하면 O(logn)의 탐색 복잡도를 보장할 수 있다

but, 삽입, 삭제 연산이 보다 복잡하다 (참고 AVL trees, Red-Black trees)

22~23. 힙(Heaps)

힙이란?

• 이진트리의 한 종류
• 이진 힙 binary heap 이라고도 함
• 데이터 원소들의 순서를 교묘하게 표현한 트리
• 데이터 정렬에도 이용 가능 --> 힙 정렬(heap sort)

힙의 종류

• 최대 힙
  • 3가지 성질을 유지하는 이진 트리
    1. 루트 노드는 항상 최댓값
    2. 완전 이진 트리
    3. 최대 힙 내의 임의의 노드를 루트로 하는 서브 트리도 최대 힙 (재귀적임)
•  최소 힙
  • 최대 힙의 대칭
    1. 루트 노드는 항상 최소값
    2. 완전 이진 트리
    3. 최소 힙 내 임의의 노드를 루트로 하는 서브 트리도 최소 힙 (재귀적)

--> 최대힙과 최소힙은 데이터 원소의 기준이 내림차순이냐 올림차순이냐만 다르고 완전히 대칭

 

이진 탐색 트리 binary search tree 와 다른점 

• 이진 탐색 트리에서는 원소들이 완전히 크기 순서대로 정렬되어 있다
  • 중위 순회를 하면 데이터를 정렬된 순서로 뽑아낼 수 있다
  • 루트 노드로부터 시작하여 특정 원소를 빠르게 검색할 수 있다
• 최대 힙은 완전히 크기 순서는 아님
  • 느슨한 정렬로 되어있는 구조
  • 트리를 순회함으로써 데이터 정렬할 수는 없다
  • 탐색 연산을 제공할 수 없다

최대 힙의 장점

• n개의 노드로 이루어진 최대 힙의 높이 = logn + 1 로 정해져있다 : 완전 이진 트리 complete binary tree 여야 한다는 조건 때문
  • 데이터 원소의 삽입/ 삭제 연산의 실행시간이 logn 비례
  • 어떤 최대 힙에서 반복적으로 루트 노드를 삭제하면서 데이터 원소를 꺼내면 루트 노드에 들어있는 키가 힙 내에서 최대임이 보장되어 있다
    --> 데이터를 내림차순으로 정렬할 수 있다 / 소요 시간 logn에 비례
  •  트리의 표현에도 이점이 있다
    •  규칙에 따라 노드에 번호를 매기면, 번호 순서대로 이루어진 선형배열에 트리 표현 가능
    •  노드의 추가 / 삭제는 배열의 맨 마지막 원소에서만 일어남

 

최대 힙의 추상적 자료 구조

데이터 표현 설계

• 배열을 통해 표현
• 노드 번호 m을 기준으로
  • left child : 2_m
  • right child : 2_m + 1
  • parent node : m // 2
• complete binary tree 이므로 추가/ 삭제는 마지막 노드에서만 가능

연산의 정의

- init() : 빈 최대 힙 생성
- insert(item) : 새로운 원소를 삽입
- remove() : 최대 원소(root node)를 반환 (그리고 동시에 이 노드를 삭제)

 

 

insert() 연산

• 트리의 마지막 자리에 새로운 원소를 임시로 저장
• 부모 노드와 키 값을 비교 --> 위로 이동 (부모와 값을 바꾸는 식으로)
• 복잡도
  - 원소 갯수가 n개인 최대 힙에서 insert -> 부모 노드외 비교의 최대 횟수 : log₂n
  - 최악 복잡도 O(logn)의 삽입 연산

 

remove() 연산 (최대 원소를 반환)

• 항상 루트 노드에서 제거함
  • 최댓값을 순서대로 뽑아내기 때문
• 루트 노드를 삭제하고 나면 트리 구조를 다시 정리해야 함
• 완전 이진 트리의 성질을 만족해야 하므로 노드의 삭제는 맨 마지막 노드에서 일어남
  • 루트 노드의 데이터를 꺼내고
  • 맨 마지막 노드의 원소를 루트 노드 자리에 임시로 넣은 다음
  • 마지막 노드를 제거하고
  • 루트 자리에 임시로 들어간 노드의 새로운 자리를 찾아 넣어 줘야 함 
• insert()와 반대로 임시로 들어간 노트는 루트 노드에서 시작해서 아래로 내려감
  • 자식들 중 더 큰 값을 가지는 노드와 자리를 바꾸면서, 더이상 바꿀 필요가 없거나 리프 노드에 도달할 때까지 이 과정을 반복
  • 더 큰 키값을 가지는 노드를 찾을 때 구분해서 생각해야
    1. child 2개
    2. child 1개
    3. child 0개
• 복잡도
  • 자식 노드들과의 비교 최대 횟수
  • 최악복잡도 Ologn의 삭제 연산

 

최대/ 최소 힙의 응용

1. 최대 힙을 이용한 효과적인 우선 순위 큐(priority queue) 구현

• Enqueue 할 때 느슨한 정렬을 이루고 있도록 하고: O(logn)
• dequeue 할 때 최댓값을 순서대로 꺼낼 수 있으며: O(logn)
• 양방향 연결리스트와 효율성을 비교해보라

 

2. 힙 정렬(heap sort)

• 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 : O(logn)
• 삽입이 끝나면, 힙이 비게 될 때 까지 하나씩 삭제 : O(logn)
• 원소들이 삭제된 순서가 원소들의 정렬 순서
• 정렬 알고리즘의 복잡도: O(nlogn)