1. 문제 11497번: 통나무 건너뛰기 (acmicpc.net) 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 2. 풀이 요약하자면 인접한 원소간 차이의 최댓값이 최소가 되도록 배열을 정렬할때, 그 최솟값을 구하는 문제 단순히 크기 순으로 정렬한다고 하더라도.. [a1,a2,a3,...,an]에서 인접한 원소간 차이의 최댓값은 an-a1이므로, 배열의 최댓값과 최솟값의 차이이므로 이것이 최소일리는 없다 만약 크기순으로 정렬한다면, a1 < a2 < a3 < ... < an일때, 이들이 인접했을때, 원소간 ..
1. 문제 20915번: 숫자 카드 놀이 (acmicpc.net) 20915번: 숫자 카드 놀이 Albert 는 n장의 숫자 카드를 가지고 있다. 각 카드에는 0부터 9까지 숫자 하나씩이 적혀있고, 6이나 9가 적힌 카드를 회전할 경우 구분할 수 없다 (즉, 6이 적힌 카드는 회전하면 9로 보이고, 9가 www.acmicpc.net 2. 풀이 숫자를 두 부분으로 나눠서 곱했을때, 최대가 되도록 만들기 두 부분은 적어도 하나의 숫자를 반드시 포함해야한다 6이나 9는 회전해도 구분할 수 없으니 회전해서 사용가능하다. 그렇다면 곱했을때 최대가 될려면 6은 무조건 9로 만들어서 사용하는게 유리하다. 또한 두 수의 곱이 최대가 될려면, 앞자리에는 무조건 큰 수가 오는게 유리하다 또한 두 수 a,b에 대하여 그 차..
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..
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문제임이 증명되어있다. 가장..
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가 되는 방법의 수를 구..
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..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
