🔥 Algorithm

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다   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번을 채택할텐데 가장 효율적이고 쓰기 좋은 알고리즘을 선택해야하고 이것은 곧 효율성과 용이성이 좋다는 의미 (알고리즘에서는 효율성을 주로 신경씀) 그럼 알고리즘의 효율성은 어떻..

Do it! 알고리즘 코딩테스트 : 파이썬  시간 복잡도시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말함 파이썬에서는 2000만 번~1억 번의 연산을 1초의 수행 시간으로 예측표기법에는1. 빅-오메가 Ω(n) : 최선일 때의 연산 횟수2. 빅-세타 θ(n) : 보통일 때의 연산 횟수3. 빅-오 O(n) : 최악일 때의 연산 횟수가 있고 → 코딩 테스트에서는 당연히 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋음!(항상 최악의 경우를 생각하고 로직을 짜야함) 시간 복잡도를 바탕으로 코드 로직을 개선하려면 코드의 시간 복잡도를 도출할 수 있어야함!시간 복잡도 도출 기준은 1. 상수는 시간 복잡도 계산에서 제외 2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 됨 디버깅문법..