[알고리즘] Dynamic Programming(동적 계획법) 1. 다이나믹 프로그래밍이란? - "동적 계획법" - step1. 하나의 큰 문제를 여러 개의 작은 문제로 나눈다. - step2. 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용한다. - 하나의 문제 해결 패러다임 (특정한 알고리즘 X) - 기억하기 프로그래밍 2. 재귀와 DP의 차이? - 일반적인 재귀(Naive Recursion)를 단순히 사용 시, 동일한 작은 문제들이 여러 번 반복 > 비효율적 계산 ex. 피보나치 수열 - 재귀: f(n-1), f(n-2)에서 각 함수를 1번씩 호출 => 동일한 값을 2번씩 구하게 됨 => n 값이 증가함에 따라 호출되는 함수의 횟수는 기하급수적으로 증가 (약 7해) - DP: 한 번 구한 작은 문제의 결과 값을 저장하고 재사용 > 반복 X > 약 200회 .. [Algorithm] 하노이의 탑 알고리즘 (재귀) 💜 하노이의 탑이란? 1) 정의 - 하노이의 탑은 퍼즐의 일종으로, 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 2) 조건 한 번에 한개의 원판만 옮길 수 있다. 가장 위에 있는 원판만 이동할 수 있다. 큰 원판이 작은 원판 위에 있어서는 안 된다 3) 목표 - 세 막대를 왼쪽부터 A, B, C라고 가정하자. - 위 조건에 맞게 모든 원판을 A에서 C로 옮겨야 한다. 💜 어떤 기능을 하는 함수를 구현해야하는가? (문제 정의) - 원반의 이동 횟수를 최소화한다. - 각 원반을 옮기는 모든 순서를 출력한다. => 원반 개수 N개를 입력 받아, 모든 원반을 C막대에 옮기는 모든 과정을 출력한다. .. 이전 1 다음
