백준 문제 풀이34 [백준 9252] LCS 2 https://www.acmicpc.net/problem/9252 해설 LCS DP 문제이며, 또 그 이후에 역추적을 사용 해 어떤 문자가 공통 문자열인지 구하는 문제입니다. 0 A C A Y K P 0 0 0 0 0 0 0 0 C 0😊 0 1 1 1 1 1 A 0 1😊 1 2 2 2 2 P 0 1😊 1 2 2 2 3 C 0 1 2😊 2 2 2 3 A 0 1 2 3😊 3 3 3 K 0 1 2 3 3 4😊 4 공통 문자 수 구하는 건 (https://far-simple.tistory.com/37) 여기서 했으니, 저는 역추적을 설명해보겠습니다. 일단, 😊 이거 적힌 순서대로 for문을 검색해주면 됩니다. 가장 오른쪽 가장 아래에서 부터 시작해서 왼쪽으로 이동합니다. 왼쪽으로 이동하면서 자기보다 왼쪽에 있는.. 2020. 3. 30. [백준 9251] LCS https://www.acmicpc.net/problem/9251 해설 이번 문제도 다이나믹 프로그래밍이다. LCS 문제를 통해 또 한번 DP의 넓은 세계에 감탄한다. LCS라는 문제로 Longest Common Subsequence 최장 공통 부분 수열의 길이를 구하는 문제이다. 지금부터 해설을 시작해보겠다. 예제에 맞게 ACAYKP CAPCAK 이 두 문자를 가지고 비교를 해보겠다. 먼저, 표를 그려주었다. ( 편의를 위해 0번 배열을 만들고, 0으로 초기화해놨다. ) 0 C A P C A K 0 0 0 0 0 0 0 0 A C A Y K P A부터 진행해보겠다. 0 A C A Y K P 0 0 0 0 0 0 0 0 C 0 0 1 1 1 1 1 A P C A K 이것만 보고 저 위에 있는 1의 의미를.. 2020. 3. 28. [백준 2294] 동전 2 https://www.acmicpc.net/problem/2294 해설 이 문제는 DP 즉, 다이나믹 프로그래밍 문제이다. ( 그리디로도 해봤지만 풀리지 않았다. ) 다이나믹 프로그래밍의 특별한 점은 큰 문제를 작은 문제로 나누어서 구한다는 것이다. 그러므로 작은 문제를 메모를 해가면서 큰 문제의 답을 구할 수 있는 발판을 마련하는 것이 다이나믹 프로그래밍 푸는 방법이다. 다이나믹 프로그래밍으로 문제를 푸려면 점화식을 구해야한다. 예제를 가지고 설명해보겠다. 설명은 대충 n번째 동전으로 k원을 만드는 데 필요한 최소 동전의 개수 구하는 걸 표로 써볼 거다. 일단 시작하기 앞서 0원은 어떤 동전이든 0개 필요하니,dp[0~n-1][0] = 0 으로 초기화 시켜놓겠다. 또, dp에서 0번 배열을 제외한 나머.. 2020. 3. 27. [백준 1541] 잃어버린 괄호 https://www.acmicpc.net/problem/1541 해설 이번 문제는 그리디 알고리즘을 사용하는 문제이다. 괄호를 더하고 빼서 최솟값을 구하는 게 문제인데, 나는 이렇게 풀었다. +가 있는 건 신경안쓰고 그냥 더해주고, 뒤에 -가 하나라도 나오면 - 로 괄호를 묶어 뒤에 있는 수를 다 더해줬다. 예시 1) 1+2+3-3+5 여기서 최솟값은 (1+2+3)-(3+5) 일거다. 예시 2) 1-3-1+5+2-13 여기서 최솟값은 1-3-(1+5+2)-13 이다. 결국 +뒤에는 -로 괄호를 묶어 더해준 셈이 된다. 1-3-(1+5+2)-13 = 1-(3+1+5+2+13) 이정도면 해설은 충분히 됐을 거라고 생각한다. 이번에는 글쓴이가 코드를 너무 더럽게 짜서 혹시라도 이 블로그 글을 보고 있다면 다.. 2020. 3. 26. 이전 1 2 3 4 5 6 ··· 9 다음
