grace's dev_note

개념 및 용어 그래프 G는 하나 이상의 정점(혹은 노드)을 포함하는 집합 V와 두 정점의 쌍으로 구성되는 간선을 포함하는 집합 E의 순서쌍으로 정의함 (G = (V, E)) 간선(인접한다) 두 정점을 연결하는 선 두 정점 쌍으로 나타냄 무방향 그래프 간선의 방향성이 없음 정점 쌍이 순서를 나타낼 필요가 없으므로 {v1, v2}로 나타냄 n개의 정점을 갖을 때 최대 간선 개수: n(n-1)/2 차수: 정점에 연결된 간선들의 개수 방향 그래프 간선의 방향성이 있음 순서쌍 (v1, v2) n개의 정점을 갖을 때 최대 간선 개수: n(n-1) 진입 차수: 주어진 정점으로 향한 간선의 개수 진출 차수: 주어진 정점에서 시작하는 간선의 개수 정점의 차수: 진출 차수와 진입 차수의 합 다중 그래프: 두 정점을 잇는 ..

m원 탐색 트리 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리 → 같은 수의 노드를 갖는 이진 탐색 트리보다 낮은 높이의 m원 트리 이진 탐색 트리의 확장된 형태임 탐색 트리의 제한을 따르면서, 2개 이상 ~ m개 이하의 자식 노드를 가질 수 있음 노드의 구조 struct Mnode { int n; struct Rectype { struct Mnode * ptr, int key; struct Rectype *addr, } keyptrs[n-1]; struct Mnode *keyptrn; } 탐색 연산 일반적으로 노드의 가지 개수가 많을수록(서브 트리가 많을수록) 최대 탐색 시간이 짧아짐(트리의 깊이가 얕으므로 더 빨리 찾을 수 있음) struct Mnode *nodeptr; struct Re..

BS(Binary Search, 이진 탐색 트리) 특정 데이터의 효과적인 검색을 위해 제한점을 가지는 이진 트리 특정 데이터의 검색과 노드의 삽입, 삭제 처리에 효과적인 이진 트리 트리를 구성할 때, 데이터의 탐색을 고려하여 구성하므로 탐색에 최적화된 이진 트리 키: 탐색, 삽입, 삭제 연산에서 비교의 대상이 되며, 이진 트리 노드에서 데이터를 대표하는 혹은 노드를 특정할 수 있는 값 노드 v_i의 키를 k_i라 할 때, 각 노드 v_i가 다음을 만족하는 이진 트리 v_i의 왼쪽 서브 트리에 있는 모든 노드의 키 값은 v_i의 키 값보다 작다 v_i의 오른쪽 서브 트리에 있는 모든 노드의 키 값은 v_i의 키 값보다 크다 중위순회를 통해 같은 순서 데이터를 만들어 낼 수 있는 다양한 BS 트리 BS 트리..

선택 트리 합병 정렬 차례로 정렬된 k개의 데이터 목록을 순서를 유지하는 하나의 데이터 리스트로 만드는 과정 일반적으로 데이터 목록이 k개인 경우, k-1번 비교를 통해 데이터 목록에서 가장 작은 값이나 가장 큰 값을 결정할 수 있음 선택 트리를 이용하여 비교 횟수를 줄일 수 있음 승자 트리 각 노드가 두 자식 노드의 작은 값을 갖는 완전 이진 트리 작은 값이 승자가 되어 올라가는 토너먼트 경기와 유사 트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 함 결과적으로 루트의 값이 트리에서 가장 작은 값이 됨 첫번째 단계에서의 비교 횟수를 줄이지는 못했지만, 두번째 비교단계부터는 비교 횟수가 감소됨 재구성 과정에서 빈 리스트가 생기면 큰 값(∞)을 넣어줌 패자 트리 각 노드가 두 자식 노드 중에서 ..

우선순위 큐 큐: 먼저 들어간 데이터가 먼저 삭제되는 자료구조 우선순위 큐: 대기 리스트에서 우선순위 높은 사람이 먼저 서비스를 받는 구조 데이터 삭제(Delete_q())와 삽입(Add_q(3)): Delete_q()에 의해 큐의 front에 있던 ‘1’이 삭제되면서, 나머지 데이터 중에서 가장 작은 값인 ‘2’가 다음 삭제 위치 즉, front가 가리키는 위치로 이동됨 우선순위 큐의 작동 방식 삭제 명령이 실행되면 저장된 데이터 중에서 가장 작은 값(가장 큰 값)이 삭제된다. 나머지 데이터들은 어떤 순서로 저장되든 문제가 되지 않는다. 힙 추상 자료형 힙 피라미드 모양으로 쌓아 올린 더미 무엇인가를 쌓아놓은 더미이고 항상 가장 위에 있는 것을 우선 꺼내는 구조 부모-자식 노드 사이에서(부분적으로) 정..

