반응형 분류 전체보기233 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. 빅오(Big O) 시간복잡도 [ Big O, 시간복잡도 ] 빅오(Big O) 시간복잡도는 위 그림하나도 전부 설명이 가능하다. 빅오는 처리시간이 아니라 시간의 증가율을 나타낸다고 보면 된다. X는 데이터의 갯수, Y는 처리의 갯수이다. 순서를 보면 $O(2^n)$ > $O(n^2)$ > $O(n log n)$ > $O(N)$ > $O(log n)$ > $O(1)$ 이다. 참고로 빅오 표기법에서 상수는 연산에 고정된 값이라서 연산에 크게 작용하지 않는다고 본다. 그래서 상수 10을 빅오랑 곱해도 값은 빅오 그대로 라는 것을 알아야 한다. 예를들어 $10 \times O(1)$ = $O(1)$ 이다. 시간 증가량에 대한 표기법은 점근적 상한(Upper Bound)인 Big-O 외에 점근적 일치(Tight Bound)인 Big-Theta.. 2021. 4. 10. 이전 1 ··· 34 35 36 37 38 39 40 ··· 78 다음 반응형
