다이나믹프로그래밍 2

이코테 part 2 요약

그리디 알고리즘 - 탐욕법현재 상황에서 지금 당장 좋은 것만 고르는 방법 현재 선택이 나중에 미칠 영향은 고려하지 않는다. **그리디 알고리즘은 **기준을 알게 모르게 제시**해준다.**그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.Ex) 큰 단위의 동전이 항상 작은 단위의 동전의 배수이다. 모든 문제에 적용할 수 없음 **바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적 해결 방법이 존재하는지 고민해봐라 → 다이나믹 프로그래밍, 그래프 알고리즘구현완전탐색, 시뮬레이션 문제완전 탐색 - 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 - 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 유형파이썬..

알고리즘 2024.12.19

백준 2579 [python]

내 풀이1. 목적지에서 시작하여 시작 지점까지 재귀 함수를 호출한다.2. 목적지로 올 수 있는 경우에 대해 최대값을 구하고 최대값에 현재 계단의 값을 더해 최대값을 구한다. Ex) 5번째 계단의 경우 3번과 4번에서 올 수 있으므로 둘 중 최대값을 구하고 5번째 계단의 값을 더해 최대값을 구한다. 3. 연속으로 세번 이동하는 경우에 대한 예외 처리를 해주기 위해 cnt 값이 3이 되면 0을 반환하게 한다.4. 목적지에 따라 오는 경우의 수의 최대값이 다르기 때문에 이를 고려하여 dp 테이블을 생성한다. 특정 목적지로 오기 위한 최대값이므로 다름 Ex) 4번에 도착하기 위한 2번의 최대값과 3번에 도착하기 위한 2번의 최대값이 다를 수 있음 몇 번째 계단인지랑, 연속으로 몇 번 이동했는지..

알고리즘 2024.11.28