david의 CS Blog

큐(Queue)란? 큐는 스택과 달리 먼저 들어온 데이터가 먼저 나가는 자료구조이다. 줄을 서 있는 사람들을 생각하면 편할 것이다. 큐는 스택와 다르게 삽입과 삭제가 같은 곳에서 일어나지 않는다. 삭제연산은 앞(front)에서 일어나고 삽입 연산은 뒤(rear)에서 일어난다. 이 그림에서 원소 $D$를 추가하면 $C$ 뒤에 추가되고 삭제연산을 하면 가장 맨 앞의 $A$가 삭제된다. 이렇게 먼저 들어온 원소가 먼저 나가는 형태를 선입선출(FIFO: First-In-First-Out)이라고 한다. Queue의 기능 $push(x)$: $x$를 큐의 맨 뒤에 추가한다. $pop()$: 큐의 맨 앞의 원소를 삭제한다. $empty()$: 큐가 비어있으면 $1(true)$, 아니면 $0(false)$을 리턴한다...

Union Find란? Union Find는 상호 배타적 집합을 표현하는 자료구조이다. 전체 집합을 교집합이 없는 부분집합들로 나누어서 저장한다. 상호 배타적: 부분 집합 간의 교집합이 없다.(공통된 원소가 없다), 모든 부분집합의 합집합은 전체 집합이다. 집합을 표현해서 구성 요소 간의 연결 여부 또는 연결성을 가지고 있는지 여부를 따지는 문제에서 많이 사용된다. Union Find의 연산 1. $find$: 해당 원소가 어느 집합에 속해 있는지 찾기 3. $union$: 두 집합을 한 집합으로 합친다. Union Find의 구현 유니온 파인드는 트리 형태의 자료 구조이므로 각 집합을 하나의 트리 모양으로 표현할 것이다. 이와 같은 모양의 집합을 트리로 표현하면 다음과 같이 된다. 이 때 트리의 모양은..

stack이란? 스택은 가장 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조를 가진 LIFO 형태의 자료구조이다. 이 그림처럼 스택은 원소가 들어올 때마다 위에 차곡차곡 쌓이는 형태이다. 이 그림에서 원소 D를 추가하면 원소 C 위에 D가 올라가는 형태가 되고 삭제 연산을 하면 가장 위에 있는 $C$가 삭제된다. 이렇게 나중에 들어온 원소가 가장 먼저 나가게 되는 입출력 형태를 후입선출(LIFO: Last-In-First-Out)이라고 한다. Stack의 기능 push(x) : 원소 x를 스택의 맨 위에 추가한다. pop() : 스택에 원소가 있다면 맨 위에 있는 원소를 삭제하고 리턴한다. empty() : 스택이 비어있으면 1(true), 그렇지 않으면 0(f..