반응형 동굴 속 정보183 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. Greedy Algorithm Python [ Greedy Algorithm ] 그리디 알고리즘(Greedy Algorithm)은 탐욕 알고리즘이라고 한다. 탐욕이라는 말이 붙기 때문에 느낌이 좀 쌔하긴 하다. 쌔한 느낌 그대로 이 알고리즘은 지금 당장 좋은 것만 골라서 사용하는 알고리즘이다. 0부터 시작하는 A라는 그래프가 있다. 이 중 가지의 합이 가장 큰 경우를 찾아야 할 때 Optimal 처럼 0-3-100을 골라내야 한다. 하지만 Greedy는 0-10-8 처럼 당장 좋은 것만 고른다. Greedy는 0에서 시작해서 3과 10의 선택 순간에 10을 선택하고 7과 8의 선택 순간에 8을 선택함으로써 탐욕을 채운다. 항상 최적의 결과를 만들지 않기 때문에 그리디 알고리즘으로 문제를 풀었어도 최적의 결과인지를 확인해야 한다. 최적의 결과를 만.. 2021. 4. 11. 이전 1 ··· 17 18 19 20 21 22 23 ··· 61 다음 반응형
