happy coding

트리 트리(Tree)란 계층적인 구조를 나타내는 자료구조를 의미하고, 부모-자식 관계의 1개 이상의 노드들로 이루어진다. 서브트리와 루트노드가 있다. 사이클이 없는 그래프, 노드(node) : 트리의 구성요소 루트(root) : 부모가 없는 노드 서브트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리 단말 노드(terminal node) : 자식이 없는 노드 비단말 노드(nonterminal node) : 적어도 하나의 자식을 가지는 노드 레벨(level) : 트리의 각 층의 번호 높이(height) : 트리의 최대 레벨 차수(degree) : 노드가 가지고 있는 자식 노드의 개수 이진 트리 이진 트리(binary tree)는 모든 노드가 2개의 서브 트리를 가지고 있는 트리이며 ..

큐란 스택과 마찬가지로 삽입과 삭제의 위치가 제한되어 있는 유한 순서 리스트이다. 큐의 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조이다. > 삽입한 순서대로 원소가 나열되어 가장 먼저 삽입한 원소는 맨 앞에 있다가 가장 먼저 삭제된다. > 선입선출구조 선형 큐 스택이 연탄이면, 큐는 한줄서기 > push. pop : enQueue. deQueue 모든 자료구조는 array(seq structure)와 linked list 로 이루어져 있다. 초기상태(공백 큐)는 front = rear = -1 이다. 삽입된 상태(enQueue(Q,A))에서는 rear가 A를 가리키고, enQueue(Q,B)에서는 rear가 B를 가리키는 상태가 된다. 원소를 삭제할 때(deQueue(Q))는 front를 A..

스택(stack) 논리적 개념으로는 linear list(ordered list) 에서 array와 linked list 가 있다. 이를 통해 stack 또는 queue를 구현한다. 연결리스트는 동적인 자료구조, 순차 접근 방식, O(n), 데이터의 접근과 탐색이 중요할 때 사용한다. 배열은 정적인 자료구조, 임의 접근 방식, O(1), 데이터의 추가와 삭제가 중요할 때 사용한다. 스택은 삽입과 삭제는 O(1)이고, 탐색은 O(n)이다. 큐 또한 같다. 스택이란, 접시를 쌓듯이 같은 크기의 자료를 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 스택에 저장된 원소는 top으로 정한 곳에서만 접근이 가능하다. 여기서, top의 위치에서만 원소를 삽입하므로 먼저 삽입한 원소(가장 최근에 들어온 데이터)는 밑에..

연결 자료구조(Linked Data Structure) 연결 자료구조란, 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조로, 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순가 연결되기 때문에 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다. 또한, 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현하기 때문에 크기 변경이 유연하고 더 효율적으로 메모리를 사용할 수 있다. 여기서 연결리스트란, 리스트를 연결 자료구조로 표현한 구조인데, 연결하는 방식에 따라 단순연결 리스트와 원형 -, 이중 - , 이중 원형 - 이 존재한다. 순차 자료구조의 문제점은 1. 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해 원소들을 이동시키는 추가적인 작업과 시간이 소요된다..

linked list 를 어떻게 c언어로 구현하는지 배열(array)은 구현이 간단하고 빠르지만 크기가 고정되고 중간에 삽입과 삭제가 어렵다. 연결리스트는 각각의 원소가 포인터를 사용하여 다음 번째 원소의 위치를 가리킨다. 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어서 쉽게 추가할 수 있지만,구현이 어렵고 오류가 나기 쉽고 포인터 연산을 많이 하기 때문에 느리다. 하지만 왜 쓰냐면, 배열의 단점을 완벽하게 커버하기 때문이다. 연결 리스트의 구조는 노드 = 데이터 필드 + 링크 필드 로 이루어져 있다. 여기서 첫 번째 노드를 가리키는 포인터를 헤드 포인터라고 한다. 자기 참조 구조체(self-referential structure)란 특별한 구조체로서 구성 멤버 중에 같은 타입의 구조체를 ..

연결리스트에서 사용됨 프로그램이 메모리를 할당받는 방법에는 정적(static)과 동적(dynamic)이 있다. 정적 메모리 할당이란 프로그램이 시작되기 전에 미리 정해진 크기의 메모리를 할당받는 것이다. 메모리의 크기는 프로그램이 시작하기 전에 결정된다. 단점은, 처음에 결정된 크기보다 더 큰 입력이 들어온다면 처리하지 못하고, 더 작은 입력이 들어온다면 남은 메모리 공간은 낭비된다. 동적 메모리란, 실행 도중에 동적으로 메모리를 할당받는 것을 말한다. 사용이 끝나면 시스템에 메모리를 반납해야 하며, 필요한 만큼만 할당받기에 메모리를 매우 효율적으로 사용할 수 있다. malloc()계열의 라이브러리 함수를 사용한다. int *p; p = (int*)malloc(sizeof(int)); void *mall..

이중 포인터(double pointer)란 포인터를 가리키는 포인터이다. 예를 들어 q는 포인터 p를 가리키는 이중 포인터인데 여기서 p는 int형 변수인 i를 가리키는 포인터이다. 여기서 **q 앞의 자료형은 q가 포인팅하는 변수의 타입이다. *(*q) = 200인 경우 뒤쪽에 있는 *연산을 먼저 하고, 괄호 밖의 *연산을 진행한다. 이중 포인터를 사용하는 이유는, 포인터 값을 인수를 통해 받아와야 할 때 포인터의 주소를 통해 받아와야 하기 때문에 사용한다. 여기서 p[1]이 dzf로 바뀌지 않는 이유는 운영체제 에서 막아놨기 때문에(?) > 위의 배열과 포인터를 구분할 줄 알아야 한다. 문자열 배열에서 가장 많이 사용되는 건 포인터 배열이며, 이는 문자열들을 효율적으로 저장할 수 있다. 포인터 배열(..

포인터(pointer)란 주소를 가지고 있는 변수를 의미한다. 이를 이용하여 메모리의 내용에 직접 접근할 수 있다. 변수는 메모리에 저장되고 메모리는 바이트 단위로 접근이 가능하다. 따라서 변수의 크기에 따라 차지하는 메모리 공간이 달라진다. 예를 들어 char형 변수는 1byte, int형 변수는 4byte. 여기서 변수의 주소를 계산하는 연산자는 &이다. 예시로, 변수 i의 주소는 &i 라고 말할 수 있다. int i = 10;// 정수형 변수 i 선언한다. int *p = &i;// 변수 i의 주소가 포인터 p로 대입된다. short birthday; short *ptr;//포인터가 가리키는 대상의 크기가 2바이트인 포인터 변수를 선언 ptr = &birthday;//birthday 변수의 주소를 ..