본문 바로가기

전체 글

 (19)
우선순위 큐 우선순위 큐는 이름에서도 의미하듯 우선순위를 정한 큐이다. 큐의 경우에는 줄서기에 비유한다면 우선순위 큐는 응급실의 응급 상황인 사람이 먼저 들어가는 상황에 비유해보자. 이처럼 우선순위가 부여가 된다. 앞서 배운 큐의 핵심 연산은 2가지이다. enqueue() 데이터 삽입 dequeue() 데이터 삭제 이와 마찬가지로 우선순위 큐의 핵심 연산도 2가지 모두 동일하다. 반면에 연산의 결과는 차이가 있다. 큐의 경우에는 먼저 들어간 데이터가 먼저 나오지만 우선순위 큐는 우선순위가 더 높은 데이터가 먼저 나온다. 우선순위 큐를 구현하기 위해서 아래와 같은 3가지의 방법이 있다. ・배열 기반 구현 ・연결 리스트 기반 구현 ・힙 기반 구현 우선 배열과 연결 리스트를 이용하면 간단하게 구현할 수 있다. 1) 배열의..
이진 트리 이진 트리는 배열과 리스트로 구현이 가능하다. 이진 트리에서 이해하기 쉬운 리스트로 구현할 예정이다. 배열 기반 트리는 나중에 나올 '힙'이라는 자료 구조에서 알아보도록 하자. 이 포스트에서는 리스트를 이용하여 이진 트리를 구현해볼 것이다. 노드의 형태 먼저 아래의 그림을 보면 노드의 형태가 나온다. 이진 트리의 정의를 보면 "노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주한다." 라고 정의되어 있다. 그러므로 아래의 그림은 두 가지 형태는 같은 노드로 표현이 된다. 이진 트리의 연결 아래의 그림을 보면 B노드를 생성한 후 A 노드의 왼쪽 자식으로 연결해준 모습을 보여준다. 연결의 경우 간단하기 때문에 다른 언급은 하지 않겠다. 이진 트리의 순회 트리의 순회 방..
트리 앞에서 봤던 자료구조들은 전부 선형적인 자료구조였다. 지금 알아볼 트리는 비선형적인 자료구조이기때문에 많이 다르게 느껴질 수 있다. 트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다. 나무처럼 가지를 늘려가며 뻗어나가는 것이다. 일상생활에서도 자주 접할 수 있다. 아래의 그림으로 트리가 어떤 형태인지 알아보자. 트리의 기본적인 용어 노드 : 트리의 구성요소에 해당하는 A, B, C, D, E, F 요소들을 노드라고 한다. 간선 : 노드와 노드를 연결하는 선을 간선이라 한다. 루트 노드 : 트리 구조에서 최상위에 존재하는 A노드를 루트 노드라고 한다. 단말 노드 : 잎 노드라고도 불리며 C, D, E, F노드를 단말 노드라고 한다. 내부 노드 : 단말 노드를 제외한..
큐 (리스트를 이용한 구현) 지난 포스팅에서는 배열을 이용하여 큐를 구현해보았다. 이번 장에서는 리스트를 이용하여 큐를 구현해볼 예정인데 큐는 배열을 사용하였을 경우 front를 기반으로 한 칸씩 이동하며 데이터를 삭제하였다. 포인터를 이용할 경우에는 front가 비어있을 경우 큐가 비었다고 볼 수 있다. 아래의 그림은 최초의 큐 형태이다. ① 데이터 삽입을 보자. 첫 번째 노드가 추가가 될 경우 Front와 Rear는 첫 번째 노드를 가리키게 되며 두 번째 노드의 추가로부터는 Rear가 새로운 노드를 가리키게 추가함으로써 데이터 삽입이 완료가 된다. ② 데이터의 삭제를 보자. 삭제할 노드를 임시 변수에 저장해둔 후 Front를 다음 위치를 가리키게 해준다. 그 이후 임시 변수에 담아두었던 노드를 삭제한 후 데이터를 반환한다. 삭제..
큐 (배열을 이용한 구현) 큐는 앞서 설명한 스택과 함께 언급되며 비교되는 자료구조이다. 스택은 먼저 들어간 데이터가 나중에 나오는 구조(LIFO)이지만 큐는 먼저 들어간 데이터가 먼저 나온다. 이는 일상생활에서도 자주 접할 수 있다. 버스를 타기위해 줄을 서는데 먼저 선사람부터 먼저 타는 상황을 떠올려보자. 이렇듯 큐의 구조는 FIFO(First In First Out)의 구조로 이루어진다. 들어가기에 앞서 1. Front와 Rear라는 용어가 나오는데 Front는 큐의 머리를 뜻하며 Rear는 큐의 꼬리를 뜻한다. 2. 스택은 Push()와 Pop()으로 삽입, 삭제를 하지만 큐의 경우에는 Enqueue()와 Dequeue()로 삽입, 삭제가 이루어진다. 큐의 구현에 대한 원리 ① 데이터 삽입을 보자. 큐는 뒤에서 넣고 앞으로..
스택 (리스트를 이용한 구현) 리스트를 이용한 구현 앞서 구현한 배열을 리스트로 변경할 경우 연결 리스트의 특징을 그대로 가져오게 된다. 리스트라고 말하면 복잡해 보이지만 "역순으로 삭제가 가능한 리스트이다"라고 생각한다면 그다지 어렵지 않다. 아래의 내용은 비어있는 초기의 리스트 스택 형태이다. 들어가기에 앞서 1. 리스트 구현과 동일하게 노드가 존재하며 노드는 데이터와 다음 위치를 가리킬 수 있는 노드를 가지고 있다. 2. 스택은 top이 아닌 head로 변경이 되며 이는 현재 위치를 가리키는 변수이다. ① 데이터 삽입을 보자. 배열을 이용한 스택과 동일하게 Push()라는 함수 호출로 값을 삽입한다. 먼저 10을 추가해보자. 10을 추가할 경우 head는 새로운 노드를 가리키게 되며 nextNode는 자기 자신의 이전 노드를 가..
2) 에코 서버 에코서버란 클라이언트가 전송해주는 데이터를 그대로 되돌려 전송해 주는 기능을 가진 서버를 말한다. 에코 서버 클라이언트 모델의 특징은 몇 바이트를 송수신할 것인지 예상할 수 있다는 것이 큰 특징이다. 그 이유는 전송한만큼 바이트를 되돌려 받기 때문이다. 서버 프로그램의 구현 과정 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 #include #include #pragma comment(lib, "ws2_32..
* Iterative 서버 https://developer-jun.tistory.com/11 위의 과정에서 Hello World 서버 프로그램을 구현해보았다. 그렇지만 클라이언트가 한 번 접속한 후 바로 종료가 되어버린다. 이러한 서버는 우리가 생각한 서버가 아니다. 위의 과정에서는 어떤식으로 서버와 클라이언트가 데이터를 송수신하는지 배워왔다. 이번에는 클라이언트가 여러번 접속을 하여도 종료가 되지않는 서버를 배워보자. 위의 흐름도를 살펴보면 적절한 송수신 이후 클라이언트의 연결을 종료한 후 accept() 함수를 호출하기 전으로간 후 루프문을 돌리고 있다. 이것이 핵심이다. 아래의 코드를 보자. 클라이언트 코드는 Hello World 서버의 코드와 동일하기 때문에 그대로 사용하면 된다. 1 2 3 4 5 6 7 8 9 10 11..

티스토리툴바