Month: November 2024

학습개요 차례로 정렬된 데이터 리스트 k를 완전한 순서를 유지하는 하나의 리스트로 만드는 과정을 합병 정렬 이라고 합니다. 이 합병 정렬에 사용하는 트리가 선택트리입니다. 선택트리를 구성하는 방법에는 승자트리와 패자트리가 있습니다. 승자트리는 각 노드가 두 개의 자식노드 보다 더 작은 값을 갖는 완전 이진트리입니다. 작은 값이 승자로 올라가는 토너먼트 경기와 유사하다고 할 수 있습니다. 패자트리는 루트노드 위에 … Read more

학습개요 힙은 완전이진트리형태이며 부모노드와 자신 노드간의 관계를 값이 대소관계를 적용하여 정의됩니다. 노드간의 관계에서 부모 노드가 자식노드보타 크면 최대힙이라고 하며, 부모 노드가 자식노드보다 작으면 최소힙 이라고 합니다. 힙에서 노드를 삭제하거나 삽입할 경우에는 완전이진 트리형태를 계속 갖춰야하고, 부모노드와 자식노드 사이의 대소관계도 계속 갖춰줘야 합니다. 즉, 노드간의 관계와 완전이진트리 정의를 만족시키며 노드의 삭제 연산과 삽입 연산을 구현해야 합니다. … Read more

학습개요 이진 트리를 순회할 때 방문하지 않고 지나쳐온 노드를 저장하는 방법으로 스택을 사용했습니다. 하지만 스택에 저장하고 스택을 관리해야 하는 번거로움이 있었습니다. 이러한 번거로움을 없애기 위한 새로운 방법이 스레드 트리입니다. 정해진 순회 방법에 따른 방문 순서를 유지하는 포인터를 스레드라고 합니다. 그리고 스레드라는 포인터를 갖는 이진 트리를 스레드 트리라고 합니다. 스레드의 종류는 두 가지가 있습니다. 오른쪽 스레드와 … Read more

학습개요 트리는 노드 혹은 정점으로 구성된 논리적인 계층이 있는 구조입니다. 데이터 사이의 계층 관계, 포함 관계 등을 나타내는 곳에서 사용되는 자료구조입니다. 나무를 거꾸로 놓은 모양이라 트리라 부릅니다. 그렇기 때문에 용어들도 나무와 관련 있게 뿌리, 잎, 서브 트리 등의 단어를 사용하며 정의됩니다. 트리에서는 용어들을 정확하게 아는 것이 중요합니다. 트리에 속한 모든 노드의 차수가 2 이하인 트리를 … Read more

학습개요 단순 연결 리스트는 하나의 링크 부분이 존재하고, 각각의 노드는 후행 노드만을 가리키는 구조입니다. 따라서 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 합니다. 이러한 단점을 보완하기 위해, 선행 노드를 가리키는 링크 부분과 후행 노드를 가리키는 링크 부분을 갖는 이중 연결 리스트가 제안되었습니다. 단순 연결 리스트가 사용하지 않는 마지막 노드의 링크 부분을 활용하면서도 프로그램 … Read more

학습개요 리스트는 배열과 달리 원소들 간의 논리적인 순서를 위한 자료구조입니다. 원소들 간의 순서가 논리적으로(추상적으로) 지켜져야 하며, 각각의 원소가 저장되는 물리적인 위치가 연속적이든 불연속적이든 상관하지 않습니다. 배열을 이용하여 리스트를 구현하면, 원소의 논리적인 순서를 지키기 위해 원소의 이동이 많아집니다. 따라서 리스트를 구현하기 위해서는 일반적으로 포인터 변수를 이용한 연결 리스트를 이용합니다. 포인터 변수의 사용과 동적인 메모리 할당 방법을 … Read more

학습개요 큐는 스택과 유사하게 입출력 순서를 중심으로 자료들 간의 관계가 성립되는 자료구조입니다. 입출력 순서의 관리를 통해 입력이 가장 빨랐던 자료가 가장 먼저 출력되는 관계를 표현합니다. 그렇기 때문에 큐는 줄을 서는 순서에 따라서 공평하게 서비스를 해주는 경우에 많이 사용되고, 자원의 할당을 받으려는 작업들 간의 순서를 관리하기 위해 사용되는 경우가 많습니다. 큐를 기반으로 하는 입력 연산을 수행하기 … Read more

학습개요 스택은 입출력 순서를 중심으로 자료들 간의 관계가 성립되는 자료구조입니다. 즉, 입력이 가장 늦게 된 자료가 가장 먼저 출력되는 관계를 표현합니다. 그렇기 때문에 스택은 왔던 길을 되돌아가는 경우에 많이 사용되고, 예전에 처리했던 값들을 역순으로 되돌아가며 찾아내서 처리해야 하는 경우에 많이 사용됩니다. 스택 구조는 입력 연산을 수행하기 전에 정의된 스택의 크기를 항상 확인해야 합니다. 스택의 크기보다 … Read more

학습개요 배열은 자료의 추상화된 의미와 구체화된 의미가 유사한 자료구조입니다. 자료간의 관계가 추상화되었을 때와 구체화되어 저장되었을 때가 동일하다는 의미입니다. 배열은 자료에 해당하는 원소(원소값)와 몇 번째에 해당하는 지를 의미하는 인덱스로 구성됩니다. 즉, 배열은 순서를 표현하는 인덱스와 값을 표현하는 원소값의 쌍으로 이루어집니다. 이러한 특성은 2차원 배열이나 3차원 배열에서도 지켜집니다. 즉, 1차원 배열의 확장된 모양이 2차원 배열이며 3차원 배열이 … Read more

학습개요 자료구조는 현실세계의 자료를 컴퓨터에게 전달하기 위해 사용되는 자료의 추상화된 형태이다. 특히 자료구조는 알고리즘과 함께 고려되어 구조화되며 컴퓨터과학에서 가장 기본적이고 핵심적인 분야이다. 이 장에서는 자료구조의 기본 개념과 알고리즘과 자료구조와의 관계, 그리고 추상화에 대해서 살펴본다. 학습목표 자료구조와 추상화의 의미를 이해할 수 있다. 알고리즘과 자료구조와의 관계를 이해할 수 있다. 미리 정의된 자료구조와 사용자 정의 자료구조의 차이를 이해할 … Read more