큐

스택과 달리 온 순서대로 나가는 자료구조이다. 첫 번째로 온 데이터가 첫 번째로 나간다고 해서 First In First Out(FIFO) 자료구조라고 부르기도 한다. 놀이기구 줄을 생각하면 된다.

class Node:
    def __init__(self, val, next):
        self.val = val
        self.next = next

class Queue:
    def __init__(self):
        self.front = None

    def push(self, val):
        if not self.front:
            self.front = Node(val, None)
            return
        node = self.front
        while node.next:
            node = node.next
        node.next = Node(val, None)

    def pop(self):
        if not self.front:
            return None
        node = self.front
        self.front = node.next
        return node.val
    def is_empty(self):
        return self.front is None

que = [1, 2, 3, 3, 5]
q1 = Queue()

for i in que:
    q1.push(i)

while not q1.is_empty():
    print(q1.pop())

삽입 함수는 inqueue, 삭제 함수는 dequeue라고도 한다.

큐 응용 - 카드2

https://www.acmicpc.net/problem/2164
첫 번째 시도 : 구현했던 큐로 해결하려 하였으나 시간 초과가 났다. 코드 자체는 맞았는데 10000이상으로 넘어가면 확실히 시간이 너무 오래걸렸다.

class Node:
  def __init__(self, val, next):
    self.val = val
    self.next = next

class Queue:
  def __init__(self):
    self.front = None
    
  def push(self, val):
    if not self.front:
      self.front = Node(val, None)
      return
    node = self.front
    while node.next:
      node = node.next
    node.next = Node(val, None)

  def pop(self):
    if not self.front:
      return None
    node = self.front
    self.front = node.next
    return node.val
  
  def is_empty(self):
    return self.front is None

n = int(input())
q1 = Queue()
for i in range(1,n+1):
  q1.push(i)

# while not q1.is_empty():
#   print(q1.pop())

while not q1.is_empty():
  ans1 = q1.pop()
  ans2 = q1.pop()
  if ans1 == None:
    result = ans2
    break
  elif ans2 == None:
    result = ans1
    break
  q1.push(ans2)

print(result)

두 번째 시도 : 리스트로 코드 길이를 줄이고 list compression을 이용했으나 또 시간 초과가 났다. 첫 번째도 그렇고 두 번째도 그렇고 삽입 과정에서 자꾸 시간이 지연되는 것 같아 파이썬 큐 시간초과를 찾아본 결과... python에서는 collections의 deque를 사용하는 게 훨씬 빠르다는 사실을 알아냈다.

n = int(input())
li = [i for i in range(n,0,-1)]

res1 = 0
res2 = 0
for i in range(n):
  if li:
    res1 = li.pop()
  if li:
    res2 = li.pop()
  li.insert(0,res2)
  
print(res1)

세 번째 시도 :

import collections
deq = collections.deque()

n = int(input())

for i in range(1,n+1):
  deq.insert(0,i)

res1 = 0
res2 = 0
for i in range(n):
  if deq:
    res1 = deq.pop()
  if deq:
    res2 = deq.pop()
  deq.appendleft(res2)
  
print(res1)

성공!

• input() 대신 sys.stdin.readline()이 빠르다는 얘기를 보고 시도해보았으나...백준이 돌리는 엔진으로는 형변환이 안 되는 것 같아 그냥 input()으로 했다. 사실 저거 하나 바꾼다고 해결될 시간초과였으면 진작에 해결됐겠지...

숙제

❓ 스택을 이용해 다음 연산을 지원하는 큐를 구현하라.

• push(x) : 요소 x를 큐 마지막에 삽입한다.
• pop( ) : 큐 처음에 있는 요소를 제거한다.
• empty( ) : 큐가 비어있는지 여부를 리턴한다.

class Node:
    def __init__(self, item, pre, next):
        self.item = item
        self.pre = pre
        self.next = next

class Stack:
    def __init__(self):
        self.top = None
        self.bottom = None

    def push(self, item):
        self.bottom = Node(item, self.bottom, None)
        if not self.top:
            self.top = self.bottom
            return
        self.bottom.pre.next = self.bottom


    def pop(self):
        if not self.top:
            return None
        pop_item = self.top.item
        self.top = self.top.next

        return pop_item

    def is_empty(self):
        return self.top is None

stack = Stack()

for i in range(1, 6):
    stack.push(i)

while not stack.is_empty():
    print(stack.pop())

해시 테이블

