공부중

⊙TCP와 UDP ○TCP/.IP 프로토콜 스택 TCP/IP 스택 이 4개의 계층으로 나뉜다 이로 데이터 송수신의 과정을 네 개의 영역으로 계층화 했다는 의미 이다. 인터넷 기반의 효율적인 데이터 전송을 하나의 큰 프로토콜 설계로 해결한 것이 아닌 작게 나눠서 계층화 하려는 노력이 시도 끝에 TCP/IP프로토콜 스택이 나왔다 그래서 TCP 소켓을 생성해 데이터를 송 수신할 경우 위의 그림과 같이 4개의 계층으로 통해 데이터를 송수신 하게 된다. 그러나 UDP소켓을 생성하여 데이터를 송수신할 경우 다음 네 계층을 통해 데이터를 송 수신 하게 된다. 이러한 각각 계층은 OS와 같이 소프트웨어 혹은 NIC같은 물리 장치가 담당한다. ○ LINK 계층 LINK계층은 물리적인 영역의 표준화에 대한 결과이다. 가장..

퀵 정렬(Quick Sort)… 이름처럼 빠르다고 한다. 퀵 정렬은 분할 정복(Divide and Conquer)에 기반되어 있다. 전체를 공략하는 대신 전체를 구성하는 구성 요소들을 잘게 나누어 쪼갠 적을 공략하는 기법이다. 퀵 정렬은 다음과 같이 정렬을 수행한다. 데이터 집합 내에서 임의의 기준을 선택하고 기준보다 작은 것은 순서에 관계 없이 기준의 왼쪽에 큰 것은 오른쪽에 위치 이렇게 나눈 데이터를 위에서와 같이 임의의 기준을 다시 선택하고 같은 방법으로 데이터를 분할 한다. 1과 2를 더 이상 나눌 수 없을 때 까지 반복 하면 정렬이 완성 된다. 642315↑기준→ ←642315↑기준 → ←642315↑기준 → ←642315↑기준 →←642315↑기준 → ←기준을 6으로 잡고 Left와 Right..

삽입 정렬은 데이터 집합을 순회 하면서 정렬이 필요한 요소를 뽑아내 이를 다시 적당한 곳에 삽입해가는 알고리즘이다. 데이터 집합에서 정렬 대상이 되는 요소들을 선택 이 정렬 대상은 왼쪽부터 선택해 나가며, 그 범위가 처음에는 2개지만, 알고리즘 반복 횟수가 늘어날 때마다 1개씩 커진다. 정렬 대상의 최대 범위는 '데이터 집합의 크기 - 1'이다. 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 가지고 있는지 확인 그렇지 않으면 정렬 대상에서 뽑고 이 요소가 위치할 적절한 곳을 정렬 대상 내에서 찾는다. (적절한 위치는 자신보다 더 작은 요소가 없는 위치를 말함) 뽑은 요소를 삽입할 적절한 곳을 찾았을 때 정렬 대상 내에서 삽입할 값보다 큰 값을 갖는 모든 요소를 한 자리씩 오른쪽으로 ..

버블 정렬은 알고리즘이 데이터를 정렬하는 과정이 물속에서 일어난 거품이 위로 올라오는 모습과 같다고 해서 붙혀졌다. 실제로 데이터가 뜨거나 하지는 않지만 간단하고 손쉽게 할 수 있는 정렬이다. 버블정렬은 데이터들을 순회하면서(곳곳히 돌면서) 교환을 통해서 정렬을 한다. 다음을 보자. 5164231부터 6까지 무작위로 저장된 배열이 있다고 해보자 이때 버블 정렬을 이용해 오름차순으로 정렬 해보자. 516423먼저 5와 1을 비교했을 때 5가 1보다 큰 수이므로 서로 위치 교환을 해준다. 1564231과 5의 위치를 바꾼 뒤 5와 6을 비교해보자. 5는 6보다 작으므로 이동의 변화가 없다. 그러므로 비교대상을 다음으로 넘어간다. 156423비교 대상을 넘어가서 6과 4를 서로 비교해 보자. 6은 4보다 큰 ..

