알고리즘 트레이닝/자료구조

개요 단일 연결 리스트는 한쪽 방향으로 연결된 노드로 구성됩니다. 따라서 액세스 및 순회는 첫 번째 노드인 Head에서 시작하여 한번에 한 노드씩 확인하며 진행해야 합니다. 만약 역순으로 액세스 및 순회를 하고자 한다면 이를 효율적으로 할 수는 없을 것입니다. 순회를 위하여 매번 Head에서 시작하여 이전 순회보다 한 노드씩 앞에서 중단하는 방식으로 여러 차례 반복적으로 순회를 수행해야 하기 때문입니다. 따라서 만약 역순으로 순회를 해야 하는 경우가 필요하다면 이번 포스트에서 소개하는 이중 연결리스트(Doubly Linked List)를 도입하는 것이 좋습니다. 구현 (C++) 이중 연결 리스트 각 노드는 3가지 멤버변수를 가지고 있습니다. 두 가지는 각각 이전 노드와 다음 노드를 가리키는 링크 값(포인..

개요 여러 언어에서 기본적으로 제공하는 자료구조인 배열은 특정 순서로 무언가 저장하기에 좋고 간단하지만 단점이 있습니다. 배열은 유연하지 않습니다. 예를 들어, 배열의 크기를 미리 지정해야 하며, 프로그램의 동작 중에 그것을 수정하는 것은 매우 어렵습니다. (이 단점은 C++의 표준 템플릿 라이브러리(STL, Standard Template Library)인 벡터(Vector)에서 해결됩니다.) 또한 요소의 삽입 및 삭제가 어렵습니다. 삽입을 위한 공간을 확보하거나 삭제 후 빈 공간을 채우기 위해 나머지 요소를 좌/우로 이동해야 합니다. 이번 포스트에서는 연결리스트(Linked List)라고 하는 중요한 자료구조의 구현을 살펴보겠습니다. 가장 간단한 형태의 연결 리스트는 한 방향으로 연결된 리스트로 리스..

개요 기하학적 데이터 처리는 이진 검색 트리(binary search tree)의 응용분야 중 하나입니다. 예를 들어 평면에 사각형이 놓여있고 점이 여기저기 분포해 있을 때, 어떠한 점이 사각형 내부에 있는지 또는 얼마나 많은 점이 사각형 내부에 포함되는지 알고 싶을 수 있습니다. 또는 점이 아닌 사각형이 여러 개 있는 경우 어떤 사각형이 서로 겹치는지 알고 싶을 수 있습니다. 우리는 이진검색트리를 이들 문제를 해결하는 데 사용할 수 있습니다. 그 경우 일반적으로 사용하는 문자열과 숫자가 아닌 기하학적 객체(점의 위치 등)를 키로 사용합니다. 1차원 범위검색 (1d Range Search) 정렬된 심볼테이블(Ordered Symbol Table)을 조금 확장하면 1차원 범위 검색과 범위 개수를 셀 수 있..

개요 덱(Double Ended Queue)은 앞과 뒤 양쪽 모두에서 데이터의 삽입과 제거가 가능한 큐를 말합니다. 구현 덱을 구성하는 연산은 다음과 같습니다.fnIinit () : 덱을 초기화 합니다. fnAddFront(item) : 덱의 전단에 item 을 삽입합니다. fnDelFront() : 덱의 전단에서 item 을 1개 삭제 합니다. fnAddRear(item) : 덱의 후단에 item 을 삽입합니다. fnDelRear() : 덱의 후단에서 item 을 1개 삭제 합니다. fnGetFront() : 덱의 전단에 있는 item 을 1개 얻습니다. 단, 삭제는 하지 않습니다. fnGetRear() : 덱의 후단에 있는 item 을 1개 얻습니다. 단, 삭제는 하지 않습니다. fnIsEmpty()..

개요 배열을 이용하여 Queue 를 작성할 경우, 큐의 상태를 저장하는 변수의 값(head, tail)이 감소하지 않고 계속 증가하기 때문에 한계치(QUEUESIZE) 에 도달하면 더 이상 올바른 저장소를 가리키지 못하기 때문에 이를 보완할 수 있는 방법이 필요합니다.변수의 값이 최대치에 도달할 경우, 이를 초기값으로 돌려주는 방식으로 원형큐를 사용완가능합니다.※ 참고로 원형큐를 링버퍼라고도 합할 수 있습니다.다음은 이러한 아이디어를 C 언어로 구현한 것입니다. 구현 앞서 작성한 포스트의 배열로 구현한 (선형)큐의 소스코드를 기초로 합니다. // main.c #define QUEUESIZE 256 #include typedef struct { int head, tail; int items[QUEUESIZ..

자료형(Data Type) 컴퓨터에서 자료(데이터)란 0과 1의 나열입니다. 예를 들어 01001100110010110101110011011100 은 정수일 수도 있고 실수, 문자일수도 있습니다. 이 자료의 해석결과인 값은 자료가 어떤 형(Type)인지에 따라 달라집니다.데이터를 어떻게 해석하면 되는 것인지 컴파일러(또는 인터프리터)에게 알려주는 속성이라고 할 수 있습니다. 이 자료형은 일반적으로 값(value)의 집합과 그 값과 관련된 연산들의 집합을 의미합니다. 집합 즉, 수학적인 모델입니다.자료형은 다음과 같은 종류가 있습니다. 원시자료형 : 기본빌딩블록 (부울, 정수, 실수, 문자 등) 복합자료형 : 원시형 또는 또다른 복합자료형을 조합하여 만든 것 (struct, 배열, 문자열 등) 추상자료형 ..

개요 정점(vertex, 노드, 포인트) 들과 이들 사이의 연결관계를 표현한 추상적 개념 및 자료구조 입니다.그래프의 표현은 아래의 그림과 같이 정점과 이들을 잊는 간선(edge)의 집합으로 나타냅니다. 용어 경로 간선으로 연결된 정점의 순서를 의미합니다. 순환 한 정점에서 시작하여 그 정점 자신으로 돌아오는, 길이가 3 이상인 경로를 의미합니다. 연결된 그래프 모든 정점에 대해서 그래프 내의 다른 정점과 연결된 경로가 있다면 연결된 그래프라고 부릅니다. 완전그래프 그래프의 모든 두 정점쌍이 하나의 간선으로 연결된 그래프 입니다. 트리 순환이 존재하지 않는 그래프입니다. 종류 그래프는 다음과 같이 3가지 종류로 나누어 볼 수 있습니다. 무향 그래프 (Undirected Graphs) 각 정점을 연결하는 ..

개요 기본적인 자료구조는 객체를 모아 놓은 것입니다. 예를들어 집합(set)은 값의 모음이고, 관련된 연산으로는 값을 추가하고, 삭제하고, 집합내부에 값이 있는지 조사하는 것이 있을 수 있습니다. 이러한 객체를 모아 놓은 기본 자료구조로는 큐와 스택이 있습니다. 이 둘은 간단하면서 널리 사용되기 때문에 유용합니다. 이 두 자료구조를 C 언어를 이용하여 구현해보도록 하겠습니다. 스택 LIFO (Last In First Out) 정책에 기반한 자료구조입니다. 출입구를 한쪽으로만 제한한 자료구조입니다. 가장 마지막에 자료구조로 삽입된 아이템이 가장 먼저 밖으로 빠져나오는 구조입니다. 실생활에서는 먼저 엘리베이터에 탑승한 사람이 엘리베이터의 안쪽으로 밀려 들어가기 때문에 가장 나중에 내리게 되는 현상을 통해서 ..