파이팅웨이

Dynamic Programming(동적 알고리즘)이란? 최적화 문제를 해결하는 알고리즘 1.입력 크기가 작은 '부분 문제'들을 모두 해결 2.그 해들을 이용하여 보다 '큰 크기의 부분 문제'들을 해결 3.최종적으로 원래 주어진 입력의 문제를 해결. Divide&Conquer(분할 정복 알고리즘) 방식과 구조적으로 유사하지만, 순서는 반대이다. 거기에 더해, 동적 계획 알고리즘은 B와 C의 해를 구하는 데 E와 F의 해 모두를 이용한다. 분할 정복 알고리즘의 경우, D,E,F,G는 각각 더 이상 분할할 수 없는 부분 문제들이다. D와 E의 해를 취합하여 B의 해를 구하고, F와 G의 해를 취합하여 C의 해를 구하고, B와 C의 해를 취합하여 A를 구한다... 동적 계획 알고리즘의 경우, 먼저 최소 단위의..

greedy 알고리즘 일곱 번째 문제 7.Huffman Code -텍스트를 압축할때, 파일에 빈번히 나타나는 문자에는 짧은 이진 코드를 할당하고 드물게 나타나는 문자에는 긴 이진 코드를 할당하는 것이다. -이 때 문자를 표현하기 위해 트리를 이용한다. -방법 1. min-priority queue를 사용하는 방법 1.각 문자 당 노드를 만들고, 그 문자의 빈도수를 노드에 저장 2.n개의 노드의 빈도수에 대해 우선순위 큐 Q를 만든다. while(Q에 있는 노드 수 >=2){ 빈도수가 가장 작은 2개의 노드 (A와 B)를 Q에서 제거. 새 노드 N을 만들고, A와 B를 N의 자식 노드로 만든다. N의 빈도수 = A의 빈도수 +B의 빈도수 노드N을 Q에 삽입한다.} return Q -Time Complexi..

-방법 1)배열의 원소 하나를 피봇(pivot)삼고 기준 2)피봇보다 작은 숫자들은 왼쪽, 피봇보다 큰 숫자들은 오른쪽에 위치하도록 분할 3)분할된 부분문제에 대해서도 위와 동일한 과정을 재귀적으로 수행하여 정렬 +이 때, 피봇은 분할된 왼편이나 오른편 부분에 포함되지 않는다. -Pseudo Code QuickSort(A, left, right) 입력: 배열 A[left]~A[right] 출력: 정렬된 배열 A[left]~A[right] 1. if (left < right) {//배열 A의 가장 왼쪽 원소의 인덱스가 가장 오른쪽 원소의 인덱스보다 작으면, 정렬 수행. 그렇지 않으면 1개의 원소를 정렬하는 경우임. 2. 피봇을 A[left]~A[right] 중에서 선택하고, 피봇을 A[left]와 자리를 ..

greedy 알고리즘의 여섯 번째 문제 6. 작업 스케줄링(Job Scheduling) -작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제. -machine의 수가 무제한이지만 최소로 쓰게 풀어라. -Input : 작업의 수 n개, 각 작업의 시작 시간과 종료시간(길이) -각자 시작 시간과 마치는 시간이 다른 강의자들을 어떻게 강의실에 배치시킬 것인가? ex) Task=(t1=[7,8],t2=[3,7],t3=[1,5],t4=[5,9],t5=[0,2],t7=[1,6]) 단, [s,f]에서 s는 작업의 시작 시간, f는 작업의 종료 시간 -방법 1.시작 시간의 오름차순으로 정렬한다. L={[0,2],[1,6],[1,5],[3,7],[5,9],[6,8],[7,8]} 2.가장..

Greedy 알고리즘의 네 번째 문제 4.부분 배낭 문제 -n개의 물건이 있고, 각 물건은 무게와 가치를 가지고 있다. 배낭을 한정된 무게의 물건들을 담을 수 있을 때, 최대의 가치를 갖도록 배낭에 물건을 넣어라. -배낭 문제의 종류 (1) 0-1 배낭 문제. 물건을 통째로 넣어야 한다. 이는 greedy알고리즘으로는 풀 수 없다. (2) 부분 배낭 문제. 물건을 부분적으로 잘라서 담는 것을 허용한다. greedy 알고리즘으로 해결 가능하다. -방법 단위 무게 당 가장 비싼 물건을 배낭에 넣고, 그 다음으로 값 나가는 물건을 넣음. 그러다 값나가는 물건을 통째로 배낭에 넣을 수 없게 되면, 배낭에 넣을 수 있을 만큼만 부분적으로 나눠 배낭에 넣음 -Pseudo Code Input : n개의 물건, 각 물..

