프로그래밍 언어들/알고리즘 썸네일형 리스트형 C언어 큐(Queues in C) - 배열로 구현(The implementation with the array) C언어 큐(Queues in C) - 배열로 구현(The implementation with the array) - FIFO(First In First Out) 정책을 사용한다. - 먼저 삽입된 데이터가 먼저 나온다. - 선형 큐의 경우 큐의 포화상태와 빈(empty)상태를 구분하지 못한다. ( 이를 해결하기 위해 환형 큐가 고안 되었다. ) - 삽입 명령을 ENQUEUE라고 부른다. - 삭제 명령을 DEQUEUE라고 부른다. 1. 동작 원리 (1) 삽입할 위치를 가리키는 head와 내보낼 위치를 가르키는 tail의 위치를 초기화 한다. (2) 삽입 명령 시 head가 가르키는 곳에 큐의 위치에 데이터를 입력하고 head의 값을 증가시킨다. (3 - 1) 삭제 명령 시 큐가 비어있는지 확인한다. (3 -.. 더보기 C언어 스택(Stacks in C) - 연결리스트로 구현(The implementation with the linked lists) C언어 스택(Stacks in C) - 연결리스트로 구현(The implementation with the linked lists) - 스택에 관한 내용은 이전 글 참고 1. 동작 원리 (1-1) push 명령 시 새로운 노드를 생성한 후 Top 포인터가 이를 가르키게 한다. ( Top 포인터는 항상 가장 최근 노드(가장 위)를 가르킨다. ) (1-2) 각 노드들은 자신의 이전 노드를 가르킨다. ( pop 명령 시 삭제되는 노드의 이전 노드를 가르키기 위함 ) (2-1) pop 명령 시 Top 포인터가 가르키고 있는 노드의 값을 반환하고, Top 포인터는 이전 노드를 가르킨다. (2-2) 값을 반환한 노드는 삭제한다. ( 메모리를 반환한다. ) 2. 함수 설명 int stack_empty( STACK *.. 더보기 C언어 스택(Stacks in C) - 배열로 구현(The implementation with the array) C언어 스택(Stacks in C) - 배열로 구현(The implementation with the array) - LIFO(Last In First Out) 정책을 수행한다. - 가장 최근에 들어간 데이터가 가장 먼저 나온다. - 삽입 명령을 스택에서는 PUSH 라고 불리운다. - 삭제 명령은 주로 POP이라고 불리운다. 1. 동작원리 (1) 새로운 데이터를 PUSH하면 TOP은 해당 데이터를 가르킨다. (2) 데이터를 POP하면 TOP이 가르키고 있는 데이터를 반환하고, TOP은 이전 데이터를 가르킨다. [ Fig. 1 ] process of the stack, site : introduction to algorithms 3/E 2. 함수 설명 stack_empty( struct stack) : 스.. 더보기 최소신장트리(Minimum Spanning Trees)프림(prim) 알고리즘 최소신장트리(Minimum Spanning Trees)프림(prim) 알고리즘 프림 알고리즘(Prim's algorithm) - 프림 알고리즘은 다익스트라(Dijkstra) 알고리즘과 유사하게 동작한다. - 알고리즘이 동작되는 동안에, 트리에 연결되지 않은 정점들은 큐에 배정되어 있다. - 각 정점들은 key 값을 가지고, 인접한 정점 중 최소 비용으로 이동가능한 정점을 선택한다. 1. 동작 원리 (1) 각 정점들의 key 값과, 다른 정점을 가르키는(pre) 값을 초기화한다. (2) 모든 정점들을 큐에 배정하고, 시작 위치의 key값을 0으로 초기화한다. (3) 큐에 배정된 정점 중, key 값이 가장 작은 정점을 꺼낸다. (4) 꺼내온 정점을 기준으로, 인접한 정점 중에 큐에 아직 배정되어 있고(=트.. 더보기 최소신장트리(Minimum Spanning Trees) 크루스칼(Kruskal) 알고리즘 최소신장트리(Minimum Spanning Trees) 크루스칼(Kruskal) 알고리즘 신장트리란? - 사이클을 형성하지 않고 그래프의 모든 정점이 간선으로 연결되어 있는 것 최소 신장 트리(MST : Minimum Spanning Trees)란? - 최소한의 비용(가중치)로 신장 트리를 형성하는 것 크루스칼(Kruskal) 알고리즘 - 최소 신장 트리를 형성하기 위한 알고리즘 - Disjoint-set을 사용한다. * 대표 원소(representitive)를 통해 각 set을 분별하는 방식. * 이에 대해서는 차 후에 자세하게 다루겠다. 1. 동작원리 (1) 모든 정점들(vertices)을 독립적인 원소(set)로 만든다. (2) 모든 선분들(edges)을 가중치를 기준으로 정렬한다. (3) 가중치가.. 더보기 벨먼-포드 알고리즘(Bellman-Ford algorithm) 벨먼-포드 알고리즘(Bellman-Ford algorithm) - 가중치 그래프에서 시작점에서 목표점까지의 최단 경로를 찾는 알고리즘이다. - 다익스트라 알고리즘과 흡사하지만, 다익스트라보다 조금 더 느리다. + 음수 가중치를 판단할 수 없는 다익스트라에 비해 조금 더 유연하다. 동작 원리 (1) 시작점을 제외한 모든 점의 거리를 무한으로 초기화한다. ( 시작점의 거리는 0 ) (2) 모든 점의 수 만큼 반복적으로 가중치가 있는 모든 선분을 검사한다. (3) 갱신 가능한 거리가 있으면 최단거리를 갱신한다. (4) 음수 싸이클이 있는지 검사하고, 검사 결과를 반환한다. [ Fig. 1 ] process of bellmanford. cite : introduction to algorithm 3/E 함수 설명.. 더보기 A* (A star) 알고리즘 A* (A star) 알고리즘 - 주어진 출발점에서 목표점까지 가는 최단 경로를 찾아내는 그래프 알고리즘 중 하나이다. - 적절한 휴리스틱 추정값 h(x) 을 가지고 이 알고리즘을 사용하면 최적의 해를 얻을 수 있다. - A* 알고리즘은 최적의 경로를 탐색하기 위해, 각각의 지점에서 다음과 같은 함수 f(n)을 이용하여 가중치를 고려한다. f(n) = g(n) + h(n) g(n) : 출발점으로부터 현재 위치까지의 경로 가중치 h(n) : 현재 위치로부터 목표점까지의 추정 경로 가중치 1. 동작 원리 (1) 현재 위치(시작점)에서 이동할 수 있는 지점을 열린 목록(open list)에 추가한다. (2) 현재 위치를 다시 확인할 필요가 없는 닫힌 목록(closed list)에 추가합니다. (3) 열린 목록.. 더보기 다익스트라(dijkstra) 알고리즘 다익스트라(Dijkstra) - 가중치 그래프에 대해 최단거리 문제를 해결하기 위한 알고리즘 - 변 경감(edge relaxaxtion) 연산을 바탕으로 한다. - 그래프의 가중치가 음수가 아니라고 가정한다. - Extract-Min(Q) 함수를 단순한 선형 탐색으로 구현하면 O(n²)의 복잡도를 가진다. - 이진 힙 또는 피보나치 힙을 통해 구현하면 O(m+nlogn) 시간까지 개선할 수 있다. 1. 동작 원리 - 각 꼭짓점 v에 대해 시작점(s)에서 끝점까지의 최단 거리 d[v]를 갱신하며 수행한다. (1) 시작점(s)의 거리를 0으로 하고, 다른 모든 꼭짓점들의 거리는 INF(무한)으로 한다. (2) Q에 나머지 모든 꼭짓점들을 배정한다. (3) Q가 비어있으면 수행을 끝낸다.(= 모든 꼭짓점을 방.. 더보기 너비우선탐색(BFS : Breadth First Search) 너비우선탐색(BFS : Breadth First Search) - 자노드를 탐색하기 전 같은 위치의 노드를 먼저 탐색하는 방식이다. - BFS의 시간 복잡도 및 공간 복잡도는 O(nⁿ)이다. ( 주어진 모든 노드를 저장하기 때문 ) - 무한히 깊은 트리에 효과적이다. [ Fig. 1] BFS 탐색 순서 1. 동작 원리 (1) 시작 노드를 큐(Queue)에 삽입한다. (2) 큐가 비어있다면 수행을 중단한다. (3) 큐에서 노드를 꺼낸다. (4) 꺼내온 노드를 기준으로 인접한 정점 중 탐색하지 않은 노드를 탐색한다. (5) 탐색한 노드를 순차적으로 큐에 삽입한다. (6) (2 - 5) 과정을 반복한다. 2. 함수 구현 #include #define MAX 6 #define VISITED 2 #define A.. 더보기 깊이우선탐색(DFS : Depth First Search) 깊이우선탐색(DFS : Depth First Search) - 해가 존재할 가능성이 있으면 계속해서 같은 방향으로 탐색하는 알고리즘이다. - 스택 구조( 재귀 )를 이용한다. - 진행 중이던 방향이 막혀 있을 경우 이전으로 되돌아가서 위의 과정을 반복한다. - 모든 곳을 방문했을 때 탐색을 종료한다. - 넓은 트리에 효과적이나 목표 노드가 없는 경로에 깊이 빠질 수 있는 단점이 있다. [ Fig. 1 ] DFS 탐색 순서 1. 동작 원리 (1) 현재(초기) 노드를 방문으로 표시한다. (2) 현재 노드와 인접한 노드 중 방문하지 않은 노드가 있는지 탐색한다. (3) (2)의 조건에 맞는 노드를 탐색하면, 해당 노드를 중심으로 (1 - 2) 과정(재귀)을 반복한다. (4) 방문하지 않은 노드가 없을 경우 종.. 더보기 이전 1 2 3 다음
