studioesso

노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 것. 간선의 방향이 있는 그래프 -> 방향 그래프 간선의 방향이 없는 그래프 -> 무방향 그래프 모든 정점이 간에 경로가 존재하는 그래프 -> 연결 그래프 사이클이 있는 그래프 -> 순환 그래프 사이클이 없는 그래프 -> 비순환 그래프 간선에 가중치가 할당된 그래프 -> 가중치 그래프, 네트워크 사이클이 없는 방향 그래프 (자기 자신으로 돌아오는 경로가 없는 그래프) -> DAG (directed acyclic graph) 정점들이 겹치지 않는 두 개의 그룹으로 나눌 때 서로 다른 그룹의 정점들 간에만 간선이 있는 그래프 -> 이분 그래프 코드에서 그래프를 표현하는 방법 1. 인접 리스트 ->한 정점에서 갈 수 있는 다른 정점들을 리스트로 저장 ->무방..

트리 종류 이진트리 : 각 노드가 최대 두 개의 자식을 갖는 트리 이진 탐색 트리 : '모든 왼쪽 자식들

부호 없는 N비트 정수형 변수는 N자리의 이진수로 쓸 수 있다. 각 비트가 표현하는 값은 2^0 ~ 2^N-1까지이고, 이때 2^0를 나타내는 비트를 최하위 비트(least significant bit), 2^N-1을 나타내는 비트를 최상위 비트(most significant bit)라고 한다. 비트 연산 AND : 두 정수를 한 비트씩 비교하면서 두 정수의 해당 비트가 모두 1일 때만(켜져 있을 때만) 결과의 비트를 켠다. ex) 1111 & 1101 => 1101 OR : 두 정수를 한 비트씩 비교하면서 두 비트 중 하나라도 켜져 있을 경우 결과 비트가 켜진다. ex) 1111 | 1101 => 1111 XOR : 두 정수를 한 비트씩 비교하면서 하나는 켜져 있고 하나는 꺼져 있을 경우 결과 비트가 ..

선입 선출(FIFO : First-In First-Out)을 기본으로 하는 자료 구조. 먼저 들어온 데이터가 먼저 나가고, 나중에 들어온 데이터가 나중에 나간다. /* 연결 리스트로 구현된 큐 코드 출처 : C언어로 쉽게 풀어쓴 자료구조 / 생능출판 / 천인국, 공용해, 하상호 지음 */ #include #include typedef int element; typedef struct QueueNode { element item; struct QueueNode *link; } QueueNode; typedef struct { QueueNode *front, *rear; } QueueType; void error(char * message) { fprintf(stderr, "%s\n", message); e..

후입 선출(LIFO : Last-In First-out), 가장 최근에 들어온 데이터가 가장 먼저 나가고 가장 나중에 들어온 데이터가 가장 나중에 나가는 자료 구조 연산 push : 데이터를 넣는다. pop : 데이터를 꺼낸다. peek : 가장 위에 있는 데이터를 반환한다. isEmpty : 스택이 비어있는지 확인한다. 추가 삭제 연산은 상수시간에 가능하나, (연결 리스트로 구현하면 메모리 할당 및 해제 시간이 배열보다 조금 더 걸린다.) 특정 항목에 대한 접근은 상수 시간안에 불가능 하다. /* 연결 리스트로 구현한 스택 코드 출처 : C언어로 쉽게 풀어쓴 자료구조 / 생능출판 / 천인국, 공용해, 하상호 지음 */ #include #include typedef int element; typedef ..

포인터로 다음 노드를 가리켜 차례로 연결된 노드를 표현하는 자료구조. 특징 특정 인덱스를 상수 시간에 접근할 수 없다. 동적으로 공간을 만들어서 추가할 수 있다. 첫 번째 노드를 가리키고 있는 변수를 헤드 포인터라고 한다. 삽입, 삭제가 빠르고 데이터 수정, 조회가 느리다. (삽입, 삭제는 포인터만 바꿔주면 되지만, 조회나 수정은 헤드 포인터에서 해당 노드가 나올 때까지 포인터 연결을 따라가야 한다. 종류 단순 연결 리스트 : 하나의 방향으로만 연결 원형 연결 리스트 : 맨 마지막 노드의 링크 값이 첫 번째 노드를 가리킴 이중 연결 리스트 : 각 노드는 자기 앞에 있는 노드의 링크와 뒤에 있는 노드의 링크를 함께 가지고 있다. 주의점 삭제 연산 후 메모리 반납을 잊지 않는다. 추가, 삭제등 포인터 연산에..

삽입 시간 복잡도 -> O(logn) 삭제 시간 복잡도 -> O(logn) /* 코드 출처 : C언어로 쉽게 풀어쓴 자료구조 / 생능출판 / 천인국, 공용해, 하상호 지음 */ #include #define MAX_ELEMENT 200 typedef struct { int key; } element; typedef struct { element heap[MAX_ELEMENT]; int heap_size; } HeapType; //초기화 함수 init(HeapType *h) { h->heap_size = 0; } //삽입 함수 void insert_max_heap(HeayType *h, element item) { int i; i = ++(h->heap_size); while((i != 1) && (ite..