Algorithm/Dynamic Programming (11) 썸네일형 리스트형 개미전사 문제 식량창고가 있을 때 최소한 한칸이상 차이가 나야 약탈을 연속으로 가능하다. 유형 파악 및 구현 내가 나름 정한 규칙이 있다. 전의 값이 지금 구하고자하는 값에 영향을 주는 가? DP 2차원 그래프에서 특정조건에 맞춰 연결된 집합을 구하거나 거리를 구하는가? DFS/BFS 완전탐색이나 시뮬레이션 문제 유형인가? Implementation 아무 생각이 안나는가? Greedy 뭐 이 중에서 알고리즘이 섞여서 나오기도 하지만 기본적으로는 저런 조건이 있다면 해당 알고리즘을 생각해내는게 중요하다. 이 문제는 전에 구한값이 지금 구하는 값에 영향을 미친다. 식량 창고가 다음과 같다고 가정하자 [2, 1, 9, 10, 11, 8] 첫번째 인덱스까지만 존재한다고 가정하고 턴다면 최대값은 2이다. check[1] .. 1로 만들기 문제 X가 주어질 때, 5, 3, 2로 나누거나 1을 빼서 결과적으로 1을 만들 때, 가장 최소의 연산의 수로 1을 만들어라 유형 파악 및 구현 전형적인 DP문제이다. 예전에 구한 값이 지금 현재 구하고자 하는 값에 영향을 준다 예를 들어, 26을 1로 만든다고 생각을 해보자 - 26은 5나 3으로는 나누어지지 않는다. - 26은 2로 나누거나 1을 뺄 수 있다. 이 때, 2로 나누는 경우 - 13에서 1을 만들기 위한 최소한의 연산의 수 + 1 1을 빼는 경우 - 25에서 1을 만들기 위한 최소한의 연산의 수 + 1 즉, 13 또는 25를 1로 만들기 위해 사용되는 연산의 수 + 1을 하고 둘 중 작은 값이 정답이 된다. x 를 1로 만드는 횟수 1 : 0 2 : min(2//2를 1로 만드는 횟수+1.. Dynamic Programming - Concept 해당 문제는 "이것이 코딩 테스트이다" 책을 참고하여 제작하였습니다. 다이나믹 프로그래밍(DP) - 메모리 공간을 더 사용해 연산속도를 늘리는 방법 - 탑다운, 보텀업 - 메모이제이션(캐싱) 다이나믹 프로그래밍을 사용할 수 있는 조건 - 큰 문제를 작은 문제로 나눌 수 있다. - 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. "예전에 구한 값이 지금 구하는 연산에 영향을 주는 경우에 이를 기록해놓는 메모이제이션을 통해 DP를 구현한다." 탑다운 - 큰 문제를 해결하기 위해 작은 문제를 호출한다. - 메모이제이션 - 재귀함수를 이용해 구현 보텀업 - 작은 문제에서부터 차근차근 답을 도출한다. - DP 테이블 - 반복문을 이용해 구현 유형 정리 - 예전에 구한 값들이 지금 계산할 값에 .. 이전 1 2 다음
