written by yechoi

그래프 - 깊이 우선 탐색​ - 깊은 것을 우선적으로 탐색하는 알고리즘 - 전체 노드를 맹목적으로 탐색하고자 할 때 사용 - 스택 자료구조에 기초해 구현이 간단 - 재귀함수로 구현할 경우 O(N) - 빠르게 모든 경우의 수를 탐색하고자 할 때 굿 ​ 알고리즘 탐색 시작 노드를 스택에 삽입하고 방문 처리 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄 2~3번을 더이상 수행할 수 없을 때까지 반복 ​ #include #include #define MAX_SIZE 1001 ​ typedef struct Node { int index; struct Node *next; } Node; ​ Node **a; i..

그래프 - 그래프의 개념과 구현 ​ 사물을 정점(vertex)와 간선(edge)으로 나타내기 위한 도구 두 가지 방식으로 구현 인접행렬(adjacency matrix) : 2차원 배열을 사용하는 방식 인접리스트(adjacency list): 리스트를 사용하는 방식 ​ ​ ​ 무방향 비가중치 그래프와 인접 행렬 무방향 그래프: 모든 간선이 방향성을 가지지 않는 그래프 비가중치 그래프: 모든 간선에 가중치가 없는 그래프 무방향 비가중치 그래프가 주어졌을 때, 연결된 상황을 인접행렬로 출력할 수 있음 모든 정점의 연결 여부를 저장해 O(V^2)의 공간을 요구(공간 효율성 떨어짐) 두 정점이 서로 연결돼 있는지 확인하는 데 O(1)의 시간을 요구 ​ #include ​ int a[1001][1001]; int ..

탐색 - 순차 탐색과 이진 탐색 순차탐색(sequential search) 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색 정렬 유무에 상관 없이 가장 앞에 있는 원소부터 확인 O(N)의 시간 복잡도 int main(void) { int n; char *word; word = malloc(sizeof(char) * 100); scanf("%d %s", &n, word); array = (char **)malloc(sizeof(char *) * n); for (int i = 0; i < n; i++) { array[i] = malloc(sizeof(char) * LENGTH); scanf("%s", array[i]); } for (int i = 0; i < n; i++) { if (!strcmp(a..

우선순위 큐 우선순위를 가진 데이터를 저장하는 큐 우선순위가 높은 데이터가 가장 먼저 나옴 운영체제 작업 스케줄링, 정렬, 네트워킹 관리 등에 적용 전체트리가 최대 힙 구조(max heap, 부모 노드가 자식 노드보다 값이 큰 완전이진트리)를 유지해야 ​ ​ ​ 큐와 우선순위큐의 차이 큐는 선형적 형태 우선순위 큐는 트리 구조로 보는 것이 합리적 완전 이진트리를 이용해 구현 ​ ​ ​ 우선순위 큐의 삽입(push) 삽입 후 루트까지 거슬러 올라가면서 정렬(상향식) logN 시간 소요 ​ typedef struct { int heap[MAX_SIZE]; int count; }priorityQueue; ​ void push(priorityQueue *pq, int data) { if (pq->count >=..

이진트리 최대 2개의 자식을 가질 수 있는 트리 많은 양의 노드를 낮은 높이에서 관리할 수 있다는 점에서 데이터 활용의 효율성이 높아짐 데이터 저장, 탐색 등의 다양한 목적에서 사용 가능 ​ ​ 트리 용어 길이: 출발 노드에서 목적지 노드까지 거쳐야하는 가짓수 깊이: 루트 노드에서 특정 노드까지의 길이 높이: 루트 노드에서 가장 깊은 노드까지의 길이 ​ ​ 트리 종류 포화 이진트리(Full Binary Tree) 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리 ​ ​ 완전 이진트리(Complete Binary Tree) 모든 노드들이 왼쪽 자식부터 차근차근 채워진 노드 ​ ​ 높이 균형트리(Height Balanced Tree) 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이상 차이나지 ..