문제 링크 1. 문제 풀이 LCS의 길이 뿐만 아니라 실제 LCS까지 출력해야 하는 문제다. LCS의 길이는 2차원 dp 테이블의 가장 마지막 행, 마지막 열이 온전한 두 문자열의 LCS의 길이를 담고 있으니 여기서 구하면 되고, 실제 LCS는 이 dp 테이블을 역추적하는 방식으로 구할 수 있다. 최종적으로 구하면 실제 LCS의 역순으로 조회되...

문제 링크 1. 문제 풀이 전형적인 LCS 알고리즘 문제로 2차원 dp 테이블을 활용해서 구현했다. 문자열 $A$, $B$ 의 LCS를 구하는 dp 점화식은 아래와 같다. [dp[i][j] = \begin{cases} 0, & \text{if } i = 0 \text{ or } j = 0 \ dp[i-1][j-1] + 1, &am...

문제 링크 1. 문제 풀이 문자열로 올 수 있는 문자가 $A$, $C$, $G$, $T$ 네 종류일 때, 주어진 문자열과 유사도가 최소인 문자열에 대해 유사도와 문자열을 출력해야 하는 문제다. 주어진 문자열의 길이를 $n$ 이라 하고 $A$, $C$, $G$, $T$ 네 종류의 문자의 개수를 $a$, $c$, $g$, $t$ 라고 할 때 $n ...

문제 링크 1. 문제 풀이 두 문자열의 가장 긴 공통 부분 문자열을 찾는 문제로 최장 공통 부분 문자열 알고리즘(LCS)을 활용하면 해결할 수 있다. 최장 공통 부분 수열(Longest Common Subsequence)이 아니라 최장 공통 부분 문자열(Longest Common Substring)임에 주의해야 한다. 최댓값의 경우도 최장 공...

문제 링크 1. 문제 풀이 주어진 두 수의 배수, 약수 관계를 판단하는 문제로 서로를 나누었을 때, 나머지가 $0$ 인지 여부로 간단하게 판별할 수 있다. 2. 코드 1. 사칙연산 [Java] import java.io.*; import java.util.*; public class Main { public static voi...

문제 링크 1. 문제 풀이 달팽이가 높이 $V$ 인 나무 막대를 올라가는데 하루에 $A$ 미터를 올라간 후 $B$ 미터를 내려오는 과정을 반복한다. 시간 제한으로 $V$ 미터가 될 때까지 이를 반복하는 방식으로는 해결할 수 없어서 수식으로 며칠이 걸리는지 찾아야 한다. 달팽이가 $V$ 미터인 나무 막대에 도착하려면 도착하기 전날에는 $V - ...

문제 링크 1. 문제 풀이 주어진 $N$ 개의 수를 정렬하는 문제로 수의 개수가 최대 $1,000,000$ 개라서 $O(N^2)$ 보다 빠른 정렬 알고리즘을 활용해야 한다. 2. 코드 1. 정렬 [Java] import java.io.*; import java.util.*; public class Main { public st...

문제 링크 1. 문제 풀이 주어진 $N$ 개의 수를 정렬하는 문제로 수의 개수도, 수의 범위도 작아서 어떤 정렬을 활용해도 된다. 2. 코드 1. 정렬 [Java] import java.io.*; import java.util.*; public class Main { public static void main(String[] ...

문제 링크 1. 문제 풀이 $M$ 이상 $N$ 이하인 소수의 합과 최솟값을 찾는 문제로 주어진 구간에서 모든 소수를 먼저 찾아야 한다는 점에서 에라토스테네스의 체를 활용했다. 에라토스테네스의 체로 $N$ 이하인 모든 소수를 찾은 후 합과 최솟값을 구했다. 2. 코드 1. 에라토스테네스의 체 [Java] import java.io.*; ...

문제 링크 1. 문제 풀이 $N$ 의 $K$ 번째 약수가 존재하면 해당 수를, 존재하지 않으면 $0$ 을 출력하는 문제다. $1$ 부터 $N$ 까지 $N$ 을 나누어서 나머지가 $0$ 이 되면 약수이며 이 개수를 세다가 $K$ 가 되면 해당 수를, 되지 않으면 $0$ 을 출력하도록 구현했다. 2. 코드 1. 브루트 포스 [Java] i...