[Algorithm] 가방문제(냅색 알고리즘, knapsack algorithm)
#. Problem https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 * The copyright in this matter is in Inflearn #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check performance time and usage memory) 5. Carry out the plan 6. Look back on the plan and find a way to ..
[Inflearn] 알리바바와 40인의 도둑(DP : Top-Down)
#. Problemhttps://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98* The copyright in this matter is in Inflearn #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check performance time and usage memory) 5. Carry out the plan 6. Look back on the plan and find a way to im..
[Inflearn] 알리바바와 40인의 도둑(DP : Bottom-Up)
#. Problemhttps://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98* The copyright in this matter is in Inflearn #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract- 해당 돌다리를 건널 때 돌의 높이 만큼 에너지가 소비- 이동은 최단 거리 이동- 현재 지점에서 오른쪽 도는 아래쪽으로만 이동- 출발점에서 도착점까지 가는데 드는 에너지의 최소량 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check pe..
#. Problemhttps://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98* The copyright in this matter is in Inflearn #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check performance time and usage memory) 5. Carry out the plan 6. Look back on the plan and find a way to im..
[Inflearn] 최대 선 연결하기(DP, LIS)
#. Problemhttps://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98* The copyright in this matter is in Inflearn #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check performance time and usage memory) 5. Carry out the plan 6. Look back on the plan and find a way to im..
#. Problemhttps://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98* The copyright in this matter is in Inflearn 철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철 수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요? #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution plan (select Algorithm, Data structure..
#. 동적 계획법? ㅇ 동적계획법 = 다이나믹 프로그래밍(Dynamic Programming), DP- 벨만-포드 알고리즘을 개발한 벨만이 만들어낸 알고리즘- 알고리즘 이름을 어떻게 지으면 기억에 잘 남고, 간지(?)가 날지 생각하다가 다이나믹이라는 단어가 좋아서 이렇게 되었다는.. ㅇ 특징- 다음 상태를 구하기 위해, 이전 상태를 저장하고, 사용(Memoization)- 무엇을 어떻게 저장할지 정하는 것이 중요- 많이 풀어보고, 생각 과정을 연습하는 것이 중요.. ㅇ 적용 순서1. 상태 정의- dp배열을 만들었을 때, index값이 의미하는 상태- 문제의 초기상태를 정의(직관적인 작은 문제의 해)2. 점화식 구하기- 다음 상태를 나타내기 위한 표현식3. 시간복잡도 계산4. 구현 ㅇ 적용 방법1. Top..