본문 바로가기

Algorithms135

Maximum flow 알고리즘 Network flow란 각각의 간선에 정해진 용량보다 작은 유량이 주어진 방향그래프를 의미함. Maximum flow란 위 수원지에서 수요지까지 공급할 수 있는 최대 유량을 의미함 #include #define MAX_V 10 const int INF = 987654321; int V; typedef struct { int queueArray[MAX_V]; int front; int rear; }Queue; void push(Queue* q, int item) { if ((q->rear + 1) % MAX_V == q->front) { return; } q->queueArray[q->rear] = item; q->rear = (q->rear + 1) % MAX_V; } void pop(Queue* q).. 2021. 6. 21.
topological sorting 알고리즘 - 유향 그래프의 정점이 간선의 방향을 거스르지 않도록 나열한 것을 의미함 #include #include #define MAX_N 25 #define MAX_M 25 #define CONNECTED 1 #define NOT_CONNECTED 0 #define NOT_UPDATED_YET 0 #define NOT_VISITED -1 #define DUPLICATE -2 int map[MAX_N][MAX_N] = { 0, }; int count[MAX_N] = { 0, }; int test_case, n, m; typedef struct { int queue[MAX_N]; int cur_ptr; int last_ptr; } Queue; void queue_reset(Queue* queue) { queue-.. 2021. 6. 21.
minimum spanning tree 알고리즘 - 네트워크(가중치가 간선에 할당된 그래프)에 있는 모든 정점들을 가장 적은 비용으로 연결하는 트리 - 가공된 데이터를 사용하는 것을 배움 #include int V; int graph[100][100]; int minKey(int* key, unsigned char* mstSet) { int min = 2147483647; int min_index; for (int v = 0; v < V; v++) { if (mstSet[v] == 0 && key[v] < min) { min = key[v]; min_index = v; } } return min_index; } void printMST(int parent[]) { int weightSum = 0; for (int i = 1; i < V; i++) { .. 2021. 6. 21.
Plane Sweeping 알고리즘 - 여러 개의 직사각형이 주어졌을 때, 총 넓이를 구하는 알고리즘 - 모든 지도는 직사각형임 트리는 다음과 같은 방식으로 수정함 1. 직사각형의 세로선 데이터를 받아옴 2. 트리의 세로선에 해당하는 구간의 노드를 구함 3. 세로선의 종류에 따라 다음과 같이 작동 시킴 3-1. 세로선이 시작선일 경우, 해당하는 구간의 노드의 cnt값을 1증가시킴 3-2. 세로선이 끝선일 경우, 해당하는 구간의 노드의 cnt값을 1감소시킴 4. 해당하는 구간의 노드를 포함해 다시 루트노드까지 올라가면서 다음과 같이 작동시킴 4-1. 위치한 노드의 cnt값이 0인 경우, 하위 두 자식 노드의 sum값을 더해 위치한 노드의 sum에 저장시킴 4-2. 위치한 노드의 cnt값이 0보다 큰 경우, 해당하는 y축 구간 크기를 sum에.. 2021. 6. 21.
Floyd-Warshall 알고리즘 - 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘 - 제일 바깥쪽 반복문은 거쳐가는 꼭짓점 - 두 번째 반복문은 출발하는 꼭짓점 - 세 번째 반복문은 도착하는 꼭짓점 N개의 정점과 방향과 가중치 w를 가진 M개의 간선으로 이루어진 방향 그래프가 주어짐. 이때 모든 정점들의 쌍에 대해 A에서 시작하여 B로 도착하는 최단 거리를 구하시오 #include #define INFINITY 999999 int weight[101][101]; int result[101][101]; void floyd(int n) { int i, j, k; for (k = 0; k < n; k++) { for (i = 0; i < n; i++) { if (k == 0) { for (j = 0; j < n; j++).. 2021. 6. 18.
parametric search 알고리즘 - 해를 바로 구해내는 것이 아니고, 임의의 값을 던지고 맞는지 확인해가며 해를 구하는 방법 - 길이가 다른 K개의 리본, N개의 리본재료를 만드려 함. 리본 재료의 최대 길이를 구하시오 #include #define MAX_RIBBON 100 int K; int N; int low, high, mid, numRibbonTape, max; int sizeRibbonTape[MAX_RIBBON]; void search() { mid = low + (high - low) / 2; numRibbonTape = 0; for (int i = 0; i = N) { low = mi.. 2021. 6. 18.
알고리즘 문제 해결 전략 1권 10.탐욕법 10.1 도입 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없음. 그러나 모든 선택지를 고려해 보고 그 중 전체 답이 가장 좋은 것을 찾는 두 방법과는 달리, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택함. 탐욕법은 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않습니다. 1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만날 경우, 동적 계획법보다 수행 시간이 훨씬 빠름 2. 최적해를 찾기 너무 어렵다면 최적해 대신 적당히 괜찮은 답을 찾는 것으로 타협할 수 있음 가끔 근사해를 구하는 문제가 주어졌다 해도 탐욕적 알고리즘보다 11장에서 다루는 조합 .. 2021. 5. 14.
알고리즘 문제 해결 8장 그리디(Greedy) 현재의 상태에서 특정한 값을 기준으로 가장 좋은 것을 선택해 나가는 방법 그리디 알고리즘으로 문제를 해결하기 위해서는 어떠한 반례도 없이 항상 최적의 결과를 얻을 수 있음이 입증되어야 함 1. 현재의 상태에서 가장 좋은 것을 선택하는 것이므로 그 선택의 기준이 되는 것을 정해야 한다. 따라서 여러 가지 선택 기준 중에서 반례가 없는 기준을 찾아야 함 2. 어떤 값을 기준으로 했을 때 반례가 없다는 것이 입증이 되면 그 기준값을 기준으로 정렬하는 것이 필수임 3. 정렬이 되었다면 처음부터 차례대로 선택이 가능한 것을 모두 선택해 나가면 됨 2021. 5. 14.
알고리즘 문제 해결 전략 1권 4.6 수행 시간 어림짐작하기 프로그램의 동작 속도에 영향을 끼치는 요소는 입력의 크기와 시간 복잡도를 제외하고도 엄청나게 많음. 1억이라는 기준은 가능한 한 보수적으로 정한 것임 4.7 계산 복잡도 클래스 : P, NP, NP-완비 일반적으로 다항 시간 알고리즘이나 그보다 빠른 알고리즘들을 빠르다고 말합니다 P문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합을 계산 복잡도 클래스라고 부릅니다. 다항 시간 알고리즘이 존재하는 문제와 존재하지 않는 문제로 문제들을 구분하기란 어렵습니다. 주어진 배열을 비교 정렬하는 문제와 최소치를 찾는 문제의 난이도를 비교하면, 정렬 문제는 최소치 문제 이상으로 어렵다고 말할 수 있습니다. NP문제란 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 의미합니다. 이런 속성을 갖.. 2021. 5. 14.

티스토리툴바