컴퓨터 기초10 동적 계획법(Dynamic Algorithm)(with. Kotlin) 동적 계획법은 정확하게는 알고리즘.. 이라는 느낌보다는 문제 해결 방법론에 가깝다. 동적 계획법은 같은 계산을 계속 반복하는 최적 부분 구조 알고리즘에 가장 편안한 방법이다. 동적 계획법의 경우 이전에 계산해둔 값을 저장해두고 다음 계산을 위해 재활용해서 사용하는 방식이기 때문이다. 동적 프로그래밍은 크게 상향식 접근의 타뷸레이션과 하향식 접근의 메모이제이션이 방법론으로 제기된다. 동적 계획법의 예시인 피보나치 수열을 타뷸레이션과 메모이제이션의 예시로 확인한다. 피보나치 수열을 동적 계획법을 사용해야하는 이유는 다음과 같다. 피보나치 수열은 다음과 같은 계산법을 가진다. f(n) = f(n-1) + f(n-2) 이제 여기에 1 2 3 4... 순서대로 숫자를 넣어보자. f(0) = 1 f(1) = 1 f.. 2024. 4. 5. Java, Kotlin] 에라토스테네스의 체 에라토스테네스의 체는 소수를 구하는 아주 기본적인 알고리즘이다. 알고리즘은 다음과 같다 1. 내가 원하는 수 만큼의 숫자를 깔아놓는다. 2. 0과 1은 소수가 아니므로 뺀다. 3. 2는 소수이고, 2의 배수부터는 소수가 아니므로 2를 제외한 2의 배수는 모두 빼버린다. 4. 3은 소수이고, 3의 배수부터는 소수가 아니므로 3을 제외한 3의 배수는 모두 빼버린다. 4. 4는 소수가 아니므로 넘어간다. 5. 5는 소수이므로 5의 배수부터는 ... 이걸 반복한다. 근데 가만히 생각해보자? 2의 소수라서 2*2 -> 2*3 -> 2*4를 뺐다. 3의 소수에서 3*2 .. 는 2의 배수에서 2*3으로 빼버렸지 않나. 그러므로 3*3부터, 즉 3^2부터 시작해도 된다. 5도 마찬가지로 5*2는 2의 배수에서, 5*.. 2024. 4. 1. Kotlin 예시 작성] 유클리드 호제법(Euclidean Algorithm) 유클리드 호제법은 최대공약수와 최소공배수를 구할 수 있는 알고리즘이다. 그니까.. 말은 이건데... a와 b의 최대공약수는 a와 b를 나눈 나머지 r 이 존재할 때, b와 r의 최대공약수와 같다.. 라는건데(???) 그래서 나머지가 0이 나오면, 그 시점의 b가 최대공약수가 된다는거다(?????) 예를 들어 742와 854의 최대 공약수를 구해보자. 일반적인 방식으로 구해보면... 약수집합 = [2], 371 427 -> 약수집합 = [2, 7], 53 61 최대공약수가 2*7 = 14 가 나오는 것을 알 수 있다. 유클리드 호제법은 다음과 같이 구한다. 854 = 742 * 1 + 112 742 = 112 * 6 + 70 112 = 70 * 1 + 42 70 = 42 * 1 + 28 42 = 28 * .. 2024. 3. 26. 탐욕 알고리즘(Greedy Algorithm) 그리디 알고리즘, 욕심쟁이 알고리즘이라고도 부른다. 탐욕 알고리즘은 최적해를 구하는 알고리즘으로, 매 순간순간마다 최적의 방식을 선택하여 최종적인 최적해에 도달한다. 물론 순간순간의 최적의 선택을 했다고 해서 이것이 최종적으로 최적이라고 하지 않는다. 대표적인 예시가 마시멜로 실험이다. 현재 순간에 마시멜로를 먹는다면, 미래에 마시멜로가 없고 / 현재 순간에 마시멜로를 먹지 않는다면 미래에 마시멜로가 두 개이다. 이 때 최적의 마시멜로를 먹을 수 있는 최적해를 찾아야 한다. 라는 문제를 보자. 물론 상식적으로는 현재에 마시멜로를 참고, 미래에 마시멜로를 두 개 먹는 것이 최적이다. 그러나 그리디 알고리즘에서는 현재 하나를 먹는다. 왜냐고? 그리디 알고리즘은 '현재 순간' 에서 최적의 방식을 선택하기 때문.. 2023. 2. 2. 이전 1 2 3 다음 반응형