알고리즘

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다   Greedy Algorithm 개요 Algorithmic Paradigms Brute-force methods=> 가능한 모든 경우를 살펴보기Divide and conquer=> 문제를 작은 문제로 분할하여 재귀적으로 해결Dynamic programming=> 작은 문제의 결과를 메모해두고 재활용오늘 다룰 주제는 Greedy algorithms 임!  Greedy Strategy 지금 당장 가장 좋아보이는 것을 선택하는 전략임 => 미래의 상황은 고려하지 않음Greedy Algorithm 이란  최적해를 항상 보장하지는 않음현재의 선택이 미래에 미칠 영향을 고려하지 않기 때문에Loca..

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다   Selection Problem Problem Definition (정렬되지 않은) 배열 arr에서 i 번째로 작은 값 찾기Input : arr, i (0 (여기서 i는 0부터 시작한다는 점을 염두하자)Output : arr에서 i 번째로 작은 값 생각해볼 수 있는 Methods 로는 1. 최솟값 찾기를 반복=> 최악의 경우 시간 복잡도 Θ(i×n) = Θ(n^2)(최악의 경우 i가 n-1 이므로)2. 정렬 후 i 번째 값 찾기 => 정렬하는데 필요한 시간 Θ(n logn)  Heapsort 사용시 Θ(n + i logn)(build-heap을 하고 뽑는데 logn 걸리는게 i 번 반..

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다  Lower Bounds of Comparision Sorting  비교 기반 정렬 알고리즘 (Comparision sort) 에서 Worst case에 O(nlogn) 보다 빠른게 존재할까?  정렬 문제의 상한은 O(nlogn) 임 => quicksort 라는 O(nlogn) 알고리즘이 존재하기 때문  정렬 문제의 하한은 Ω(n log n) 임 => 모든 알고리즘이 Ω(n log n) 인 것을 증명해야함 Comparison Sort를 Decision Tree로 추상화 가능함    위 그림 처럼 모든 sort의 process를 Decision Tree 형태로 추상화가 가능함! => Tr..

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다   Heapsort Heapsort는 이름 그대로 Heap 자료구조를 활용하는 정렬 알고리즘이다! => Heap이란 Heap Property를 만족하는 Complete Binary Tree임! (Complete Binary Tree란 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리 = 왼쪽이 비어있을 수 없음) Heap Property(Min-Heap의 경우) 각 노드의 값 (Max-Heap의 경우) 각 노드의 값 >= 자식 노드의 값    => Complete Binary Tree 이므로 위와 같이 배열로 구현이 가능함!  Heap Operations의 경우 (n은 Heap에 저장된 ..

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다  Merge Sort 분할 정복(Divide and Conquer) 정렬 알고리즘임  => 영역을 나눠서 각각 정렬하고 합치는게 Key Idea(나뉜 영역을 재귀적으로 정렬)   Merging Two Sub-array   2개의 포인터를 이용하게 되는데 위 과정을 반복하여 나눠진 두 배열을 하나로 합친다 => 두 Sub-array의 최솟값을 비교하고 더 작은값을 복사하는 방식  결국 Merge는 arr에 n개만큼을 정렬하여 값을 채우게됨=> Θ(n) 만큼 연산을 필요로 하다는 것을 알 수 있음 Complexity Analysis of Merge Sort mergesort(arr, l, l..

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다  Sorting? 정렬(Sorting) : 배열 원소들을 번호 순, 알파벳 순 등 정해진 순서대로 재배치하는 문제 3 / 1 / 2 / 5 / 4   ->  1 / 2 / 3 / 4 / 5  Sorting Algorithms에는 크게 기본적인 정렬 알고리즘평균 시간복잡도가 Θ(n^2)인 알고리즘들Selection Sort, Insertion Sort, Bubble Sort고급 정렬 알고리즘평균 시간복잡도가 Θ(nlogn)인 알고리즘들Merge Sort, Quicksort, Heapsort특수 정렬 알고리즘특수한 경우 시간복잡도가 Θ(n)인 알고리즘들Radix Sort, Counting S..

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다   Complexity of Recursive Functions   Algorithm1 은 팩토리얼을 재귀적으로 나타내고 있고 Algorithm2 는 탐색 범위를 반으로 나누어 해당 숫자를 탐색하고 있음 그럼 복잡도는 어떻게 될까..? 바로 복잡도를 구하기는 힘들고 우선 복잡도 함수의 점화식 (Recurrence Relation)을 구해볼 수 있음  => 이는 복잡도 함수를 재귀적으로 정의한 식  Solving Recurrences 복잡도를 구하고 싶은데 점화식은 또 어떻게 풀 수 있을까..?  점화식을 푼다 = 점화식을 해석적 해로 변환 => 해석적 해(Closed solution) 란..

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Algorithm Analysis 알고리즘 : 어떤 문제(Problem)를 해결하기 위한 절차나 방법을 공식화한 형태로 표현한 것 => 여기서 문제란 입력(Input)과 출력(Output)의 관계 정렬 문제를 예시로 봤을 때Input : 정렬되지 않은 숫자들의 목록Output : 오름차순으로 정렬된 숫자들의 목록 한 문제는 다양한 알고리즘으로 해결할 수 있음  Problem : n을 n번 더한 값은?   누가봐도 3번을 채택할텐데 가장 효율적이고 쓰기 좋은 알고리즘을 선택해야하고 이것은 곧 효율성과 용이성이 좋다는 의미 (알고리즘에서는 효율성을 주로 신경씀) 그럼 알고리즘의 효율성은 어떻..