Greedy 알고리즘의 세 번째 문제 3.최단 경로 찾기 문제 -주어진 가중치 그래프에서 '어느 한 출발점'에서 '또 다른 도착점'까지의 최단 경로를 찾는 문제 -weight값이 양수일 때! -대표적인 알고리즘 다익스트라(Dijkstra)최단 경로 알고리즘 주어진 출발점에서 시작하여 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정 앞선 최소 신장 트리와 비교했을때, 무조건 weight가 적은 노드를 찾는 MST와는 달리 특정 경로를 향해 거쳐갈 수 있는 경로 중에서 가장 weight가 적은 것을 선택해야 한다. 여기서 Greedy 개념에 Dynamic programing 성격을 가진다. 서울에서 대구로 가는 최소 경로를 찾을 때, 출발점 기준 ..

Greedy 알고리즘 문제 중 하나인 최소 신장 트리 구하는 문제의 두 번째 풀이 -Prim algorithm 랜덤으로 노드를 하나 고르고 고른 노드와 연결되는 edge 중 weight가 적은 것을 고르고, 이어진 노드에서 이 과정을 이어가기를 반복한다 -주의 점을 하나 선택할때마다 근처 점들의 weight를 가져오는 것은 비효율적이다. 그래서 배열D에 각 노드에서 다른 한 노드까지 걸리는 wieght의 최소값을 저장해놓는다. D의 값들 중 최솟값을 T로 업데이트한다. T를 갱신할때마다 D를 업데이트한다. 이 과정이 추가됨에 따라 Greedy Search+Dynamic program 방법이 섞인 알고리즘이 된다. -Prim MST의 Pseudo Code 입력 : 가중치 그래프 G=(V,E), |V|=n,..

정의 그리디 알고리즘은 최적화 문제를 해결하는 알고리즘 최적화(optimization) 문제 : 가능한 해들 중(선택 순간)에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불린다. 이름만큼 그리디 알고리즘은 (입력) 데이터 간의 관계를 고려하지 않고 수행 과정에서 '욕심내어' 최소값 또는 최대값을 가진 데이터를 선택하는 것.(부분적인 최적해(Partial Solution)) 당장 눈 앞의 선택을 하기 때문에 '근시안적'선택이라고도 말한다. 이들을 모아 문제의 최적해(Final Solution)를 구한다. \ 특징 -그리디 알고리즘은 한 번 선택하면 이를 절대로 번복하지 않는다. 뒤에 나쁜 결과가 나와도 선택한 데이터를 버리고 다른 것을 취하지 않는다..

-선택 문제란? n개의 숫자들 중에서 K번째로 작은 숫자를 찾는 문제이다. 최소 숫자를 k번 찾거나, 숫자들을 정렬한 후 k번째 숫자를 찾는 방법도 있지만, 각각 최악의 경우 O(kn)과 O(nlogn)의 수행 시간이 걸린다. 그래서 다른 방법으로, 정렬된 입력의 중간에 있는 숫자와 찾고자 하는 숫자를 비교함으로써, 입력을 2/1로 나눈 두 부분 중에서 한 부분만을 검색하는 방법이 있다. 퀵 정렬처럼 피봇을 무작위로 선택하고 한 부분을 정렬시킨다. 퀵 정렬과 다른 점은, 원하는 수가 속하는 '원하는 그룹'이 아니라면 정렬시킬 필요가 없다는 것이다. Small group은 피봇보다 작은 숫자의 그룹이고, Large group은 피봇보다 큰 숫자의 그룹 이 때 각 그룹의 크기를 알면, k번째 작은 숫자가 어..

분할 정복 알고리즘이란? -주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘. ->문제를 나누어서 풀면 더 효율적인 경우 사용 -대부분의 분할 정복 알고리즘은 분할만 해서는 해를 구할 수 없다. -따라서 분할된 부분 문제들을 정복해야한다. ->부분해를 찾는다. ->일반적으로 부분 문제들의 해를 취합하여 보다 큰 부분 문제의 해를 구한다. -종류 1.합병 정렬(merge sort) 합병 정렬은 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘. 1)n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할(Divide) 2)각각의 부분문제를 해결(Conquer) 3)재귀적으로 합병 정렬(Merging) 2.퀵 정렬(quick sort) 위와 반대로 정복 후 분..