모종닷컴

그리디 알고리즘 : 최적화 문제(가능한 해들 중 가장 좋은 해를 고르는)를 해결하는 알고리즘 ◆그리디 알고리즘의 특징 1)데이터 간의 관계를 고려하지 않고 부분적인 최적해를 찾고, 이들을 모아서 문제의 최적해를 얻는다. 2)일단 한번 선택하면 그 데이터를 버리고 다른 것을 취하지 않는다. ◆그리디 알고리즘으로 해결 가능한 대표적인 문제들 1)동전 거스름돈 :거스름돈을 받을 때 가장 적은 수의 동전으로 주는 문제 #유사코드 입력:거스름돈 액수W 출력:거스름돈 액수에 대한 최소 동전 수 change=W,n500=n100=n10=n1=0 //n500,n100,n50,n10,n1은 각각의 동전 수를 위한 변수이다. while(change>=500) change=change-500,n500++ while(chan..

3)선택 문제 알고리즘 k번째 작은 수를 찾는 문제로서, 입력에서 퀵 정렬에서와 같이 피봇을 선택하여 피봇보다 작은 부분과 큰 부분으로 분할한 후에 k 번째 작은 수가 들어있는 부분을 재귀적으로 탐색한다. 평균 경우 시간복잡도는 O(n)이다. #유사코드 Selection(A, left, right, k) 입력: A[left]~A[right]와 k, 단, 1≤k≤|A|, |A|=right-left+1 출력: A[left]~A[right]에서 k 번째 작은 원소 1. 피봇을 A[left]~A[right]에서 랜덤하게 선택하고, 피봇과 A[left]의 자리를 바꾼 후, 피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자는 A[left]~A[p-1]로 옮기고, 피봇보다 큰 숫자는 A[p+1]~A[right]로..

분할 정복 알고리즘 = 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘 ◆대표적인 분할 정복 알고리즘 1)합병 정렬 문제를 계속해서 반으로 잘르고 다시 합병시키는 정렬. 자를 수 없을 때까지 자른 후 합병 과정에서 sorting함 #유사코드 MergeSort(A,p,q) 입력:A[p]~A[q] 출력: 정렬된 A[p]~A[q] if( pfloor MergeSort(A,p,k) MergeSort(A,k+1,q) A[p]~A[k]와 A[k+1]~A[q]를 합병한다. } #파이썬 소스 def merge_sort(a): print(a) n = len(a) # 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없음 if n

알고리즘 = 문제를 해결하는 단계적 절차 또는 방법 ◆알고리즘의 특성 -정확성 : 알고리즘은 주어진 입력에 대해 올바른 해를 주어야 한다.-수행성 : 알고리즘의 각 단계는 컴퓨터에서 수행이 가능하여야 한다.-유한성 : 알고리즘은 일정한 시간 내에 종료되어야 한다.-효율성 : 알고리즘은 효율적일수록 그 가치가 높아진다. ◆알고리즘의 표현 방법 말로 표현 :ex)첫 카드의 숫자를 읽고...다음 카드의 의사 코드 : 프로그래밍 언어와 유사ex) max=A[0] for i = 1to9 if(A[i]>max)max=A[i] return max ◆여러가지 알고리즘 #해결방식에 의한 알고리즘 분류-분할 정복 알고리즘-그리디 알고리즘-동적 계획 알고리즘-근사 알고리즘-백트래킹 기법-분기 한정 기법-기타 등등 문제를 해..