반응형 전체 글229 점화식 Recusion Tree로 풀기 [ 점화식 기본 수식 ] 재귀의 기초 지식 내용을 알아보기 전에 아래의 수식이 어떤 시간 복잡도를 가지고 있는지를 눈으로 읽혀둔다. 처음 봤을 때는 이게 무슨 말인지 모를 수도 있지만, 나중에 딱 이 수식만을 알기 위해 찾을 경우가 존재하므로 글의 가장 상단에 위치시켰다. 하나의 항목을 제거하기 위해 입력을 반복하는 재귀 알고리즘이다. $$T(n) = T(n-1) + n => O(n^2)$$ 입력을 2개로 분할 후, 정렬 작업을 수행하는 재귀 알고리즘이다.(Quick Sort, Merge Sort) $$T(n) = 2T(n/2) + cn => O(nlogn)$$ 하나의 단계마다 입력을 절반으로 줄이는 재귀 알고리즘이다.(Binary Search) $$T(n) = T(n/2) + c => O(logn)$$.. 2021. 4. 21. Binary Search Algorithm [ 이진 탐색 알고리즘 ] 이진 탐색 알고리즘(Binary Search Algorithm)은 리스트에 존재하는 특정 값을 찾기 위해서 리스트의 범위를 절반씩 좁혀가며 찾는 알고리즘이다. 처음부터 끝까지 값을 비교하는 순차 탐색에 비해 이진 탐색 알고리즘은 속도가 월등하게 빠르다. 이진 탐색은 시작, 끝 그리고 중간에 있는 데이터의 인덱스를 통해 범위를 줄이고 비교대상을 찾는다. 다만 이진 탐색 알고리즘을 사용할 때는 리스트 안의 값들이 이미 정렬이 되어 있어야 한다. 정렬이 되어 있지 않은 리스트에서는 이진 탐색 알고리즘을 사용할 수 없다. 그러므로 Mege Sort나 Quick Sort 등을 사용해서 리스트를 먼저 정리하고 이진 탐색을 사용해야 하는 것이다. 정렬이 완료된 리스트에서 범위를 절반을 나누.. 2021. 4. 12. Randomized Algorithm [ 무작위 알고리즘 ] 무작위 알고리즘(Randomized Algorithm) or 랜덤화된 알고리즘은 무작위성을 사용하여 알고리즘의 일부를 랜덤하게 작동하게 만든다. 이런 방식의 알고리즘을 사용하기 좋은 경우는 바로 입력값의 적절한 분포를 알기 어려울 때이다. 입력값의 분포를 모르기 때문에 무작위성을 사용하여 기댓값을 동일한 확률로 처리하기 위함이다. 확률을 따라 운이 좋으면 소요시간이 짧아질 수도 있고 최악의 경우 최대 O(n)까지 비용이 발생한다. O(n)의 뜻을 이해하지 못하겠다면, 이전 글인 시간복잡도 관련한 글을 읽어보는 것을 추천한다. (1) 정렬 방법 : Permute-by-sorting 원소마다 임의의 Priority를 할당하고 그 순서대로 정렬한다. import random def pe.. 2021. 4. 11. 이전 1 ··· 32 33 34 35 36 37 38 ··· 77 다음 반응형
