개발 공부 블로그

연결 리스트란? 필요할 때마다 바구니를 하나씩 마련해서 그곳에 데이터를 저장하고 이들을 배열처럼 서로 연결한다. 라는 개념으로 접근하면 이해하기 쉽다. 바구니 역할이 구조체가 되고, 구조체 변수를 하나씩 동적 할당해서 이들을 연결한다. 그리고 구조체 Node의 변수를 가리켜 '노드'라 한다. 이는 데이터를 담는 바구니보다는 연결이 가능한 개체라는 사실에 중점을 두어 지은 이름이다. 이렇듯 구조체의 정의 하나만 가지고도 연결 리스트의 기본 원리라고 말할 수 있다. 이를 그림으로 표현하면 다음과 같다. 연결 리스트에서의 데이터 삽입 다음 임의 코드로 연결 리스트의 삽입 개념을 잡아보자. Node * head = NULL;// 리스트의 머리를 가리키는 포인터 변수 Node * tail = NULL;// 리스트..

으래 그냥 리스트라고 하면 연결 리스트를 종종 떠올린다. 하지만, 리스트에는 순차 리스트와 연결 리스트가 있다. 순차 리스트는 배열을 기반으로 구현된 리스트이며 연결 리스트는 메모리의 동적 할당을 기반으로 구현된 리스트이다. 하지만 이는 리스트의 구현방법의 차이에서 비롯된 것이기 때문에 이 둘의 ADT가 동일하다고 해서 문제가 될 것은 없다. 물론 각각의 특성의 차이 때문에 ADT에 차이를 두기도 한다. 이는 ADT는 각종 자료구조들의 표준이 아니기 때문이다. 정의하는 사람이나 회사에 따라서, 다시 말해 피룡에 따라서 ADT에도 차이가 난다. 물론 필요에 따라 확장도 가능하다. 하지만 그렇다고 해서 해당 자료구조의 기본 특성을 무시하는 형태로 ADT가 정의되는 것은 아니다. 리스트 ADT 정의를 위해서 ..

트리 순회 일단 트리가 구성되어 있다면, 이 트리를 다양한 방법으로 순회하여 원하는 노드에 접근할 수 잇다. 다양한 순회 방법에 대해 간략히 알아보자. 전위 순회 (preorder traversal) 이 방법은 현재 노드를 먼저 방문하고, 그다음은 현재 노드의 왼쪽 하위 노드를, 마지막으로는 현재 노드의 오른쪽 하위 노드를 재귀적인 방식으로 방문한다. 여기서 '전위(pre)'는 상위 노드를 하위 노드보다 먼저 방문한다는 뜻이다. 전위 순회는 항상 부모 노드를 방문한 다음 왼쪽 자식 노드, 오른쪽 자식 노드를 차례로 방문한다. 이러한 방식의 순호를 루트 노드에서만 수행하는 것이 아니라 루트 노드 아래의 모든 서브 트리에 대해 적용한다. 중위 순회 (in-order traersal) 중위 순회 방법은 왼쪽 ..

하노이 타워 코드 #include void HanoiTowerMove(int num, char from, char by, char to) { if (num == 1)// 이동할 원반의 수가 1개라면 { printf("원반1을 %c에서 %c로 이동 \n", from, to); } else { HanoiTowerMove(num - 1, from, to, by); printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to); HanoiTowerMove(num - 1, by, from, to); } } int main(void) { // 막대 A의 원반 3개를 막대 B를 경유하여 막대 C로 옮기기 HanoiTowerMove(3, 'A', 'B', 'C'); return 0; }

