문제 링크 1. 문제 풀이 주어진 이항계수에서 끝자리 0의 개수를 세는 문제로 조합을 팩토리얼로 바꾸어 찾으면 해결할 수 있다. 이항계수는 아래와 같이 팩토리얼간 나눗셈으로 바꿀 수 있다. [\binom{n}{m} \frac{n!}{m!(n-m)!}] 끝자리에 0이 있다는 것은 위 식에서 분자와 분모에 소인수로 있는 2와 5...

문제 링크 1. 문제 풀이 원에서 두 현이 교차하는 상황으로 방멱 정리를 활용하면 $p_{ab} \cdot p_{cd} = p_{bc} \cdot p_{da}$ 가 된다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; public class Main { public...

문제 링크 1. 문제 풀이 주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제로 단조 스택을 활용해서 해결할 수 있다. 아래는 예제 그림의 히스토그램이다. 히스토그램의 첫 번째 막대부터 순서대로 탐색을 진행한다. 먼저 첫 번째 막대의 경우 기준이 될 다른 막대가 없다. 두 번째 막대의 경우 첫 번째 막대보다 ...

문제 링크 1. 문제 풀이 주어진 조건을 만족하는 이름을 출력하면 되는 문제로 건물 이름이 gwan으로 끝나야하며 맨 앞 글자와 맨 뒤 글자가 같아야해서 n으로 시작해야 한다. 중간에 k와 u를 적절히 넣어주면 된다. 2. 코드 1. 풀이 [Java] public class Main { public static void ...

문제 링크 1. 문제 풀이 시작 번호가 주어졌을 때 만들 수 있는 서로 다른 비밀번호의 개수를 구하는 문제로 DFS를 활용해서 해결할 수도 있지만 버튼이 3 by 3 크기라는 점에서 관찰을 통해서도 해결할 수 있다. 먼저 대칭성이 있으므로 코너 쪽에서 시작하는 경우, 코너 사이의 변에서 시작하는 경우, 중앙에서 시작하는 경우만 구하면 되며 ...

문제 링크 1. 문제 풀이 주어진 배열에 대해 추가, 삭제, XOR 최댓값을 구해야 하는 문제로 트라이 자료구조를 활용해서 해결할 수 있다. 각 수를 2진수 문자열로 다루어 삽입, 삭제를 구현하고 XOR의 경우 서로 다른 비트일수록 값이 커지기에 이에 맞게 탐색을 해주면 된다. 2. 코드 1. 풀이 [Java] import ja...

문제 링크 1. 문제 풀이 $N$ 개의 수에 대해 XOR 연산의 결과가 가장 큰 두 수를 찾는 문제로 트라이 자료구조를 활용하면 해결할 수 있다. XOR 연산은 두 수의 각 비트가 다를수록 값이 커지기 때문에 트라이에 각 수를 2진수 문자열로 저장하고 탐색은 각 자릿수에 대해 다른 비트를 우선으로 탐색하면 된다. 2. 코드 1. ...

문제 링크 1. 문제 풀이 부분 수열의 XOR 값의 최대를 찾는 문제로 트라이 자료구조를 활용하면 해결할 수 있다. 부분 수열의 경우 연속한 구간을 말하는데 누적 합에서 구간의 합을 누적 합의 차로 계산하듯이 누적 XOR도 구간의 XOR 값을 누적 XOR의 XOR 연산으로 구할 수 있다. 이를 위해 수열의 XOR 값을 누적시키며 트라이에서...

문제 링크 1. 문제 풀이 BaekJoon 14725번 - 개미굴 문제와 동일한 아이디어로 해결할 수 있다. 역슬래시 파싱에만 주의하면 된다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; public class Main { static StringBuilder ...

문제 링크 1. 문제 풀이 지워야 하는 파일들과 지우면 안 되는 파일들이 주어졌을 때 최소한의 삭제 명령으로 지워야 하는 파일들을 모두 지워야 하는 문제다. 트라이 자료구조를 활용하면 해결할 수 있는데 먼저 지워야 하는 파일들로 트라이를 만들어준다. 이때 생성 과정에서 방문한 모든 각 노드에 매번 +1을 해줘서 각 노드가 자신까지를 접두어로...