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

문제 링크 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 \t...

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

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

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

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

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

문제 링크 1. 문제 풀이 무한히 큰 배열의 분수들에 대해 지그재그로 순서를 매겼을 때, $X$ 번째 분수를 구하는 문제로 반복문을 활용해 분자가 $1$ 이면 분모가 $1$ 이 될 때까지 좌하 방향으로 순회하고, 분모가 $1$ 이면 우상 방향으로 순회하도록 했다. 이때 끝에 도달하면 우로 한 칸 이동하거나 아래로 한 칸 이동하도록 해줬다. ...

문제 링크 1. 문제 풀이 주어진 정수를 소인수분해하는 문제로 소인수분해는 $2$ 이상의 소수로 주어진 수를 반복적으로 나누어서 $1$ 이 될 때까지 반복하면 된다. 이때 반복적으로 나누는 과정 덕분에 합성수로 나누게 되어 잘못 소인수분해를 할 일은 없는데 해당 합성수를 구성하는 소수로 이전에 이미 나누었을 것이기 때문이다. 따라서 나누는 수를...