Computer Science50 4. Priority Queue & Heap Priority Queue란? Queue의 경우 먼저 들어간 데이터가 먼저 나오게 된다. Priority Queue는 이와 다르게 들어간 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나오게 된다. 그렇다면 Priority Queue를 어떻게 구현해야 할까? 첫번째, 배열로 구현하여 삽입 시마다 우선순위에 맞게 정렬한다. 이 방법은 항상 정렬된 형태를 유지하기 때문에 데이터를 꺼낼 때 용이하지만, 삽입 시 O(n)의 시간이 필요하다. 두번째, 리스트로 구현하여 데이터를 불러올 때 우선순위가 높은 데이터를 찾는다. 이 방법은 삽입 시 상수 시간이 걸려 용이하지만, 데이터를 꺼낼 때마다 O(n)의 시간이 필요하다. 이처럼 배열과 리스트로 Priority Queue를 구현하면 이와 같이 데이터 삽입이나 요청.. 2020. 5. 22. 3-2. Tree Traversal Tree의 노드들을 탐색하는 데에는 여러 가지 방법이 있다. 기본적으로 노드를 방문하는 순서에 따라 preorder, postorder, inorder traversal이 있고, 이 외에도 level-order traversal, Euler tour traversal 등 여러 가지 순회 방식이 있다. 하나씩 순회 과정을 살펴보자. Preorder Traversal (전위 순회) 전위 순회는 현재 노드를 먼저 탐색하기 때문에 붙여진 이름이다. 따라서 1.현재 노드 2. 왼쪽 child 노드부터 차례대로 순으로 방문하게 된다. 실제 위 트리를 예시로 전위 순회를 실행해보자. 먼저 root 노드인 0번 노드를 방문하고, 그 다음으로 left child인 1번 노드를 방문하게 된다. 1번 노드를 방문했다면, 다.. 2020. 5. 21. 3-1. Binary Tree Binary Tree Binary Tree(이진 트리)는 각각의 노드가 최대 2개의 child 노드를 갖는 tree를 말한다. 이진 트리는 노드들이 어떻게 구성되어 있는지에 따라 다음과 같이 부르기도 한다. Full Binary Tree (정 이진 트리) 모든 노드가 0 또는 2개의 child를 갖는 binary tree. Perfect Binary Tree (포화 이진 트리) 모든 internal 노드가 2개의 child를 갖는 binary tree. 모든 leaf 노드가 같은 level에 있다. (Proper Binary Tree라고도 함) Degenerate Tree (변질 트리) 모든 parent 노드가 하나의 child만 갖고 있는 tree. (Pathological Tree라고도 함) Comp.. 2020. 5. 21. 3. Tree Tree Tree의 기본적인 정의는 Circuit이 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 Graph를 말한다. 따라서 Tree는 Graph의 종류 중 하나이며 다음과 같은 특징을 갖는다. Parent, Child 연결 리스트의 경우 다음 노드 하나를 가리키지만 Tree의 경우 여러 개의 노드를 가리킬 수 있다. 이렇게 가리켜진 노드들을 child 노드라고 하며 가리킨 노드를 parent 노드라고 한다. 예를 들어 4번, 5번 노드는 2번의 child이고, 2번 노드는 4번, 5번 노드의 parent이다. 동시에 5번 노드는 8번 노드의 parent이고, 2번 노드는 0번 노드의 child이다. 이처럼 parent, child 노드는 상대적인 개념이다. 이에 더해 ancestor는 해당 노드의 .. 2020. 5. 18. 2. Queue & Stack Queue Queue는 한글로 번역하면 줄이라는 뜻인데 줄을 서는 원리와 똑같이 동작하기 때문이다. 먼저 들어간 element가 먼저 나오는, First In First Out (FIFO) 형태를 갖는 자료구조이다. 따라서 index에 따라 넣고 빼는 것이 아닌 맨 뒤에 넣거나(enqueue), 맨 앞에서 빼는(dequeue) 것만 가능하다. Enqueue 위와 같이 리스트 형태로 구현된 queue가 있을 때, enqueue를 통해 노드를 추가하고 싶다면 추가할 새 노드를 만들어 준 뒤 맨 뒤 노드의 포인터를 새 노드로 지정해주면 된다. 이 때 마지막 노드의 포인터(tail)를 따로 저장해두지 않으면 처음부터 끝까지 탐색해야 하므로 미리 저장해두어야 한다. 따라서 언제나 위와 같이 상수 시간이 걸리므로 .. 2020. 5. 12. 1. Array & Linked List Array A ordered sequence of elements of the same type 배열이란 같은 형태의 요소들로 이루어진 자료구조를 말하며 다음과 같은 특징이 있다. - 각각의 element들은 index를 통해 참조한다. - 특정 순서에 따라 저장하기에 편리하다. - 미리 크기를 설정해주어야 한다. Search 배열은 i 번째 element를 찾을 때 시작 주소 + ( i × 자료형의 크기 ) 계산만 하면 위치를 찾을 수 있다. 따라서 탐색에 걸리는 시간이 상수이므로 시간복잡도는 O(1)이 된다. Insertion 위와 같은 배열에서 2와 6 사이에 4를 넣고 싶다면 뒤의 모든 element들을 한칸씩 뒤로 옮겨주어야 한다. 따라서 삽입에 element 갯수 n에 비례한 시간이 소모되므로.. 2020. 5. 12. Concurrency Problem의 종류 및 원인 Concurrency Problem이란? 하나의 process 안에서 여러 개의 thread를 사용하는 경우가 많다. 여러 개의 thread를 사용하면서 동시에 공유 자원에 접근하거나 잘못된 scheduling으로 인해 오류가 발생할 수 있다. 이렇게 동시에 여러 개의 thread를 관리하면서 생기는 문제들을 Concurrency Problem이라고 한다. 그렇다면 Concurrency Problem에는 어떤 것들이 있을까? 먼저 대표적인 Concurrency Problem인 Deadlock에 대해서 알아보고, 추가적으로 다른 Problem들을 알아보자. Deadlock Deadlock이란 여러 가지 원인으로 인해 아무도 lock을 획득하지 못하고 멈춰있는 교착상태를 말한다. 예를 들어 위와 같이 여러 .. 2019. 9. 24. Semaphore란? Semaphore란? Semaphore는 간단하게 말하면 정수 하나라고 생각할 수 있다. 여기에 wait와 post 함수를 통해서 이 정수 값을 바꿈으로써 thread를 통제한다. 어떻게 정수값을 통해 thread를 관리하는지 알아보자. Semaphore 사용법 Semaphore를 사용하기 위해서는 먼저 Semaphore 객체를 만들어주어야 한다. 객체를 만들어 준 뒤에는 init 함수를 통해 Semaphore 값을 초기화시킨다. 이 때, 첫번째 파라미터는 Semaphore 객체, 두번째 파라미터는 Semaphore를 사용할 범위 (0: 같은 process / 1: 다른 process), 세번째 파라미터는 Semaphore 값을 초기화 할 값이다. 객체를 초기화 했다면 이제 wait()와 post() 함.. 2019. 9. 16. Condition Variable이란? Condition Variable이란? Condition Variable은 특정 조건을 만족하기를 기다리는 변수라는 의미이다. 따라서 이를 이용하여 주로 thread간의 신호 전달을 위해 사용한다. 하나의 thread가 waiting 중이면 조건을 만족한 thread에서 변수를 바꾸고 signaling을 통해 깨우는 방식이다. Condition Variable 사용법 Condition Variable은 앞서 말했 듯 waiting과 signaling을 사용한다. 따라서 기본적으로 cond_wait()와 cond_signal() 함수를 사용하게 된다. 또한 wait와 signal 내부적으로 unlock()과 lock()이 각각 앞 뒤로 있기 때문에 외부를 lock()과 unlock()으로 감싸야 한다. 그.. 2019. 9. 5. 이전 1 2 3 4 5 6 다음
