'프로그래밍/알고리즘' 카테고리의 글 목록

프로그래밍/알고리즘

Emong's Factory

2020.04.26

Prolem : Find an optimal order for mult. n mat Q. Given (d0, d1, d2, d3, d4, d5) = (2,4,1,3,4,2), solve the chained matrix multiplication problem. You may have only to make an array M and an array P. (You have only to make a table such as in p46 of the notebook.) What is the optimal order of the matrix multiplications? 1. i, j의 거리가 1일때 M[1,2] = 2 x 4 x 1 = 8 (k = 1) M[2,3] = 4 x 1 x 3 = 12 (k = ..

[알고리즘] 정비소 문제 - Bellman Ford Algorithm

2020.04.20

Q. Efficiently solve this problem for the following input. What algorithm should you use? Give the step - by - step descripion of the arrays D[0..6] and P[0..6]. Write the recursive algorithm 'void path (int P, int k)' to print out the final path. Write the final answer. Input 120 (최대 거리) 5 (정비소 개수) 80 30 30 60 40 20 (거리) 5 10 4 12 8 (정비 시간) ０ 1 2 3 4 5 6 T[최소비용] ０ 5 10 9 (14 , 9) 21 (21 , 22) 1..

[알고리즘] Dynamic Programming (동적 프로그래밍)

2020.04.16

Dynamic Programming(동적 프로그래밍)은 문제를 작은 인스턴스들로 나누고 Bottom-up order로 풀어나가면서 문제의 값을 저장해놓고 필요할때 가져와 쓰는 방식으로 문제를 해결하는 방식을 의미한다. Divide and conquer와의 공통점은 문제를 작은 단위로 나누어 해결한다는 것이고 차이점은 Divide and conquer는 Top-down 방식으로 위에서부터 진행하는 방식인데 Dynamic Programming은 Bottom-up 방식으로 작은 인스턴스부터 풀어나가면서 그 값을 더 큰 인스턴스를 풀 때 이용한다. 기존에 진행된 smaller instance의 값들은 주로 이차원 array에 저장되며 영향을 받는 변수의 수에 따라 배열의 차원은 더 늘어날 수도 있다. 재귀 피보..

[알고리즘]Divide and Conquer (분할 후 정복)

2020.04.16

Divide and Conquer(분할 후 정복) 방법은 어떠한 문제를 작은 단위로 나누고 그것이 해결하기에 충분히 작으면 그것을 풀고, 아니면 더 작은 단위로 나누어 알고리즘을 풀어나가는 방식을 의미한다. Divide and Conquer라 하면 재귀(Recursive) 방식으로 알고리즘을 풀어나간다. Divide and Conquer로 풀 수 있는 문제의 예는 Binary Search, Merge Sort, Quick Sort 등등이 있다. Divide and Conquer로 문제를 풀기에 적당하지 않는 경우 1) 문제를 smaller instance로 나누었는데도 size가 기존과 비슷 2) 문제를 n등분하였는데도 size가 n/c 일 경우 이럴 때는 알고리즘을 잘못 구성하게 되면 complexit..

[알고리즘] Insertion Sort, Merge Sort, Quick Sort 비교

2020.04.16

다음 세 정렬에 대한 3가지 속성과 시간복잡도 Insertion Sort Merge Sort Quick Sort 1. Stability O O X 2. In - place O X O (but stack space) 3. On - line O X X Time Complexity O(n^2) O(n log n) W : O(n^2) A : O(n log n) W : Worst case A : Average Why is quicksort faster than mergesort? Merge Sort : S[ i ]

Emong's Factory