문자열 3개의 가장 긴 공통 부분문자열(Longest Common Subsequence)구하기

1. 문제 1958번: LCS 3 (acmicpc.net) 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 2. 풀이 문자열 X[1,2,...,i]와 Y[1,2,..,j]와 Z[1,2,..,k]의 가장 긴 공통부분문자열을 dp[i][j][k]라고 하자. 그러면 2개의 문자열 LCS를 구할때와 동일한 방법으로 DP배열을 채울 수 있다 https://deepdata.tistory.com/1022 = 1 and dp[i][j] == dp[i][j-1]: j -= 1 elif dp[i][j] == dp[i-1][j]: i -= 1..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 10. 28.
• textsms

LCS(Longest Common Subsequence) 문제 다이나믹 프로그래밍 기본 해법 배우기

1. 문제 두 문자열 $X = x_{1}x_{2}x_{3}...x_{n}$와 $Y = y_{1}y_{2}y_{3}...y_{m}$이 주어진다. 여기서 $x_{i}$와 $y_{j}$는 하나의 문자를 나타낸다. 여기서 문자열의 부분문자열(Subsequence)은? "원래 문자열에서 순서를 유지한채로 문자 몇개를 제거한 문자열"로 정의한다. 예를 들어 'ABCBDAB'라고 한다면... ABC도 부분문자열이지만, ABBAB도 부분문자열이 된다. 가장 긴 공통 부분문자열(Longest Common Subsequence) 문제는 K개의 문자열이 주어질때, 모든 문자열의 공통 부분문자열 중에서 가장 긴 공통 부분문자열을 구하는 문제이다. K가 변수이면 다항시간내에 풀 수 없는 NP-hard문제임이 증명되어있다. 가장..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 10. 28.
• textsms

integer partition5 -최댓값이 제한된 상태에서 원소의 합이 n이 되는 방법의 수 구하기-

1. 문제 9599번: Equal Sum Sets (acmicpc.net) 9599번: Equal Sum Sets Let us consider sets of positive integers less than or equal to n. Note that all elements of a set are different. Also note that the order of elements doesn’t matter, that is, both {3, 5, 9} and {5, 9, 3} mean the same set. Specifying the number of set e www.acmicpc.net 2. 풀이 이번엔 집합의 원소 최댓값이 n이면서 k개의 서로 다른 정수를 사용하고 합이 s가 되는 방법의 수를 구..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 10. 27.
• textsms

integer partition4 -서로 다른 소수의 합으로 자연수를 만드는 방법의 수(역으로 순회하는 테크닉)-

1. 문제 3908번: 서로 다른 소수의 합 (acmicpc.net) 3908번: 서로 다른 소수의 합 양의 정수는 서로 다른 소수의 합으로 나타낼 수 있다. 두 정수 n과 k가 주어졌을 때, n을 서로 다른 k개의 소수의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 여기서 덧셈의 순 www.acmicpc.net 2. 풀이 소수만을 사용하는데, 서로 다른 소수를 사용해야하고 k개를 사용해서 합했을때 n을 만드는 방법의 수를 구하기 일단 도구로 소수를 구해야겠지 n이 최대 1120이니까 1120이하의 소수를 모두 에라토스테네스의 체로 구해놓고 def get_prime(n): result = [1]*(n+1) for i in range(2,int(((n+1)**(1/2)))+1): if res..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 10. 27.
• textsms

integer partition 문제 3 - 서로 다른 자연수를 사용해서 특정한 자연수 n을 만드는 방법의 수는 홀수만을 사용해서 만드는 방법의 수와 같다(count number of partition of n)

1. 문제 9764번: 서로 다른 자연수의 합 (acmicpc.net) 9764번: 서로 다른 자연수의 합 첫째 줄에, 테스트 케이스의 개수 T (1 ≤ T ≤ 20)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. www.acmicpc.net 2. 풀이 dp[j][i]를 1부터 i까지의 자연수 중에서 최대 하나씩만 사용해서 j를 만드는 방법의 수라고 정의하자. 여기서 구성이 같은데 순서가 달라도 같은 방법으로 취급한다 https://deepdata.tistory.com/951 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 1. 문제 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 10. 23.
• textsms

담금질 기법(simulated annealing) 배우고 최소 외접원 문제(smallest enclosing circle problem) 풀기

1. 담금질 기법(simulated annealing) 담금질 기법은 인공지능에서 말하는 gradient descent와 비슷하다. 목적함수를 설정하고, 해당 함수를 최적화하는 해를 찾는 것이다. 현재 답의 근처 해를 적당히 찾은 다음, 해가 더 좋아질 경우에는 갱신하고 해가 좋아지지 않을 경우에는 확률적으로 갱신하는 기법이다. 다항시간에 해를 찾기 어렵다고 생각되면 적당히 좋은 해를 찾기 위해 사용되는 휴리스틱(heuristic) 방법이다. 마치 금속을 뜨거운 온도에 담금질하여 원하는 금속으로 만드는 과정과 비슷하다고 하여 이름 붙여진 듯 하다. 원하는 금속으로 만들려면 적절한 온도에 담그는게 중요한데, 담금질 기법의 핵심은 온도 설정에 있다. 인공지능의 gradient descent에서도 weight..

• format_list_bulleted 휴리스틱
• · 2023. 10. 18.
• textsms