반응형 [알고리즘 + 자료구조]43 [알고리즘] 동적계획법(2021.02.03수정) + 그리디 알고리즘 정리 1차 + (분할 vs 동적 ) 동적계획법 - 동적 계획법은 최적 부분 구조(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제해결 패러다임이다 ( 동적계획법의 사용 조건 : 최적 부분 구조 && 중복된 하위 문제들 ) - 쪼개지는 부분 문제가 중복될 때 메모이제이션을 사용하여 속도를 향상시키는 방법이다. 즉 하나의 문제가 부분 문제로 쪼개져서 푸는 문제에서, 같은 부분 문제들이 있다면 이들을 한 번만 실행하게끔만 구현해주는 것. (중복되는 문제에 대한 답을 여러 번 구할 필요가 없도록, 한 번 실행할 때 결과값을 캐시해놨다가 다음에 실행될 때는 캐시해놓은 값을 꺼내 쓰는것) - 부분 문제로 쪼개서 원래의 답을 구한다는 점, 최적 부분 구조에서 사.. 2020. 12. 14. [알고리즘] Do it 자료구조와 알고리즘 7장 정리 연습문제 Q_1 > 실습 7 - 2 프로그램에 다음 8개의 함수를 추가하세요. // 집합이 가득 찼다면 1, 아니면 0을 반환 int IsFull(const IntSet *s); // 집합의 모든 원소를 삭제하는 함수 void Clear(IntSet *s); // 집합 s2, s3의 대칭 차를 s1에 대입하는 함수 IntSet *symmetricDifference(IntSet *s1, const IntSet *s2, const IntSet *s3); // 집합 s1에 s2의 모든 원소를 추가하는 함수(s1 포인터 반환) IntSet *ToUnion(IntSet *s1, const IntSet *s2); // 집합 s1에서 s2에 들어 있지 않은 모든 원소를 삭제하는 함수(s1 포인터 반환) IntSet .. 2020. 12. 6. [알고리즘] 도수 정렬 ( = 카운팅 정렬 = 계수 정렬 ) 도수 정렬은 요소의 대소관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다. 도수 정렬 알고리즘은 도수분포표 작성, 누적도수분포표 작성, 목적 배열 만들기, 배열 복사의 4 단계로 이루어집니다. 코드 // 도수 정렬 함수(배열의 요솟값은 0 이상 max 이하) void fsort(int a[], int n, int max) { int i; int *f = calloc(max + 1, sizeof(int)); // 도수분포표 & 누적 도수 int *b = calloc(n, sizeof(int)); // 작업용 목적 배열 // step_0 (생략가능 : calloc함수가 동적으로 확보하는 메모리의 모든 값은 0으로 초기화되기 때문) for(i = 0; i 2020. 11. 27. [알고리즘] 힙 정렬 (Heap Sort) 힙 정렬 선택 정렬을 응용한 알고리즘인 힙 정렬은 힙의 특성을 이용하여 정렬을 수행한다. 힙 상태에서 루트를 꺼내고 다시 힙 상태 유지를 반복 코드 //힙 정렬 #define swap(type, x, y) do { type t = x; x = y; y = t;} while(0) // a[left] ~ a[right] 를 힙으로 만드는 함수. a[left] 이외에는 모두 힙 상태라고 가정. static void downheap (int a[], int left, int right) { int temp = a[left]; // 루트 int child; int parent; // 이 인덱스를 기준으로 다음 인덱스부터는 리프노드임 -> (Right-1)/2 // (Right-1)/2 + 1 보다 작아야 리프노드.. 2020. 11. 27. 이전 1 2 3 4 5 6 7 ··· 11 다음 반응형