CS/알고리즘

알고리즘 - 모든 쌍 최단 경로 문제(All Pairs Shortest Paths)

각 쌍의 점 사이의 최단 경로를 찾는 문제 다익스트라의 최단 경로 알고리즘 - 한 정점에서 모든 정점으로의 최단경로를 구함 - 각 점을 시작점으로 정하여 다익스트라 알고리즘 수행 - 시간 복잡도는 O(n^3) - 가장 적은 비용의 정점을 기준으로 하나씩 선택해 가며 구해냄. 플로이드-워샬(Floyd_Warshall) 알고리즘 - 모든 정점에서 모든 정점으로의 최단 경로를 구함. - 거쳐가는 정점을 기준으로 알고리즘 수행

알고리즘 - 동적 계획 알고리즘(Dynamic Programming)

Dynamic Programming(DP) 동적 계획 알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다. - 입력 크기가 작은 부분 문제들을 해결한 후, 그 해를 이용하여 큰 크기의 부분 문제들을 해결... - 최종적으로 주어진 입력의 문제를 해결 - 작은 부분 문제의 해가 보다 큰 부분 문제를 해결하는데 사용되는 관계가 있다. 각 단계의 부분문제의 답을 기반으로 전체 문제의 답을 구하는 방법

알고리즘 - 작업 스케줄링 알고리즘(JobScheduling)

