gold_honeybadger

탐욕적 알고리즘(욕심쟁이 알고리즘)이라고도 하며, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식 내가 돈을 많이 받기 위해 문을 통과해야하면 어떤 문을 선택할 것인가 ? --> 10만원 이번 문을 통과해서 많은 돈을 받으려면? --> 8만원 총 18만원을 받았다 현재로썬 최적의 선택일지 모르지만 이렇게 보면? 사실 그렇게 좋은 선택은 아니다 greedy 알고리즘은 모든 사항을 고려하지 않고, 상황에 맞는 항상 최적의 선택을 할 수밖에 없다. 그렇다고 최악의 선택도 아니기 때문에 근사치를 추정하기 위해 많이 사용한다. 탐욕 알고리즘이 잘 작동하는 문제는 두 가지 조건이 만족해야한다. 1. 탐욕스런 선택 조건 : 앞의 선택이 이후의 선택에 영향을 주지 않는다..

coding/Algorithm 2021. 5. 11. 18:19

소수의 정의는 '1과 자기 자신 외에 양의 약수가 없는 1보다 큰 자연수' 2부터 (x - 1)까지의 모든 수로 중 하나라도 나누어떨어진다면 def isPrime(x): if x == 1: return False for i in range(2, x): if x % i == 0: return False return True 알고리즘 성능 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 약수의 성질을 이용한 개선 알고리즘을 만든다. 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루는 것을 알 수 있다 예를 들어 16의 약수는 1, 2, 4, 8, 16 에서 2 X 8 = 16은 8 X 2 = 16과 대칭이다 따라서 우리는 특정한 자연수의 자연수의 제곱근까지만 확인하면 된다 예를 들어 16이..

coding/Algorithm 2021. 5. 8. 12:08

2021.05.07 - [분류 전체보기] - [coding_test] 순위 검색 high: return false else: # 2. mid 는 (log + high) 를 2 로 나눈 몫으로 결정합니다. mid = (low + high) // 2 # 3. data[mid] 와 target 이 서로 같으면 목적을 달성했으므로 탐색을 종료합니다. if target == data[mid]: return True # 4. 만약 target data[m..

coding/Algorithm 2021. 5. 8. 01:23