우선순위 큐에 적당한 것은 힙으로 결정이 되었다. 힙은 '트리 구조'이다. 트리를 구현하는 방법에는 배열과 연결 리스트 둘 중 하나를 선택 해야 하는데.. 앞에서 트리를 구성했을 때 연결 리스트로 구현을 하였으니 여기서도 똑같이 구현 하면 되겠지만 이와 같은 단점이 있다. "연결 리스트를 기반으로 힙을 구현시 새로운 노드를 힙의 마지막 위치에 추가하는 것이 쉽지 않다." 해결은 가능하고 사소하지만 간단한 문제가 아니다.. 배열 기반의 힙의 경우 이런 문제는 매우 간단하게 처리 된다. 그래서 '힙'같이 새로운 노드를 추가한 이후에도 완전 이진 트리를 유지해야 하는 경우 연결리스트가 아닌 배열을 기반으로 트리를 구현해야 한다. 배열을 기반으로 힙을 구현할 때 필요한 것은 다음과 같을 것이다. 왼쪽과 오른쪽 ..

큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오나 우선순위 큐는 다르다. 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 일상 예제로 병원의 응급실을 예로 들어보면 물론 모든 환자분들이 빠른 치료를 받고 완치가 되면 좋겟지만 제일 응급한 환자부터 치료를 하게 된다. 즉 우선순위가 높은 환자가 먼저 치료를 받는 것이다. 이렇게 우선순위 큐에서 중요한 것은 우선순위 이다. 데이터를 근거로 우선순위를 판단해야 되고 목적에 맞게 우선순위를 프로그래머가 판단해서 결정해야 되는 일이다. 우선순위가 다른 데이터 뿐만 아니라 같은 데이터가 존재할 수도 있다. 우선순위 큐를 구현하는 방법은 세 가지로 나뉘어진다. 배열을 기반으로 구현하는 방법 연결리스트를 기반으로 구현 하는 방법 힙(Heap)을 이용하..

힙(Heap)은 무엇인가를 차곡차곡 쌓아 올린 더미라는 뜻을 가지고 있다. 그런 뜻을 가진 힙(Heap)이.. 이 자료구조에서의 힙(Heap)은.. 간단히 정의를 내리자면 힙은 완전 이진 트리이다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 루트노드에 저장된 값이 가장 커야 한다. 위 문장에서 말하는 형태의 이진트리는.. 다음 그림들과 같다. 위와 같이 루트 노드로 올라갈수록 값이 커지는 완전 이진 트리를 '최대 힙(Max Heap)' 이라 한다. 이번에는 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 '최소 힙(Min Heap)'이라 한다.

이진 트리의 경우도 배열과 리스트 2가지 방법으로 구현이 가능하다. 트리가 완성된 이후에는 매우 자주 탐색이 이루어 진다. 그래서 배열로 구성 해볼 만 하다. 배열을 기반으로 이진 트리를 구현하려면 노드에 고유의 노드 번호를 부여해야 한다. 이 번호들은 데이터가 저장되어야 할 배열의 인덱스 값이다. 인덱스가 0인 배열의 요소를 사용하지 않는 이유는 개인 차가 있겠지만 구현의 편의와 실수를 줄이기 위해서 일반적으로 사용하지 않는다. 다음은 연결리스트 기반의 구현방법이다. 그림만 봐도 단번에 이해가 될 만큼 쉽게 표현 가능하다. 그림에 나온대로 구성하면 되므로 별 다른 설명은 필요 하지 않을 것 같다.. 만약에.. 연결리스트로 이진 트리를 구현 했다고 했을시. "삭제는 어떻게 하겠는가?" 둘 이상의 노드로 ..