재귀는 자료구조와 알고리즘에 있어서 매우 중요한 요소이고,C언어는 이렇듯 중요한 재귀를 지원하는 언어이다. 재귀함수의 기본적인 이해 재귀함수란 무엇인가?재귀함수란 다음과 같이 함수 내에서 자기 자신을 다시 호출하는 함수를 의미합니다. void Recursive(void){ printf("Recursive call! \n"); Recursive(); // 나 자신을 재호출한다}  위 형태의 함수가 재귀호출이다.그렇다면 재귀 호출은 어떻게 이해해야 할까?  다음 그림과 같은 구조는 매우 단순해 보이지만,그림 내용대로 재귀함수를 이해하는 것이 여간 쉬운 일은 아니다. 그렇다고 위 그림이 재귀호출에 대해서 잘못 설명하고 있다거나 하지는 않는다. 해당 함수는 완료되지 않은 함수를 다시 호출하는 것이 ..

#include int BSearch(int ar[], int len, int target) { int first = 0; int last = len - 1; int mid; int opCount = 0;// 비교연산의 횟수를 기록 while (first

앞선 게시글에서 해시 테이블을 이용하여 필요한 키를 저장하고 검색하는 방법에 대해 알아보았다.그러나 다수의 키가 같은 해시 값을 갖는 충돌 문제가 발생한다는 점도 배웠다.이전 예시에서는 같은 해시 값을 갖는 키에 대해서는기존 키를 덮어써서 가장 최근에 추가된 키만 유지되도록 했었다.그러나 이 방식은 다수의 키글 저장할 수 없는 문제가 있다.그러므로 이러한 문제를 해결하고해시 테이블에 모든 키를 저장할 수 잇는 몇 가지 방법에 대해 알아보자.  해시 테이블에서 충돌 해결 방법1. 체이닝 2. 열린 주소 지정 2-1 .선형 탐색 2-2. 이차함수 탐색3. 뻐구기 해싱   체이닝앞에서는 하나의 해시 값에 대해 하나의 원소만을 저장했다.그래서 특정 해시 값 위치에 이미 원소가 존재한다면새로운 값과 예전 값 중 ..

해시 테이블과 블룸 필터를 알면 좋은 이유 대용량 데이터를 다루는 응용 프로그램에서 발생할 수 있는 룩업 관련 문제에 대해 이해할 수 있다. 주어진 문제에 대해 결정적 룩업 솔루션이 적합한지, 또는 비결정적 룩업 솔루션이 적합한지를 구분할 수 있다. 시나리오에 근거한 효율적인 룩업 솔루션을 구현할 수 있다. C++ STL에서 제공되는 일반적인 솔루션을 구현할 수 있다. 룩업은 특정 원소가 컨테이너에 있는지 확인하거나 또는 컨테이너에서 특정 키에 해당하는 값을 찾는 작업을 의미한다. 데이터 베이스 시스템이나 병원 관리 시스템에 저장된 방대한 자료 중에서 원하는 자료를 찾아 가져오는 작업과 같은 사례에 훨씬 빠르게 수행할 수 있는 효과적인 알고리즘이 필요할 때가 있는데, 해시 테이블과 블룸 필터라는 두 가지..

트리 트리는 노드와 노드 사이를 연결하는 에지를 이용하여 계층을 구성한다. 트리이 계층 구조를 화면에 도식적으로 나타내려면 말 그대로 나무 형태로 나타낼 수 있으며, 이때 에지는 나뭇가지처럼 표현된다. 트리의 중심이 되는 노드를 루트 노드라고 부르고, 이 노드는 보통 가장 맨 위에 나타낸다. 즉, 트리 구조를 그림으로 나타낼 때는 실제 나무와는 정 반대로 뿌리 모양처럼 생기게 된다. 그 외에도 다양한 트리 모양이 있다. 연습 문제 : 조직도 구조 만들기 #include #include struct node { std::string position; node* first; node* second; }; struct org_tree { node* root; // 새로운 트리를 만드는 정적 함수로 트리 구조를..

컨테이너 어댑터 이번 게시글에서는 이미 존재하는 컨테이너를 기반으로 만들어진 컨테이너를 알아볼 것이다. 기존 컨테이너를 감싸는 래퍼를 제공하는 데에는 몇 가지 이유가 있다. 코드에 좀 더 의미를 부여하고 싶거나, 또는 특별한 인터페이스를 새롭게 제공하고 싶은 경우가 대표적이다. 이러한 자료 구조 중의 하나가 스택이다. 스택은 데이터 처리와 보관을 위해 LIFO(Last In First Out, 후입선출) 구조를 사용한다. 기능적인 측면에서 스택은 컨테이너의 한족 끝에서만 데이터를 삽입하거나 삭제할 수 있으며, 한쪽 끝이 아닌 위치에 있는 데이터는 접근하거나 변경할 수 없다. 벡터나 덱은 이러한 기능을 기본적으로 지원하기 때문에 스택을 구현하기 위한 용도로 사용할 수 있다. 그러나 벡터나 덱을 직접 스택처..