트리의 구성 노드: 트리의 항목/트리에 저장되는 데이터의 묶음 부모노드-자식노드: 상하 계층구조가 있고 직접적으로 연결된 노드들로서 상위계층의 부모 노드와 하위계층의 자식 노드를 의미함 루트 노드: 트리의 최상위 노드(부모가 없는 노드) 서브트리: 부모 노드를 삭제하면 생기는 트리들 잎 노드: 트리의 맨 끝(바닥)에 있으면서, 자신의 서브트리를 갖지 않는 노드 진입/진출 차수 루트 노드: 진입 차수 = 0 루트를 제외한 모든 노드의 진입 차수: 1 잎 노드: 진출 차수 = 0 내부 노드와 형제 내부 노드: 루트도 아니고 잎도 아닌 노드 형제: 같은 부모를 갖는 노드들 트리의 레벨 노드의 레벨: 루트로부터 그 노드까지 이어진 선(경로)의 길이 트리의 깊이: 트리의 레벨에서 가장 큰 값에 1을 더한 것 추상..

리스트의 개념 리스트 물품이나 사람의 이름 따위를 일정한 순서로 적어 놓은 것 어떤 정의에 의해서 결정된 논리적인 순서의 나열 리스트의 순서는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되고 어떤 정의에 의해서 결정된 논리적인 순서, 혹은 리스트에 나타나는 원소들 간의 의미적인 순서를 의미함 배열 인덱스로 표현되는 추상적 순서가 원소의 메모리 공간(메인 메모리, DDR)의 물리적인 위치와 일치함 배열의 순서는 메모리 공간에서 저장되는 원소값의 물리적 순서 배열을 이용한 리스트의 구현 배열의 확장 초기 배열 선언에서 충분히 크게 하면 어느 정도는 배열의 추가 확장을 피할 수 있겠지만(메모리 낭비), 원소를 리스트의 중간에 삽입하기 위해서는 리스트의 원소값을 하나씩 뒤로 밀어야 하는 상..

큐 큐의 개념 한쪽에서는 삽입연산만 발생 가능하고, 다른 한쪽에서는 삭제연산만 발생 가능한 양쪽이 모두 터진 관 한쪽에서는 삽입연산: 서비스를 받기 위한 기다림 다른 한쪽에서는 삭제연산: 서비스를 받는 중 선입 선출(First-In-First_out, FIFO) 또는 선착 순 서브(First-Come-First-Serve, FCFS) 알고리즘과 함께 사용됨 큐의 추상 자료형 큐 객체: 0개 이상의 원소를 갖는 유한 순서 리스트 연산: queue∈Queue, item∈element, maxQueueSize∈positive integer인 모든 queue, item, maxQueueSize에 대하여 다음과 같은 연산이 정의됩니다. (queue는 0개 이상의 원소를 갖는 큐, item은 큐에 삽입되는 원소, ..

스택의 개념 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 자료구조 가장 먼저 입력된 자료가 가장 나중에 출력되는 관계를 표현함 관계를 표현하기 위해서 연산이 필요하며, 객체에 대한 정의와 연산이 모여서 순서가 기억되는 스택의 추상 자료형이 완성됨 0개 이상의 원소를 갖는 유한 순서 리스트 push(add)와 pop(delete) 연산이 한 곳에서 발생되는 자료구조 스택의 추상 자료형 스택 객체: 0개 이상의 원소를 갖는 유한 순서 리스트 CreateStack 연산 stack ∈ Stack, item ∈ element, maxStackSize ∈ positive integer인 모든 stack, item, maxkStackSize에 대하여 다음과 같은 연산이 정의됩니다. (stack은 0개 이상..

배열의 정의 배열의 정의 일정한 차례나 간격에 따라 벌여 놓음(사전적 정의) ‘차례’(순서)와 관련된 기본적인 자료구조 원소의 메모리 공간(메인 메모리, DDR)의 물리적인 위치를 ‘순서’적으로 결정하는 특징 배열의 순서는 메모리 공간에서 저장되는 ‘원소값의 물리적 순서’ 인덱스와 원소값()의 쌍으로 구성된 집합 배열의 의미 ‘호수’(인덱스)로 표현되는 순서를 갖는 ‘아파트’ → 호수: 인덱스 / 원소값: 거주민 원소들이 모두 같은 자료형과 같은 크기의 기억 공간을 가짐 배열의 인덱스값을 이용해서 원소값에 접근하기 때문에 직접 접근이 가능함 배열의 인덱스값: 추상화된 값 = 컴퓨터의 내부구조나 메모리 주소와 무관하게 개발자에게 개념적으로 정의됨 메모리 주소값은 실제 메모리의 물리적인 위치값 배열의(추상화..