목록프로그래밍, 알고리즘 (11)
Shine's dev log
[알고리즘] Activity Selection (Greedy Algorithm 활용)
1. Activity Selection 코드 def activity_selection(S, F, k, n, result): m = k + 1 while m a3 선택 3) a3을 선택하고 난 뒤 남은 시간은 7~16이다. 이 중 가장 빨리 끝나는 Activity는 a6이다. -> a6 선택 4) a6을 선택하고 난 뒤 남은 시간은 10~16이다. 이 중 가장 빨리 끝나는 Activity는 a8이다. -> a8 선택 5) a8을 선택하고 난 뒤 남은 시간은 14~16이다. 이 중 선택할 수 있는 Activity는 없다. -> 종료 즉 위와 같은 과정을 통해 나온 결론은 a1, a3, a6, a8이다. 다시 코드로 돌아가보자. def activity_selection(S, F, k, n, result): m..
[알고리즘] The Longest Common Subsequence(LCS) (Dynamic Programming 활용)
1. LCS 코드 def lcs(X, Y, m, n): if m == 0 or n == 0: return 0 elif X[m-1] == Y[n-1]: return 1 + lcs(X, Y, m-1, n-1) else: return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)) X = ['h', 'e', 'r', 'o', 'i', 'c', 'a', 'l', 'l', 'y'] Y = ['s', 'c', 'h', 'o', 'l', 'a', 'r', 'l', 'y'] print(lcs(X, Y, len(X), len(Y))) 위의 코드는 LCS를 recursive 하게 수행하는 python 코드다. (Dynamic Programming 방식 아님) def LCS_dp(X, Y, m, ..
[알고리즘] Quick Sort 의 개념
1. Quick Sort 코드 def swap(a, b): return b, a def partition(A, p, r): x = A[r] i = p - 1 for j in range(p, r-1): if A[j]
[알고리즘] Maximum-subarray 구하기 (Divide-and-conquer 활용)
1. Maximum-subarray 코드 def FindMaximumSubarray(A, low, high): if high < low: return 0, 0, 0 if high == low: return low, high, A[low] else: mid = (low + high) // 2 (left_low, left_high, left_sum) = FindMaximumSubarray(A, low, mid - 1) (right_low, right_high, right_sum) = FindMaximumSubarray(A, mid + 1, high) (cross_low, cross_high, cross_sum) = FindMaxCrossingSubarray(A, low, mid, high) if left_s..
[알고리즘] Merge sort (Divide-and-conquer 활용)
1. Merge sort 코드 def mergesort(l): if len(l) < 2: return l mid = len(l) // 2 left = mergesort(l[:mid]) right = mergesort(l[mid:]) if left and right: return merge(left, right) def merge(left, right): left.append(99999) # Suppose 99999 is infinite. right.append(99999) # Suppose 99999 is infinite. index1 = 0 index2 = 0 temp = [] while left[index1] != 99999 or right[index2] != 99999: if left[index1]..
[알고리즘] Insertion sort 란?
1. Insertion sort 코드 def insertion_sort2(arr): for n in range(1, len(arr)): j = n key = arr[j] i = j - 1 while i >= 0 and arr[i] > key: arr[i + 1] = arr[i] i = i - 1 arr[i + 1] = key arr = [9, 8, 1, 7, 5, 3, 2, 6, 4] insertion_sort(arr) print(arr) 위의 코드는 Insertion Sort의 파이썬 코드다. 2. 기본 알고리즘 Insertion sort의 기본 원리는 카드를 들고있을때 정렬하는 것과 유사하다. 위의 사진처럼 카드를 양손에 쥐고있다고 하자. 왼손에는 무조건 정렬된 상태의 카드들을, 오른손에는 무작위로 ..