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

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

문제 링크 1. 문제 풀이 $A$ 와 $B$ 를 부분 문자열로 갖는 $S$ 의 최소 길이를 찾아야 하는 문제다. 해당 문제는 LCS 알고리즘을 활용하면 해결할 수 있는데 $A$ 와 $B$ 의 LCS의 길이를 $len$ 이라 할 때, $(A\ 의\ 길이 + B\ 의\ 길이 - len)$ 으로 $S$ 의 길이를 구할 수 있다. $A$ 와 $B...

문제 링크 1. 문제 풀이 주어진 $N$ 개의 수를 정렬하는 문제로 수의 개수가 최대 $10,000,000$ 개로 매우 많은데 수의 범위는 작다는 점에서 카운팅 배열을 활용하면 효율적으로 해결할 수 있다. $1$ 부터 최대 $10,000$ 까지 원소들의 등장 횟수를 카운팅한 다음 각 숫자의 등장 횟수만큼 출력하는 방식으로 해결했다. ...

문제 링크 1. 문제 풀이 $N$ 이 최대 $500,000$ 이고 각 숫자가 $-10,000,000$ ~ $10,000,000$ 일 때, $M$ 개의 숫자에 대해 등장 횟수를 출력하는 문제다. 가장 간단하게는 맵을 활용해 등장 횟수를 판단할 수 있고, 주어진 숫자 카드를 정렬한 후 Lower Bound, Upper Bound 이분 탐색을 통...

문제 링크 1. 문제 풀이 $N$ 이 최대 $500,000$ 이고 각 숫자가 $-10,000,000$ ~ $10,000,000$ 일 때, $M$ 개의 숫자에 대해 등장한 적이 있는지 여부를 출력하는 문제다. 가장 간단하게는 집합을 활용해 등장 여부를 판단할 수 있고, 주어진 숫자 카드를 정렬한 후 이분 탐색을 통해 등장했는지 판단하는 방식으...

문제 링크 1. 문제 풀이 주어진 문자열에 대해 전화를 거는데 걸리는 최소 시간을 구하는 문제로 각 알파벳 별로 몇 초가 걸리는지 미리 배열에 저장한 후 조회하는 방식으로 해결했다. 2. 코드 1. 풀이 [Java] import java.io.*; public class Main { public static void m...

문제 링크 1. 문제 풀이 $42$ 로 나눈 겹치지 않는 나머지의 개수를 구하는 문제로 방문 체크 배열을 활용해서 해결할 수도 있고, 집합 자료구조를 활용해도 해결할 수 있다. 2. 코드 1. 방문 체크 배열 [Java] import java.io.*; public class Main { public static voi...

문제 링크 1. 문제 풀이 세 점이 주어졌을 때, 직사각형을 만들 수 있는 남은 한 점의 좌표를 구하는 문제로 간단하게는 각 좌표가 두 번씩 등장해야 한다는 점을 활용한 조건문으로 해결할 수 있다. 다른 방법은 비트 XOR 연산자를 활용하면 되는데 비트 XOR 연산자는 두 비트가 다르면 $1$, 같으면 $0$ 을 반환한다. 따라서 $x$,...

문제 링크 1. 문제 풀이 주어진 문자열에서 크로아티아 알파벳을 구분해서 알파벳의 개수를 세야 하는 문제다. 크로아티아 알파벳을 찾으면 현재 바라보는 인덱스를 이동시키는 방식으로 크로아티아 알파벳의 개수를 세줬다. 2. 코드 1. 풀이 [Java] import java.io.*; public class Main { pu...