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

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

문제 링크 1. 문제 풀이 각 방마다 규칙적인 숫자가 부여되어 있는데 특정 방까지 최소 개수의 방을 지나서 갈 때, 몇 개의 방을 지나가면 도착할 수 있는지 구하는 문제다. $1$ 개의 방을 지나면 갈 수 있는 방은 1번 방 하나뿐이며, $2$ 개의 방을 지나면 갈 수 있는 방은 2 ~ 7번 방, $3$ 개의 방을 지나면 갈 수 있는 방은 ...

문제 링크 1. 문제 풀이 주어진 수 중에서 소수의 개수를 구하는 문제로 각 수에 대해 $2$ 부터 해당 수의 제곱근까지 나누어서 나머지가 $0$ 이 되는 수가 있는지 판단하는 방식으로 찾아도 되고, 에라토스테네스의 체를 활용해서 미리 소수를 구한 후 비교하는 방식으로도 해결할 수 있다. 2. 코드 1. 소수 판정 [Java] ...

문제 링크 1. 문제 풀이 세 문자열의 LCS 문제로 두 문자열의 LCS는 2차원 dp 테이블을 활용해서 해결하듯이, 3차원 dp 테이블을 활용하면 된다. 문자열 $A$, $B$, $C$ 의 LCS를 구하는 dp 점화식은 아래와 같다. [dp[i][j][k] = \begin{cases} 0, & \text{if } i = 0 ...

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

문제 링크 1. 문제 풀이 두 문자열의 가장 긴 부분 문자열을 구하는 문제로 LCS 를 활용하면 된다. 이때 LCS의 길이가 아니라 실제 LCS를 출력해야 하는데 실제 LCS는 LCS를 구할 때 활용한 dp 테이블을 역추적하는 방식으로 구할 수 있다. 최종적으로 구하면 실제 LCS의 역순으로 조회되므로 이를 뒤집으면 실제 LCS를 구할 수 ...

문제 링크 1. 문제 풀이 주어진 도형의 실선으로 이루어진 둘레의 길이를 구하는 문제다. 주어진 도형의 가장 아랫부분의 정사각형이 $n$ 개일 경우, 위에서 바라봤을 때 보이는 실선의 길이와 아래에서 바라봤을 때 보이는 실선의 길이, 왼쪽에서 바라봤을 때 보이는 실선의 길이와 오른쪽에서 바라봤을 때 보이는 실선의 길이는 모두 동일하며 $n$...

문제 링크 1. 문제 풀이 한글로만 이루어진 두 문자열의 LCS를 구하는 문제로 LCS 알고리즘을 활용하면 구할 수 있는 것은 똑같지만 언어별 한글 처리에 주의해서 구현해야 한다. 2. 코드 1. 풀이 [Java] InputStreamReader가 입력 스트림을 유니코드 문자로 디코딩(기본적으로 UTF-8)해줘서 Java에서 영...

문제 링크 1. 문제 풀이 주어진 $N$ 의 각 자릿수를 내림차순으로 정렬한 수를 출력하는 문제로 자릿수에 대한 계산을 해야 하기에 주어진 수를 문자열로 다루어서 역순 정렬을 구현해야 한다. 2. 코드 1. 풀이 [Java] 주어진 수 $N$ 을 char 배열로 변환 후 정렬하고 역순으로 출력했다. char 타입의 경우 숫자의 ...