비어있는 슬롯에 해시함수를 거친 데이터를 삽입하는 자료구조이다. 데이터 충돌이 발생할 시 오픈 어드레싱이나 체이닝 둘 중 하나의 기법을 사용해 데이터를 삽입한다. 자세한 내용은
https://velog.io/@dlskawns/CS-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%ED%95%B4%EC%8B%9C%ED%95%A8%EC%88%98-%EC%A0%95%EB%A6%ACChaining-Open-addressing

파이썬에서 해시 테이블을 이용하는 자료형이라면 딕셔너리 자료형이 있는데, 이 모듈은 오픈 어드레싱 기법을 채택하고 있다.

• 참고 : https://github.com/python/cpython/blob/16901c0482734dbd389b09ca3edfcf3e22faeed7/Objects/dictobject.c#L850

힙

주로 파일 구조를 구성할 때나 데이터를 검색할 때 이용되는 자료구조이다. 크기순대로 저장되어 있는 완전 이진 트리의 구조라 자료를 찾을 때의 시간 복잡도를 획기적으로 줄일 수 있다. 좌우 자식의 관계 또한 대소로 정해져 있는 이진 탐색 트리와는 달리 오로지 부모 자식간의 대소 관계만 따진다.

보통 부모에서 자식 노드로 갈 수록 크기가 작아지는 max힙을 많이 이용한다.

삽입

원소를 맨 마지막 리프 노드에 넣어준 뒤 부모 노드와 비교해 가면서 자리를 바꿔주는 방식으로 삽입한다. 예전에 신입 사원을 받으면 일단 말단에 배정한 뒤 실력에 따라 직급이 상승하는 것과 비슷하다는 말을 본 기억이 있다.

삽입의 시간 복잡도는 힙의 높이와도 같은 O(logN) 이다.

삭제

삭제는 삽입과는 반대로 루트 노드부터 추출한다. 사장을 자르면 바로 아래 직위에 있던 사람이 그 자리로 올라오는 거라고 생각하면 된다고 했다.

삭제의 시간 복잡도는 삽입과 똑같은 O(logN) 이다.

• 힙에서 삽입 / 삭제 연산을 수행한 뒤 힙의 성질을 유지하도록 힙을 재조정하는 과정을 Heapify라고 한다.

힙은 예전에 C로 구현해둔 게 있어서 그걸 예시로 쓴다.
파이썬에서는 heapq 모듈을 import 해서 힙의 기능을 간편하게 쓸 수 있다.

#include <stdio.h>
#include <stdlib.h>

int size;

int main()
{
    int A[100] = {};
    
    printf("size : ");
    scanf("%d", &size);
    for(int i = 0; i < size; i++){
        scanf("%d", &A[i]);
    }
    Heapsort(A, size);
    print_ar(A);

    return 0;
}

int print_ar(int *A){
    for(int i = 0; i < size; i++){
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

int Heapsort(int A[], int n){
    int tmp;
    Build_heap(A, n);
    for(int i = n; i > 0; i--){

        
        tmp = A[0];
        A[0] = A[i-1];
        A[i-1] = tmp;
        
        Heapify(A,0,i-1);

    }
    
    return 0;
}

int Build_heap(int A[], int n){

    for(int i = n/2-1; i >= 0; i--){
        Heapify(A, i, n);    //단말 노드 바로 위의 노드부터 비교 시작

    }
    
    return 0;
}

int Heapify(int A[], int i, int n){
    int j = i;
    int max;
    int tmp;
    
    while(1){

        if(2*j + 1 < n && A[2*j + 1] > A[j]){  //왼쪽 자식노드가 n보다 작고 부모보다 크다면
            max = 2*j+1;  
        } else{
            max = j;
        }

        if(2*j+2 < n && A[2*j + 2] > A[max]){  //오른쪽 자식노드가 n보다 작고 부모보다 크다면
            max = 2*j + 2;
        } 

        if(max != j){    //최댓값이 j가 아니라면 교환
            tmp = A[j];
            A[j] = A[max];
            A[max] = tmp;

            
        } else  break;
        Heapify(A, max, n);
    }

    return 0;
}

• C에서 이진 트리는 배열의 형태로 구현했다.

힙 응용 - k번째로 큰 수

https://leetcode.com/problems/kth-largest-element-in-an-array/

from heapq import heappush, heappop

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heappush(heap, (-num,num))
        result = 0
        for i in range(k):
            result = heappop(heap)[1]
        return result

이거 정렬 알고리즘 사용해도 될 것 같은데 괜히 힙 사용해서 시간 복잡도만 늘렸다는 생각이 든다.