코테 알고리즘 그리디 알고리즘(탐욕법) 초간단 이해 그리디 알고리즘이란? 사실 알고리즘이라고 말하기도 뭣하고 그냥 간단한 선택 방법론이다 그리디 알고리즘은 간단히 말해서 전체를 보지 않고 매 선택에서의 최적의 결과를 구하는 방법이다 이를 바꿔 말하면 그리디 알고리즘으로 구한 결과는 전체적으로 봤을때 최선의 선택이 아닐 수 있다는 것이다 예를 들어 다음과 같은 상황에서 최대 값을 찾는 경우 그리디 알고리즘은 10과 1 중에서 10을 선택한다 하지만 10을 선택한 경우 다음 숫자는 1 로 합쳐서 11이 되지만 1을 선택한 경우 다음 숫자는 50으로 합쳐서 51이 된다 해당 선택에서는 최선의 결과였지만 결국 전체를 고려하면 최선의 선택이 아니었던 것이다 그리디 알고리즘은 왜 쓸까? 항상 최선의 결과를 알아내는 것도 아닌데 그리디 알고리즘을 왜 쓰는걸까? 그리디.. 2023. 11. 4. 코테 알고리즘 다이나믹 프로그래밍 간단 이해 다이나믹 프로그래밍(dp)는 뭘까? 다이나믹 프로그래밍은 이름은 뭔가 거창하지만 개념은 간단한데 바로 최종 결과를 얻기 위해 필요한 하위 데이터를 계속 저장해서 상위 문제를 해결하는 방법이다 핵심은 하위 데이터를 계속 저장한다는 점이다 물론 이 말만 듣는다고 바로 이해하기는 어렵다 이해를 위해 예를 하나 들어보겠다 다이나믹 프로그래밍하면 무조건 따라오는 문제인 피보나치 수열을 보자 피보나치 수열은 n번째 수가 n-1과 n-2의 합인 수열이다 즉 n번째 수를 구하기 위해서는 n-1과 n-2의 정보가 필요하다 피보나치 수열을 다이나믹 프로그래밍으로 구하는 방법은 몹시 간단한데 코드는 다음과 같다 dp = [0]*n dp[0] = 1 dp[1] = 1 for i in range(2,n) : dp[i] = dp.. 2023. 11. 4. 이전 1 다음
