written by yechoi

너비우선탐색(Breadth First Search) 너비를 우선으로 하여 탐색을 수행하는 알고리즘 DFS와 마찬가지로 맹목적으로 전체 노드를 탐색하고자 할 때 사용 큐(Queue) 자료구조에 기초 구현 시 큐 STL(라이브러리)을 사용하면 좋고, 탐색에는 O(N)의 시간이 소요 수행시간은 DFS보다 좋은 편​ 동작원리 탐색 시작 노드를 큐에 삽입하고 방문처리 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드들을 모두 큐에 삽입하고 방문처리 2번의 과정을 더 이상 수행할 수 없을 때까지 반복 ​ ​ 구현 (아래 코드는 방문 순서에 대한 규칙이 없음) #include #include #define INF 99999999 #define MAX_SIZE 1001 ​ typedef struct..

그래프 - 깊이 우선 탐색​ - 깊은 것을 우선적으로 탐색하는 알고리즘 - 전체 노드를 맹목적으로 탐색하고자 할 때 사용 - 스택 자료구조에 기초해 구현이 간단 - 재귀함수로 구현할 경우 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 >=..