9251번 문제 - LCS(Longest Common Subsequence) 이 문제는 풀이법이 잘 떠오르지 않았다. 문자열 a,b를 가지고 점화식을 그려보자면, a[i] == b[j] 일 때, LCS(a[i], b[j]) = LCS(a[i-1], b[j-1]) + 1 a[i] != b[j] 일 때, LCS(a[i], b[j]) = LCS(a[i-1], b[j]), LCS(a[i], y[i-1]) !! 위의 코드는 자꾸 틀렸다.. 입력값의 길이 조건이 없는 게 찝찝했는데 다른 사람 풀이를 보고 나니 앞에 패딩을 넣고 인덱스를 +1 로 처리해줘야한다는 걸 알았다. 내가 완전히 이해한 건지는 모르겠지만 다음에 내 힘으로 다시 풀어보자. 12865번 문제 - 평범한 배낭 ![

수열 문제, DP로 풀어보자! 11053번 - 가장 긴 증가하는 부분 수열 문제 설명 이 문제는 생각보다 문제를 이해하는 데에 시간 소모가 컸다. 역시 문제를 처음 접했을 때, 문제와 입력 조건, 출력을 잘 읽어보는 것이 중요하다는 걸 또 한번 느낄 수 있었다. 수열이 주어졌을 때, 증가하는 숫자의 수열 (연속 조건 x) 길이 중 가장 긴 길이를 구하는 것이다. 테스트 케이스가 간단한 입력만 나와있어서 그거만 보고 풀었다가는 산으로 갈 수 있다. , 와 같은 케이스를 고려해야 하기 때문이다! 처음 드는 DP의 사고방식은 각 인덱스마다 그 값으로 끝나는 증가하는 수열의 길이를 저장하는 것이었다. 그렇다면

동적 프로그래밍(dynamic programing) 지난 계단 오르기 문제(참고)를 풀어보며 동적 프로그래밍은 각 단계의 최적값을 메모리에 기록하여 중복 연산을 줄이는 기법이라고 이해했다. 그 이해를 바탕으로 오늘은 1912번 연속합 문제를 풀어보았다. 문제 1 - 연속합 배열이 주어졌을 때, 가장 큰 부분합을

동적 프로그래밍(다이나믹 프로그래밍)의 목적은? 메모리를 사용해서 중복 연산을 줄이고, 수행 속도를 개선하는 것 여기서 메모리를 사용한다는 것은! 배열 혹은 자료구조를 만든다는 것이다. 이를 통해 중복 연산을 줄인다는 것은 연산한 결과를 배열에 담는다는 것이다. 자꾸 다이나믹 프로그래밍이라는 이름이 와닿지 않아서 모호해지고, 응용이 어려워지는 것 같다. 한 교수님은 이것을 기억하기 알고리즘이라고 말했는데 그렇게 생각하고 풀어보자. 동적 프로그래밍 알고리즘 문제를 알아보고 구분하는 방법 이 풀이법은 특정 유형에만 국한되지 않고 다양한 유형의 문제를 최적화할 때 고려될 수 있는 알고리즘이다. 그렇다면 코딩테스트 문제를 보고 dp로 풀어야겠다고 어떻게 알아볼까? dfs/bfs 로 풀 수는 있지만 경우의 수가 너무 많은 문제 경우의 수들에 중복 연산이 많은 경우 위에 해당한다고 했을 때, 각 위치까지 올 수 있는 최적의 값을 기록해가며 활용해보는 것이다. 그렇게

개념 참고 - https://velog.io/@lhj99apr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Dynamic-Programming%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95 백준 9461 - 파도반 수열 문제 - [https://www.acmicpc.net/problem/9461] 수열의 패턴을 잘 살펴보고, 패턴을 코드로 구현하면 된다. 백준 1149번 - RGB거리 문제 링크 - https://www.acmicpc.net/problem/1149 이 문제는 dp로 푼다는 생각을 못했던 문제다. 여기서 다시 동적프로그래밍으로 풀 수 있는 문제의 조건을 살펴보면, 작은 해가 큰 해에 영향을 끼치는 것, 그 값을 구하기 위해 이전의 값이 반복적으로 사용된다는 점을 확인할 수 있고 DP로 구현할 수 있다. 백준 1932번 - 정수 삼각형 문제 링크 - https://www.acmic

1. Dynamic Programming 이란? DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은동적 프로그래밍은 "큰 문제"를 "부분 문제"로 나누고 "부분 문제"의 정답으로 "큰 문제"의 해답을 찾아가는 알고리즘 설계 기법이다. Richard Bellman이 1950년대에 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지어졌으니 신경 쓰지 않아도 된다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하는 이 방식을 그래서 DP 보다는 '기억하며 풀기'라고 부르면 더 직관적일 것 같다. 2. DP를 쓰는 이유? 왜 DP를 사용할까? 일반적인 재귀(Naive Recursion) 방식을 사용하는 것도 DP와 매우 유사하게 느껴진다. 하지만 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다. 피보나치 수열을 예로 들어 동적 프로그래밍을 설명하려 한다. 다음은 피보나