개발자 꿈나무의 블로그

* 개요 수학, 특히 그래프 이론에서 회로가 없는 연결된 무향의 그래프를 Tree(트리)라고 한다. 트리의 각 부분의 명칭과 용어는 다음과 같다. 트리는 항상 root 노드에서 시작된다. 루트 노드는 자식 노드를 가지며, 간선으로 연결되어 있다. 자식 노드의 개수는 차수라고 하며, 크기는 자신을 포함한 모든 자식 노드의 개수다. 높이는 현재 위치에서부터 리프까지의 거리, 깊이는 루트에서부터 현재 노드까지의 거리다. 트리는 그 자식도 트리인 서브트리 구성을 띤다. 레벨은 0부터 시작한다. 트리는 항상 단방향이기 때문에(단방향이 아니면 순환 참조가 발생하여 문제 발생) 간선의 화살표는 생략이 가능하다. 일반적으로 방향은 위에서 아래로 향한다. 루트 노드(root node/root): 트리에서 부모가 없는 최..

* 개요 Hash Table(해시 테이블)은 Index(색인)에 해시값을 사용하는 자료구조로, 정렬을 하지 않고도 빠른 검색, 빠른 삽입이 가능하다는 특징을 가진다. 해시는 리스트를 사용하는 접근법은 동일하지만, 여기에 색인 개념이 추가되어 있다. 충분히 큰 공간을 할당받은 다음, 해시 함수를 이용하여 고유 인덱스를 생성한다. 그리고 이 고유 인덱스와 맞는 위치에 데이터를 저장한다. 예를 들어, 0 ~ 100까지의 데이터를 담을 수 있는 리스트를 생성하고, '사과' 라는 단어에 해시 함수를 적용하여 50이라는 인덱스가 생성되면, 리스트의 50번 인덱스에 '사과'를 저장하는 방식이다. 언제나 동일한 해시 값을 반환하기 때문에 '사과'를 입력하면 50이라는 인덱스가 나오므로, 정렬하지 않고도 데이터를 탐색할..

* 개요 Deque(덱)은 단뱡향으로만 데이터의 삽입 / 삭제가 가능했던 큐와는 달리 양방향으로 데이터의 삽입 / 삭제가 가능한 자료구조이다. 즉, 스택으로도 쓸 수 있고, 큐로도 쓸 수 있다는 장점이 있다. 리스트 자료형이 있는데, 덱을 많이 사용하는 이유는 리스트보다 덱의 속도가 훨씬 빠르기 때문이다. 리스트는 O(N), 덱은 O(1)의 시간 복잡도를 가진다. * 파이썬으로 구현한 덱 deque 모듈을 활용하여 덱을 구현하였다. from collections import deque queue = [] dq = deque(queue) dq.append(1) # 1 dq.append(2) # 1 2 dq.append(3) # 1 2 3 dq.appendleft(0) # 0 1 2 3 dq.pop() # ..

