본문 바로가기

class 521

[백준 9252] LCS 2 [C] 풀이 "백준 9251, LCS"에서 LCS를 출력하기위해 사용했던 j, i값을 이용해 문자열이 동일한 경우를 Recursion방식으로 찾았다. 소스코드 #include #define max(a, b) a > b ? a : b int dp[1001][1001]; char str[2][1001]; void LCS(int j, int i){ if (dp[j][i]) if (str[0][i-1] == str[1][j-1]){ LCS(j-1, i-1); printf("%c", str[0][i-1]); }else dp[j-1][i] > dp[j][i-1] ? LCS(j-1, i) : LCS(j, i-1); } int main(){ scanf("%s %s", &str[0], &str[1]); int i, j; for.. 2021. 8. 24.
[백준 1644] 소수의 연속합 [C] 풀이 연속된 소수의 합이므로, 소수로만 이루어진 배열에서 투 포인트를 적용하면 된다. 에라토스테네스의 체로 소수가 아닌 것들을 구분하여 소수로만 이루어진 배열을 만들고, 투 포인트 방식으로 풀이했다. 소스코드 #include #include #include #define MAX 4000001 bool not_prime[MAX]; int sum_prime[MAX/10]; int main(){ int N; scanf("%d", &N); int sq = sqrt(N); for (int i = 2; i 2021. 8. 15.
[백준 10942] 팰린드롬? [C] 풀이 Dynamic Programming의 Memorization 방식으로 풀이했다. (S~E) 구간이 팰린드롬인지 알기 위해서는 (S+1 ~ E-1), (S+2 ~ E-2), ... (X, X+1) or (X, X)구간의 수들이 팰린드롬인지 알아내는 과정을 반복해야한다. 길이가 3이상일 때, 요소가 홀수개인 팰린드롬은 최종적으로 길이가 1인 팰린드롬의 여부에 따라, 요소가 짝수개인 팰린드롬은 최종적으로 길이가 2인 팰린드롬의 여부에 따라 결정되기 때문에 다음과 같이 나누었다. 입력을 받을 때 길이가 1, 2인 펠림드롬을 확인하고, for (int i = 1; i 1 && arr[i] == arr[i-1]) dp[i-1][i] = 1; } 입력이 끝난 후 길이가 3 이상인 팰린드롬을 구했다. for (i.. 2021. 8. 9.

티스토리툴바