문제 링크 1. 문제 풀이 서로 다른 세 점이 주어졌을 때, 적절한 점 $D$ 로 평행사변형을 만들 수 없으면 $-1$ 을 출력하고, 만들 수 있으면 만들 수 있는 평행사변형 중 가장 큰 둘레의 길이와 가장 작은 둘레의 길이의 차를 출력해야 하는 문제다. 평행사변형을 만들 수 없는 경우는 세 점이 일직선 상에 위치하는 경우로 세 점의 좌표...

문제 링크 1. 문제 풀이 주어진 수가 완전수인지 판단하는 문제로 완전수는 자기 자신을 제외한 약수의 합이 자기 자신이 되는 수이다. 약수는 $1$ 부터 주어진 수보다 작은 수까지 모든 수로 나누어서 나머지가 $0$ 이 되는지 판단하면 된다. 2. 코드 1. 풀이 [Java] String을 타입 매개변수로 갖는 리스트를 활용해서...

문제 링크 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, &...

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

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

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

문제 링크 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 { publi...

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