* 개요 Circular Queue(원형 큐)는 큐의 변형된 구조로서, 데이터를 넣는 부분(rear)과 데이터를 빼는 부분(front)을 포인터로 지정함으로써,enqueue와 dequeue를 하는 형태의 자료구조이다. 원형 큐에서 정해둔 큐의 크기보다 더 큰 경우(큐가 가득 찬 경우), 큐가 비어있을 경우에 포인터가 같은 위치를 지정하기 때문에 이를 해결하기 위해 한 공간을 비워놓는다.(None or Null) * 파이썬으로 구현한 원형 큐 원형 큐를 리스트로 구현하였다. MAX_SIZE = 5 class CircularQueue: def __init__(self): self.front = 0 self.rear = 0 self.queue = [None] * MAX_SIZE def enqueue(self,..

* 개요 Priority Queue(우선순위 큐)는 선입선출 구조를 가지는 일반적인 큐의 자료구조와는 달리, 데이터의 삽입은 순서와 관계가 없지만 삭제할 때는 우선순위가 높은 원소부터 삭제가 되는 자료구조이다. 우선순위 큐의 대표적인 예로 heap이 있다. * Heap(힙) heap(힙)은 여러 개의 값 중에서 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 이진 트리이다. 힙의 종류에는 최대 힙과 최소 힙이 있는데, 최대 힙은 root 노드에 가장 큰 값이 들어가게 되며, 최소 힙은 root 노드에 가장 작은 값이 들어가게 된다. 힙의 데이터 삽입 및 삭제의 시간 복잡도는 O(logN)이 소요된다. * 파이썬으로 구현한 우선순위 큐(최소 힙) 우선순위 큐를 위해서 파이썬에 내장되어 있는 heapq ..

* 개요 Queue(큐)는 선입선출(First In First Out)의 자료구조를 뜻한다. 대기열이라고도 한다. 데이터가 들어오는 위치는 가장 뒤(rear 또는 back)에 있고, 데이터가 나가는 위치는 가장 앞(front)이다. 큐를 응용한 형태의 큐로는 원형 큐(Circular Queue), 우선순위 큐(Priority Queue) 등이 있다. 보통 배열을 사용해서 큐를 구현하면, enqueue(rear에 데이터 추가)와 dequeue(front의 데이터 삭제)를 할 때마다 계속 데이터가 앞으로 밀려나는 문제가 생기는데, 이를 해결하기 위해 원형 버퍼(원형 큐)를 사용한다. 원형 큐는 이후 포스트에서 다룰 예정이다. * 파이썬으로 구현한 큐(리스트) 큐를 리스트로 구현하였다. class Queue:..

* 개요 Stack(스택)은 후입선출(Last In First Out - LIFO) 특성을 가지는 자료구조이다. 즉, 데이터의 삽입과 삭제가 메모리의 한 쪽 끝에서만 나타난다고 할 수 있다. 메모리에 새로 들어오는 데이터(push)의 위치가 메모리의 말단에 위치하고, 이를 '탑 포인터'라고 일컫는다. 내보내는 데이터(pop) 역시 메모리의 말단을 거친다. 스택의 추상 자료형(Abstract Data Type - ADT)을 살펴보면, 입력 연산은 push, 출력 연산은 pop이다. 조회 연산은 peek라고 하는데, 탑 포인터가 가리키는 데이터를 조회만 할 뿐, 인덱스에 변화를 주지는 않는다. 스택은 흔히 크기를 고정해서 사용하기 때문에, 이를 다 사용하면 데이터가 넘치게 된다. 이에 대한 대처방안이 존재하..

* 개요 이번 포스트에서 다룰 내용은 Circular LinkedList(원형 연결리스트)이다. 원형 연결리스트는 단순 연결리스트에서 마지막 노드가 None이 아닌 첫 노드를 참조하는 형태의 자료구조이다. 바로 원형 연결리스트에 대해 알아보도록 하자. * Circular LinkedList(원형 연결 리스트) Circular LinkedList는 리스트가 비어있지 않으면 어떤 노드도 None을 가지고 있지 않기 때문에 프로그램에서 None 조건을 검사하지 않아도 된다는 장점을 지니고 있다. 그러나 이전 노드를 쉽게 참조할 수 있었던 이중 연결리스트와는 달리, 역방향으로 노드를 순회하기 쉽지 않으며, 무한 루프가 발생할 수도 있다는 단점을 가지고 있다. 해당 단점을 보완한 원형 연결 리스트가 존재하긴 한다..

* 개요 이번 포스트에 다룰 내용은 Doubly LinkedList(이중 연결리스트)이다. 이전 노드를 참조할 수 없어 단방향으로만 노드에 접근이 가능했던 SIngly LinkedList(단순 연결리스트)와 달리 Doubly LinkedList(이중 연결리스트)는 이전 노드 참조가 가능하다. 또한 양방향으로 노드에 접근할 수 있어 삽입/삭제/탐색이 단순 연결리스트에 비해 속도가 더 빠르다는 특징이 있다. * Doubly LinkedList(이중 연결리스트) Doubly LinkedList(이중 연결리스트)는 다음 노드의 참조 뿐만이 아니라 이전 노드의 참조도 같이 가리킬 수 있다. 뒤로 탐색하는게 빠르다는 단순한 장점 외에도 한 가지 장점이 더 있는데, 단순 연결리스트는 현재 가리키고 있는 노드를 삭제하..

* 개요 오늘부터 자료구조를 공부하기로 했다. 백준이나 프로그래머스 문제를 풀면서 자료구조와 알고리즘의 필요성에 대해 알게 되었기 때문이다. 백준 같은 경우 테스트 케이스가 워낙 방대하고 많기에, 자료구조와 알고리즘을 제대로 쓰지 않을 경우 시간 초과가 나는 경우가 종종 발생한다.(보통 테스트 케이스가 10만을 넘어간다면, 시간 복잡도 O(N^2)의 코드를 짰을 때 99퍼센트 확률로 시간 초과가 발생한다.) 자료구조는 컴공과 커리큘럼 기준으로 2학년 과정이지만, 필자는 학부 2학년 시절 코포자(코딩포기자)였기 때문에... 프로그래밍 관련 수업은 제대로 듣질 않았다.(그래서 학점이 개판이다...) 먼저 스터디 멤버들과 자료구조 스터디 커리큘럼에 대해 고민을 해보았는데, 먼저 LinkedList(연결 리스트..