[백준] 5582번 공통 부분 문자열 파이썬 풀이
https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 1. 풀이 DP 테이블을 활용하자 아래 9251번 문제와 현재 5582번 문제는 비슷하지만, 확연한 차이점이 하나 있다. 9251번은 공통 부분 문자열 사이에 다른 문자열이 존재해도 괜찮았지만, 현재 5582번은 반드시 공통 서브 문자열이 서로 붙어 있어야 한다. 서브 문자열 사이에 다른 문자가 들어오면 안 된다. [백준] 9251번 LCS 파이썬 풀이 https://www.acmicp..
[백준] 9251번 LCS 파이썬 풀이
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 풀이 가장 뒤의 문자부터 검사하자 맨 뒤 문자부터 서로 비교하면서 (1) 같으면 두 문자열에서 동시에 마지막 문자를 제거하고 (2) 다르면 문자열1의 마지막 문자만 제거하거나 문자열2의 마지막 문자만 제거하는 식으로 2가지 갈래로 나누어 가자. 더 이상 문자열을 비교할 수 없을 때는, 그 동안 동시에 제거된 문자 (C, E)가 바로 두 문자열의 L..
[백준] 2294번 동전 2 파이썬 정답 풀이
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 1. 접근 방식 작은 문제들을 모아 큰 문제를 해결하는 다이나믹 프로그래밍 기법이다 k원을 구성하는 최소 동전들의 개수는 (k - coin)원을 구성하는 최소 동전 + 1이다. 따라서 1원부터 k원까지 점진적으로 각 금액을 구성하는 최소 동전 개수를 구하면 문제를 해결할 수 있다. 인덱스 i원을 만드는 최소 동전 개수를 담은 1차원 dp 배열을 선언하자 최소 동전 ..
[백준] 1890번 점프 파이썬 풀이
https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 1. 접근 방식 dfs로 접근하면 안 된다 시작점과 끝점이 명확한 그래프 문제처럼 보이지만, DFS로 풀면 시간 초과가 발생한다. bfs로도 접근하면 안 된다 (a - 1, b)에서 (a, b)를 방문하게 되는 경우와 (a, b - 4)에서 (a, b)를 방문하게 되는 경우는 서로 다르게 취급되어야 한다. 그러나 bfs에서 각 노드의 방문 여부를 나타내는 visited라는 배열은 (a ..