거북목개발자

CircularDoublyLinkedList.h #ifndef CIRCULAR_DOUBLY_LINKEDLIST_H #define CIRCULAR_DOUBLY_LINKEDLIST_H #include #include typedef int ElementType; typedef struct tagNode { ElementType Data; struct tagNode* PrevNode; struct tagNode* NextNode; } Node; //함수 원형 선언 Node* CDLL_CreateNode(ElementType NewData); void CDLL_DestroyNode(Node* Node); void CDLL_AppendNode(Node** Head, Node* NewNode); void CDLL_I..

탐욕 알고리즘 : 동적 계획법과 마찬가지로 최적화 문제의 답을 얻기 위해 사용한다. 각 단계의 부분 문제를 풀 때 근시안적으로 최적해를 구한다고 해서 붙여졌다. -> 항상 최적의 결과를 보장하지는 못한다!!! 동적 계획법은 최적의 해를 구하긴 하지만 탐욕 알고리즘보다는 덜 효율적(대게 더 많은 수행 시간을 요구합니다) 입니다. 반면에 탐욕 알고리즘은 동적 계획법보다 효율적이긴 하지만 동적 계획법처럼 반드시 최적의 해를 구해준다는 보장은 하지 못한다. 최적의 해가 나오기를 바랄뿐이다. 탐욕 알고리즘으로 풀 수 있는 문제는, 동적 계획법처럼 대상 문제가 최적 부분 구조를 갖고 있어야한다. 1) 해 선택 : 현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합에 추가한다. 2)..

동적 계획법 : 동적으로 변화하는 결정을 만드는 방법 1)분할 정복은 문제를 위에서부터 아래로 쪼개지만(Top-Down), 동적 계획법은 제일 작은 부분 문제부터 상위에 있는 문제로 풀어 올라간다(Bottom Up) 2)분할 정복 기법으로 쪼갠 각 단계에 있는 부분 문제들은 그 이전 단계에 있는 문제들의 답에 의존한다. 동적 계획법은 분할 정복과 달리 한번 푼 적이 있는 부분 문제의 답은 다시 푸는일이 없도록 테이블 등에 저장해 놓는다. 동적 프로그래밍으로 알고리즘을 설계할 때 부분 문제의 답을 저장해 놓는 테이블을 빼놓으면 안된다. 이 테이블이 없으면 부분 문제들의 답을 수없이 반복해서 다시 구하는 일이 생길 수도 있기 때문이다. 1) 문제를 부분 문제로 나눈다. 2) 가장 작은 부분 문제부터 해를 구..

분할 정복 알고리즘 : 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 알고리즘 ex) 퀵 정렬 -> 임의의 기준 요소(pivot)을 정하고 기준 요소보다 작은 요소들을 왼편으로, 큰 요소들은 오른편으로 옮긴다. 그 다음에 기준 요소에 의해 나누어진 양 편에 있는 요소들에 대해 왼쪽/오른쪽에 대하여 각각 분할을 수행한다. 그리고 이렇게 분할된 데이터 집합들을 더 이상 분할 할 수 없을 때까지 계속해서 분할한다. 더 이상 분할 할 수 없을 때는 이미 정렬이 끝난 경우 이다. 핵심 : 문제를 잘게 쪼개기 1. 분할(Divide) : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눈다. 2. 정복(Conquer) : 하위 문제가 여전히..

2. Shortest Path : 그래프 내의 한 정점에서 다른 정점으로 이동할 때 가중치 합이 최소값이 되게 만드는 경로를 찾는 알고리즘 - Dijkstra Algorithm : Prim Algorithm과 동작 방식이 상당히 비슷하다. 다만 Prim Algorithm이 단순히 간선의 길이를 이용해 어떤 간선을 먼저 연결할지를 결정하는데 반해, 다익스트라 알고리즘은 '경로의 길이'를 감안해서 간선을 연결한다는 점이 다르다. : 사이클이 없는 방향성 그래프에 한해서만 사용할 수 있다. 1) 각 정점 위에 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 모든 정점 위에 있는 경로의 길이를 무한대로 초기화 합니다. 2) 시작 정점의 경로 길이를 0으로 초기화하고 (시작 정점에서 시작 정점까..

1. Minimum Spanning Tree : 각 간선이 갖고 있는 가중치의 합이 최소가 되는 신장 트리가 바로 최소 신장 트리이다. - Prim Algorithm 1) 그래프와 최소 신장 트리를 준비한다. 이때 최소 신장 트리는 노드가 하나도 없는 상태이다. 2) 그래프에서 임의의 정점을 시작 정점으로 선택하여 최소 신장 트리의 루트 노드로 삽입한다. 3) 최소 신장 트리에 삽입되어 있는 정점들과 이 정점들의 모든 인접 정점 사이에 있는 간선의 가중치를 조사한다. 간선 중에 가장 가중치가 작은 것을 골라 이 간선에 연결되어 있는 인접 정점을 최소 신장 트리에 삽입한다. 단, 새로 삽입되는 정점은 최소 신장 트리에 삽입 되어있는 기준의 노드들과 사이클을 형성해서는 안된다. 4) 3)의 과정을 반복하다가..