걸음마코딩기

대표적인 dp문제이다. 하지만, 나는.. 바보같이 처음에 map써봤다가 당차게 틀려먹었다.. (대체 왜이러니..) map쓰면 문자열을 계속 순회해야해서 시간복잡도에서 걸린다. 그리고 이건 대표적인 dp라서 그냥 내가 바보였던것으로.. 넘어갑시다. 아무튼, dp를 이용해서 각 부분 문자열에 대한 LCS 값을 구해나가면 된다! 여기서 dp의 경우의 수는 두가지인데, i번째 문자열 == j번째 문자열 이건 왼쪽 위 대각선 값에 +1 해주면된다. 왼쪽 위 대각선 값이 이전 문자열인 (i-1,j-1)의 LCS 값이기 때문! i번째 문자열 != j번째 문자열 이건 왼쪽과 위 중 max값을 가져가면 된다. #include #include using namespace std; int main(void) { ios::s..

🚦 이번 포스팅에서는 〰️ ▶️ 동적 계획법(Dynamic Programming)이란? ▶️ 동적 계획법(Dynamic Programming) 문제 풀어보기 📌 동적 계획법(Dynamic Programming)이란? : 하나의 문제는 단 한번만 풀도록 매번 저장하는 알고리즘 동일한 문제를 요구하는 경우 기존에 이미 저장해 두었던 것을 가져온다. 불필요한 반복 계산을 줄이고 효율적으로 최적해를 찾는다. 계산한 값들은 하나의 보관용 테이블(배열)에 순서대로 저장한다. 분할 정복법과 같이 여러개의 하위 문제들로 나누어 먼저 처리해야 할 때 사용한다. 대표적인 문제 : 피보나치 수열 DP 구현의 두가지 방법 재귀 함수 이용 (Top - Down) : 큰 문제를 쪼개나간다. 재귀 함수를 이용한 피보나치 수열 구현..