written by yechoi

그래프 - 그래프의 개념과 구현 ​ 사물을 정점(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 >=..

기수 정렬 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘 1의 자리수를 기준으로 오름차순으로 정렬 그 데이터를 다시 10의 자리수를 기준으로 오름차순으로 정렬 ... 반복 정렬하는 법 bucket[10] 에 자리수 별로 count 함. 19이면 bucket[9]++ 이런 식. 이 버켓을 누적함. bucket[i + 1] = bucket[i] + bucket[i + 1] 뒷 숫자부터 버켓에 담긴 인덱스 대로 집어 넣음. 맨 뒷 숫자가 37이고, bucket[7]이 3이라면 세번째 배열(result[2])에 넣는 것. 결과물 배열을 다시 원 배열에 복사 이 과정을 반복 가장 큰 자릿수를 D라고 했을 때 O(DN)의 시간 복잡도 #define MAX 10000 void radixSort(int *a, ..

큐 뒷쪽으로 들어가서 앞쪽으로 나오는 자료구조 먼저 들어간 게 먼저 나옴 스케줄링, 탐색 알고리즘 등에서 다방면으로 활용 기본적인 형태의 자료구조 연결리스트로 큐 구현하기 큐 삽입함수(push) 새 노드를 마지막 노드 뒤에 넣고 새 노드의 next가 rear를 가리키게 typedef struct { int data; struct Node *next; } Node; typedef struct { Node *front; Node *rear; int count; } Queue; void push(Queue *queue, int data) { Node *node = (Node *)malloc(sizeof(Node)); node->data = data; node->next = NULL; if (queue->cou..