개발 공부 블로그

#include #include #include #include #include #include #include #include #include using namespace std; bool CheckeSorted(int arr[], int size) { if (arr[0]

static int ListNum = -1; class List { public: List* CurPtr = this; List* BeforePtr = nullptr; List* AfterPtr = nullptr; int Index = 0; int Value = 0; bool IsDummy = false; ~List(); }; // 빈 List 생성 void InitialList(); // 원하는 만큼의 수와 해당 값으로의 초기화된 List 생성 void InitialList(int MaxIndex, int Value); // 부분 삭제 void DeleteIList(int iter, List* InDeleteList); // 전체 삭제 void DeleteAllList(); // 삽입 void Push..

연결 리스트란? 필요할 때마다 바구니를 하나씩 마련해서 그곳에 데이터를 저장하고 이들을 배열처럼 서로 연결한다. 라는 개념으로 접근하면 이해하기 쉽다. 바구니 역할이 구조체가 되고, 구조체 변수를 하나씩 동적 할당해서 이들을 연결한다. 그리고 구조체 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에서 제공되는 일반적인 솔루션을 구현할 수 있다. 룩업은 특정 원소가 컨테이너에 있는지 확인하거나 또는 컨테이너에서 특정 키에 해당하는 값을 찾는 작업을 의미한다. 데이터 베이스 시스템이나 병원 관리 시스템에 저장된 방대한 자료 중에서 원하는 자료를 찾아 가져오는 작업과 같은 사례에 훨씬 빠르게 수행할 수 있는 효과적인 알고리즘이 필요할 때가 있는데, 해시 테이블과 블룸 필터라는 두 가지..