작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제 대학 수업에서 강의실을 배정하는 문제와 같다. 강의실 = "기계" 강의 = "작업" 주어진 요소 - 작업의 수 - 각 작업의 시작시간과 종료시간 - 작업의 길이 알고리즘 다음과 같은 그리디 알고리즘이 존재한다. - 빠른 시작시간 작업 우선(Earliest start time first)배정 - 빠른 종료시간 작업 우선(Earliest finish time first)배정 - 짧은 작업 우선(Shortest job first)배정 - 긴 작업 우선(Longest job first)배정 위 4가지중 첫 번째 알고리즘을 제외하고 나머지 3가지는 항상 최적해를 찾지 못한다. 빠른 시작시간 작업 우선(Earliest start ..

알고리즘 - 집합 커버 문제(Set Cover)

집합 F에서 선택하는 집합들의 수를 최소화하는 문제 신도시를 계획하는데 있어서 학교 배치의 예) 10개의 마을이 신도시에 만들어질 계획이다. 조건이 만족되어야 한다. 조건 1. 학교는 마을에 위치해야 한다. 조건 2. 등교 거리는 걸어서 15분 이내이어야 한다. 2번 마을에 학교를 만들면 1, 2, 3, 4 ,5 마을이 커버된다. 6번 마을에 학교를 만들면 5, 6, 7, 9, 19 마을이 커버된다. 최소 학교의 수 = 2개 전체 마을의 수 U = {1, 2,3 ,4, 5, 6, 7, 8, 9 ,19} 한 마을에 배치했을때 커버되는 마을의 집합 S1 = {1, 2, 3, 8} S2 = {1, 2, 3, 4, 8} S3 = {1, 2, 3, 4} S4 = {2, 3, 4, 5, 7, 8} S5 = {4, ..

알고리즘 - 부분 배낭 문제(Fractional Knapsack)

문제 n개의 물건이 각 무게와 가치를 가지고 있을 때, 한정된 용량의 배낭에 최대 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제. 물건의 전체를 넣지 못한다면 물건을 부분적으로 담는 것을 허용된다. 해결 방법 단위 무게당 가장 값나가는 물건을 배낭에 넣고 계속해서 그 다음으로 값나가는 물건을 넣는다. 만일 물건을 통째로 배낭에 넣을 수 없으면 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담는다. 수행 과정 배낭의 최대 용량 = 40 단위 무게당 가치로 정렬 물건 가치 무게 단위 그램당 가치 백금 60만원 10g 6만원 금 75만원 15g 5만원 은 10만원 25g 4천원 주석 1만원 10g 1천원 백금을 통째로 담는다. 배낭의 무게 = 10/40 가치 = 60만원 금을 통째로 담는다. 배낭의 ..

알고리즘 - 다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단경로(Shortest Path)탐색 알고리즘이다. 흔히 최소비용으로 선로 또는 파이크 네트워크, 인공위성 GPS 소프트웨어에서 가장 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 이 떄 음의 간선을 포함할 수 없는데 현실 세계엔 음의 간선이 존재하지 않기 때문에 현실 세계에 사용하기 매우 좋은 알고리즘이라고 한다. 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단 거리는 여러개의 최단 거리로 이루어져 있기 떄문이다. 하나의 최단거리를 구할 때 직전까지 구했던 최단거리를 이용한다. 1. 출발 노드를 정한다. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다. 3...

알고리즘 - 프림 알고리즘(Prim Algorithm)

최소 비용 신장 트리를 구하는 알고리즘이다. 크루스칼 알고리즘은 간선을 기준으로 그래프를 생성하여 최소 비용 신장 트리를 구한다. 프림 알고리즘은 임의의 정점을 선택하며 가중치가 적은 노드를 선택해서 연결해주고 가중치를 업데이트 하는 과정을 반복해준다. 크루스칼 알고리즘은 간선을 기준으로 그래프를 구하는 반면 프림 알고리즘은 정점을 기준으로 최소 비용 신장 트리를 구한다. 노드 0을 선택한다. 노드 0을 선택하고 연결된 모든 노드의 거리를 살펴본다. 직접 이어지지 않은 노드의 거리는 inf(무한대)가 된다. 따라서 0과 연결된 1, 2, 3에 각각 4, 6, 5가 할당된다. 그 후 거리가 가장 짧은 노드를 선택한다. 1번 노드의 거리가 4므로 거리가 가장 짧으니 1번 노드가 선택된다. 그 후 1번 노드와..

알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용되는 알고리즘이다. 최소 신장 트리를 만들기 위한 알고리즘이다. 1. 모든 간선들을 오름차순으로 정렬한다. 2. 가중치가 가장 적은 간선을 추가한다. 3. 추가된 간선이 사이클을 만들면 삭제한다. 2~3번의 동작을 반복한다. 시간복잡도: O(m log m)

알고리즘 - 퀵 정렬(Quick Sort)

퀵 정렬은 대표적인 분할 정복 알고리즘이다, 하지만 알고리즘이 수행되는 과정을 살펴보면 정복 후 분할하는 알고리즘이다. 피봇은 항상 요소의 가장 오른쪽 멤버가 되는 퀵정렬 1. 퀵 정렬의 아이디어는 피봇이라는 원소(숫자)를 정하고, 피봇보다 작은 숫자는 왼편으로, 피봇보다 큰 숫자는 오른편에 위치하도록하고, 피봇을 그 사이에 놓는다. 2. 피봇을 기준으로 작은쪽(왼쪽)과, 큰쪽(오른쪽)의 순서는 상관하지 않는다. 3. 피봇의 왼쪽엔 피봇으로 정한 수보다 작은수들만 모여있다. 순서X 4. 피봇 이전의 수를 기준으로 다시 수들을 정렬하고, 5. 피봇의 위치를 그 수들의 사이에 놓는다. 6. 1 ~ 5를 반복한다. 예) 7 2 5 1 3 4 피봇은 4가된다. 4보다 작은 애들을 왼쪽으로 몰아둔다. j가 4보다..

알고리즘 - 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)은 입력 배열 전체에서 최솟값을 선택하여 배열의 0번 원소와 자리를 바꾸고, 다음에는 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여 1번 원소와 자리를 바꾼다. 이런 방식으로 마지막에 2개의 원소중에서 작은 값을 선택하여 자리를 바꿈으로써 오름차순의 정렬을 마친다. 정렬 할 데이터: 15 9 6 27 24 9 8 13 10 1 5 정렬된 데이터 1회전 결과: 1 9 6 27 24 9 8 13 10 15 5 2회전 결과: 1 5 6 27 24 9 8 13 10 15 9 3회전 결과: 1 5 6 27 24 9 8 13 10 15 9 4회전 결과: 1 5 6 8 24 9 27 13 10 15 9 5회전 결과: 1 5 6 8 9 24 27 13 10 15 9 6회전 ..