💻 알고리즘/이론

kruskal 알고리즘 구현(c언어) #include #include typedef struct Edge { char v1, v2; int weight; struct Edge* next; }Edge; typedef struct IncidentEdge { char aName; Edge* e; struct IncidentEdge* next; }IncidentEdge; typedef struct Vertex { char vName; IncidentEdge* iHead; struct Vertex* next; }Vertex; typedef struct { Vertex* vHead; Edge* eHead; int eCount, vCount; }Graph; void init(Graph* G) { G->vHead = ..

동적 계획 알고리즘(DP) 주어진 문제를 부분 문제로 나누어서 푼 다음, 그 결과로 주어진 문제를 푸는 방법 부분 문제의 정보를 저장->시공간적 효율 증가 memoization 활용 최적 부분 구조(기본 문제의 최적해가 부분 문제의 최적해를 포함) DP 적용 여부 판단 방법 1.문제를 같은 형태의 하위 구조로 나눌 수 있는가 2.하위 문제의 계산이 반복되는가 (최적화, 최대화, 최소화, 어떡 작업의 경우의 수를 구하는 문제인가 *애매한 경우에 참고할 수 있는 대표적인 DP 문제 유형) DP 적용 과정 1. 점화식 / 재귀 과정 정의 - 문제를 Top-Down(하향식/재귀) 으로 정의한다 - 문제 풀이에 필요한 기본적인 문제의 하위 부분 값을 초기화 - 종료 조건 추가 2. memoization 적용 3...

그리디 알고리즘 가장 직관적인 알고리즘 설계 패러다임으로 최적화 문제(가능한 해들 중 가장 좋은(최대/최소) 해를 찾는 문제)를 해결한다. 모든 선택지를 고려하지 않고, 각 단계마다 가장 좋은 방법만을 선택 (근시안적 태도) -> 근시안적인 선택으로 부분 문제의 최적해를 찾고, 이들을 모아서(축적하여) 문제의 최적해를 얻는다. 근시안적이기 때문에 많은 경우 최적의 정답을 찾아주지 못한다. 그렇기에 정당성 증명이 필수적!(해결 가능한 문제가 제한적) -탐욕적 선택 속성 : 탐욕적으로 선택하더라도 문제의 최적해를 구할 수 있다 -최적 부분 구조 : 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있다. 그리디의 사용 1. 동전 거스름돈 문제 거스름돈 액수에 대한 최소 동전 수를 출력하는 문제 -거스름돈..

최근접 점의 쌍(closest pair) 문제는 2차원 평면상의 n개의 점이 입력으로 주어질 때 거리가 가장 가까운 한 쌍의 점(거리)을 찾는 문제이다. 최근접 점의 쌍을 찾는 방법으로는 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점의 쌍을 찾는 방법 (BruteForce) - O(n^2) n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고 부분해 중 짧은 쌍을 찾는 방법 (분할정복) 이 있다. 부분해를 취합(정복)하는 과정에서 중간 영역 사이의 점에서 더 근접한 점의 쌍이 존재할 수 있다. 중간 영역의 점들은 [왼쪽 그룹의 가장 오른쪽 점의 x 좌표에서 부분해를 뺀 값과 오른쪽 그룹의 가장 왼쪽 점의 x좌표에서 부분해를 더한 값 사이의 x 좌표 값을 가진..