LinkedList

 

0x01. insertAt ( LinkedList ) vs insertAt ( Dummy LinkedList )

insertAt ( LinkedList )

• 1에 추가할때 그놈을 헤드로..
• 나머지인덱스는 prev노드를 먼저 찾고,
  • <newNode가 prev노드 next를 가리키게>하고, <prev노드 next는 newNode를 가리키게>
• (+추가) 맨끝+1 인덱스에 노드집어넣을경우 그 노드를 tail로 조정

insertAt ( Dummy LinkedList )

• 그냥 prev노드 찾아서 insertAfter을 호출

insertAfter ( Dummy LinkedList )

• <newNode가 prev노드 next를 가리키게>하고, <prev노드 next는 newNode를 가리키게>

   

0x02. popAt ( LinkedList ) vs popAt ( Dummy LinkedList )

popAt ( LinkedList )

• 1을 꺼낼때 현재헤드의 next를(None을) 새롭게 head로..

  • 단, 데이터가 0개가 되므로 tail도 None으로 조정

• 나머지 인덱스 꺼낼때는 prev찾고, prev의 next가 curr.next를 가리키도록!

  • 단, 맨 마지막놈을 꺼낼땐 tail도 하나 전껄로 변경

popAt ( Dummy LinkedList )

• 그냥 prev찾아서 popAfter 호출

popAfter ( Dummy LInkedList )

• prev의 next가 curr.next를 가리키도록!
  • 단, prev의 next가 None이면(끝놈을 삭제했을 경우), tail을 prev로 조정

---

Stack

연산자 우선순위가 높다: 상대적으로 스택 꼭대기 근방에 있다.

<기본>

infix -> postfix

1. 문자는 그냥 후위표현식에 적는다.
2. 첫번째 연산자는 스택에 넣는다.
3. 그다음 연산자 만나면 스택꼭대기에 있는 놈과 우선순위 비교 후
   • 스택에 있는 연산자가 더 높으면 pop해서 계산한다.
   • 아니면 스택에 push한다.

• [중위] A * B + C
• [후위] A B * C +

• [중위] A + B * C
• [후위] A B C * +

• [중위] A + B + C
• [후위] A B + C +

<괄호의 처리>

괄호는 스택 내 구분선이다

