GeniusForCE GeniusForCE

히프(Heap)란?▶ 우선순위 큐를 위해 만들어진 자료구조▶ 히프란 노드들이 저장하고 있는 키들이 다음과 같은 식을 만족하는 완전이진트리 (complete binary tree) 최대 히프(max heap)▶ 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리▶ key(부모 노드) ≥ key(자식 노드) 최소 히프(min heap)▶ 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리▶ key(부모 노드) ≤ key(자식 노드) 히프(heap)의 높이▶ n개의 노드를 가지고 있는 히프의 높이는 logn▶ 히프는 완전 이진 트리 (complete binary tree)▶ 마지막 레벨 h을 제외하고는 각 레벨 i에 2^i-1개의 노드 존재 히프의 구현방법히프는 배열..

우선순위 큐(priority queue)▶ 우선순위를 가진 항목들을 저장하는 큐(queue)▶ FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다.자료구조삭제되는 요소스택가장 최근에 들어온 데이터 (LIFO)큐가장 먼저 들어온 데이터 (FIFO)우선순위 큐가장 우선순위가 높은 데이터 환자 치료의 예시를 들어보자.▶ 큐: 먼저 온 사람을 먼저 치료▶ 스택: 나중에 온 사람을 먼저 치료▶ 우선순위 큐: 위급한 사람을 먼저 치료 우선순위 큐(priority queue)는 가장 일반적인 큐임.스택(stack)이나 FIFO 큐를 우선순위 큐로 구현할 수 있다. 우선순위▶ 시간: 스택, 큐▶ 스택, 큐에서는 시간에 따라 자료구조를 조직화▶ 다른 가치: 우선순위 큐▶ 따라서 우선순위 큐는 스택이나 큐..

해싱(Hashing)이란?▶ 대부분의 탐색 방법들은 키 값 비교로써 탐색하고자 하는 항목에 접근▶ 키 값에 대한 산술적 연산에 의해 테이블의 주소를 계산하여 항목에 접근▶ 해싱은 물건을 정리하는 것과 같다. 해시 테이블(Hash Table)▶ 키 값의 연산에 의해 직접 접근이 가능한 구조  해시 함수(Hash Function)▶ 탐색키를 입력받아 해시 주소(Hash Address) 생성▶ 이 해시 주소가 배열로 구현된 해시 테이블(Hash Table)의 인덱스 해시 테이블의 구조 해시 테이블 ht▶ M개의 버켓(bucket)으로 구성된 테이블▶ ht[0], ht[1], ..., ht[M-1]의 원소를 가짐▶ 하나의 버켓에 s개의 슬롯(slot) 가능 충돌(collision)▶ 서로 다른 두 개의 탐색키 ..

이진 트리(binary tree) 연산 1) 노드 개수 구하기 ▶ 탐색 트리 안의 노드의 개수를 계산▶ 각각의 서브 트리에 대하여 순환 호출한 다음, 반환되는 값에 1을 더하여 반환 int get_node_count(TreeNode *node) { int count = 0; if (node != NULL) { count = 1 + get_node_count(node->left) + get_node_count(node->right); return count; }} 2) 이진 트리 높이 구하기 ▶ 서브트리에 대하여 순환 호출하고 서브 트리들의 반환값 중에서 최대값을 구하여 반환int get_height(TreeNode *node..

트리란?▶ 계층적인 구조를 나타내는 자료구조▶ 리스트, 스택, 큐 등은 선형 구조이다.▶ 트리는 부모-자식 관계의 노드들로 이루어진다.▶ 응용 분야:1) 계층적인 조직 표현2) 컴퓨터 디스크의 디렉토리 구조3) 인공지능에서의 결정 트리 (Decision Tree) ex) 회사의 조직 ex) 파일 디렉토리 구조 ex) 결정 트리 (Decision Tree)예시 - 골프에 대한 결정 트리 이처럼, 계층적인 구조를 표시할 때 사용되는 자료구조가 트리이다. 트리에 대해 자세히 공부하려면 트리의 용어부터 알고 가야한다. 트리의 용어▶ 노드(node): 트리의 구성요소▶ 루트(root): 부모가 없는 노드▶ 서브트리(subtree): 하나의 노드와 그 노드들의 자손들로 이루어진 트리 말로만 이해하려고 하면 어려우니..

원형 연결 리스트▶ 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트▶ 한 노드에서 다른 모든 노드로의 접근이 가능 ▶ 보통 헤드 포인터가 마지막 노드를 가리키게끔 구성하면 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 단순 연결 리스트에 비하여 용이 리스트의 처음에 삽입▶ plast: 리스트의 헤드 포인터의 포인터▶ new_node: 삽입될 노드  리스트의 끝에 삽입▶ plast: 리스트의 헤드 포인터의 포인터▶ new_node: 삽입될 노드 헤드노드(head node)▶ 데이터를 가지지 않고 단지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드▶ 삽입 및 삭제 시, 헤드 포인터의 NULL 여부에 상관없이 프로그램 가능▶ 헤드 포인터와의 구별 필요▶ 공백상태에서는 헤드 노드만 존재 ▶ 원..

리스트(list), 선형 리스트(Linear list)란?▶ 순서를 가진 항목들의 모임 ▶ 집합: 항목간의 순서의 개념이 없음 리스트의 예▶ 요일: (일요일, 월요일, ..., 토요일)▶ 한글 자음의 모임: (ㄱ, ㄴ, ..., ㅎ)▶ 카드: (Ace, 2, 3, ..., King)▶ 핸드폰의 문자 메시지 리스트 리스트의 연산은 무엇이 있을까?▶ 새로운 항목을 리스트의 끝, 처음, 중간에 추가한다.▶ 기존의 항목을 리스트의 임의의 위치에서 삭제한다.▶ 모든 항목을 삭제한다.▶ 기존의 항목을 대치한다.▶ 리스트가 특정한 항목을 가지고 있는지를 살핀다.▶ 리스트의 특정 위치 항목을 반환한다.▶ 리스트 안의 항목 개수를 센다.▶ 리스트가 비었는지, 꽉 찼는지를 체크한다.▶ 리스트 안의 모든 항목을 표시한다.등..

큐(Queue)란?▶ 먼저 들어온 데이터가 먼저 나가는 자료구조 큐의 특징▶ 선입선출(FIFO: First-In First-Out): 가장 먼저 들어온 데이터가 가장 먼저 나감. 편의점 아르바이트나, 다른 아르바이트를 해본 사람들이라면 선입선출이라는 개념을 한 번씩 들어봤을 것이다.유통기한이 가장 적게 남은(가장 매점에 먼저 들어온) 물건이 제일 앞에 위치하는 개념처럼,큐 자료구조에서도 같은 원리가 적용된다. 큐의 구조 ▶ 큐는 전단(front), 후단(rear)의 데이터가 있고, 그 사이에 데이터가 있는 형태이다. 큐 추상데이터 타입(ADT) ▶ 삽입과 삭제는 FIFO 순서를 따른다.▶ 삽입은 큐의 후단에서, 삭제는 전단에서 이루어진다. 큐의 응용▶ 직접적인 응용1) 시뮬레이션의 대기열(공항에서의 비행..