1. ( 는 스택에 push
   • ∵ ( 가 들어가기 전에는 우선순위가 가장 높으므로 무조건 push

단, ( 가 들어가는 순간 우선순위가 가장 낮음

2. ) 를 만나면 ( 가 나올 때까지 pop

• [중위] (A + B) * C
• [후위] A B + C *

• [중위] A * (B + C)
• [후위] A B C + *

• [중위] (A + B) * (C + D)
• [후위] A B + C D + *

• [중위] A * (B + C)
• [후위] A B C + *

• [중위] (A + (B - C)) * D
• [후위] A B C - + D *

• [중위] A * (B - (C + D))
• [후위] A B C D + - *

---

이진탐색트리(Binary Search Tree)

0x01. 이진탐색트리(Binary Search Tree)의 정의

• 모든 Node에 대해서,
  • left subtree에 있는 모든 데이터는 현재 node보다 작음.
  • right subtree에 있는 모든 데이터는 현재 node보다 큼.
• 이러한 특징으로 인해 데이터 검색이 수월
  • 이진탐색과 비슷하게 찾을 수 있으므로..
• 장점: data 추가 / 삭제 용이
• 단점: 공간 소모가 큼

0x02. 이진탐색트리(Binary Search Tree)의 ADT

• 데이터: 각 노드는 (key, value) 쌍으로

  • key를 이용해 value검색
    • 그냥 숫자만하기에는 심심하니까..ㅋ

• 연산

  • insert(key, data) : 트리에 주어진 데이터 원소를 추가
  • inorder() : 키의 순서대로 데이터 원소를 나열
  • lookup(key) : 특정 원소를 검색
  • remove(key) : 특정 원소를 트리로부터 삭제
  • min() , max() : 최소 key, 최대 key를 가지는 원소를 각각 탐색

• remove(key) : 특정 원소를 트리로부터 삭제

  1. key를 이용해서 Node와 그 Node의 parent를 찾는다. => lookup(key)
  • parent도 찾는이유: 찾은 Node를 제거하고도 BST의 성질을 만족시켜야 하기 때문
  2. 삭제하려는 Node가 어떤 자식인지에따라 다음과 같이 분류
  3. 자식이 0인 경우: - 그냥 그 노드 없앰 <= 부모노드 링크조정(좌? 우?)
  4. 자식이 1인 경우: - 삭제되는 노드자리에 그 child를 대신 배치 <= 자식이 왼쪽?오른쪽?, 부모노드 링크조정(좌? 우?)
  5. 자식이 2인 경우: - 삭제되는 노드보다 바로 다음 큰 key를 가지는 노드를 찾아 그 노드를 삭제되는 노드자리에 대신 배치 후 이 노드를 대신 삭제

---

힙(Heap) 이란?

0x01. 힙(Heap)의 정의

• 이진 트리의 한 종류 (이진 힙 - binary heap)
  • 루트 (root) 노드가 언제나 최댓값 or 최솟값을 가짐
    • 최대 힙 (max heap), 최소 힙 (min heap)
    • ex) 최대 힙 : 부모는 무조건 자식보다 큼
    • ex) 최소 힙 : 부모는 무조건 자식보다 작음
  • But, left subtree와 right subtree는 부모보다 작다는 것 외에는 관계 X
    • 따라서 이진 탐색 트리보다는 느슨한 정렬(탐색, 순회에 적합하지 X)
• 완전 이진 트리여야 함

완전 이진 트리: 왼쪽부터 오른쪽으로 채워져 있는 트리

이진 탐색 트리: left subtree < 자기자신 < right subtree 이진 탐색 트리와의 비교

1. 원소들은 완전히 크기 순으로 정렬되어 있는가? => 이진 탐색트리 O / 힙 X
2. 특정 키 값을 가지는 원소를 빠르게 찾을 수 있는가? => 이진 탐색트리 O / 힙 X
3. 부가적인 제약조건이 무엇인가? => 힙: 완전 이진 트리 이어야함.

0x02. 최대 힙의 ADT

• __init__() : 빈 최대 힙을 생성
• insert(item) : 새로운 원소를 삽입
• remove() : 이 노드를 삭제함과 동시에 최대 원소 (root node)를 반환
  • traverse, search 는 제공 X

0x03. 데이터 표현의 설계

3.1 배열을 이용한 이진 트리의 표현

• 지금껏 이진 트리는 한 노드당 left, right를 가지는 것으로 정의되었으나, 배열을 이용하면 효율적
• 배열의 인덱스가 main!
  • (1 / 2 3 / 4 5 6 7 / 8 9 10 11 12 13 14 15 / 16 17 ⋯⋯)
  • 왼쪽 자식 노드의 인덱스 값: 부모 노드의 인덱스 값 * 2
  • 오른쪽 자식 노드의 인덱스 값: 부모 노드의 인덱스 값 * 2 + 1
  • 부모 노드의 인덱스 값: 자식 노드의 인덱스 값 // 2
• 완전 이진 트리의 한 갈래이므로
  • 노드의 추가 및 삭제는 마지막 노드에서만

3.2 최대 힙에 원소 삽입

1. 트리의 마지막 자리에 새로운 원소를 일단 임시로 저장(완전 이진 트리의 성질을 만족하기 위해)
2. 부모 노드의 키 값과 비교하며 크다면 계속 위로, 위로 이동

원소의 크기는 임의값

3.3 최대 힙에 최대 원소 삭제

1. 원소들 중 최댓값인 루트 노드의 제거
2. 트리 마지막 자리 노드를 일단 임시로 루트 노드의 자리에 배치
3. 자식 노드들의 키 값과 비교하여 아래로, 아래로 이동

• 자식은 둘 있을 수도 있는데, 어느 쪽으로 이동? => 더 큰 자식과 교체

최대 힙에 원소 삽입과는 다르게, 삭제에서는 특정 원소를 삭제하는 연산은 없고, 최대 원소를 삭제하는 연산만이 존재한다.
복잡도: 원소의 개수가 n인 최대힙에서 최대원소 삭제 => 자식노드들과의 대소비교 최대횟수 $2 * log_2n$ , 즉, $O(logn)$

분리집합

서로 공통된 원소를 갖지 않는 집합들

• 트리는 부모가 자식을 가리키나, 분리집합은 자식이 부모를 가리킨다.
  • 그래서, root는 부모가 없으므로 parent가 None임.
• root는 집합 그 자체를 대표한다.

분리집합의 연산: Union, Find

1. Union(합집합)

• 분리집합을 합한다.
• 오른쪽 분리집합의 루트노드를 왼쪽 분리집합의 루트노드의 자식으로 만들면 됨.
  • ex) {1}←{{2},{3},{4}}이라는 분리집합과, {5}←{{6},{7}}라는 분리집합이 있을 때, Union연산을 하면 {1}←{ {2},{3},{4}, {{5}←{6},{7}} } 이 됨.

2. Find(집합탐색)

• 원소가 속해있는 집합을 찾음.
  • 집합에서 원소를 찾는 것이 아님!!
• 즉, 특정 원소가 어떤집합에 속해있는지 알려면, 이 원소가 속해있는 트리의 root를 찾으면 됨.