PS/BOJ
BOJ 1260 DFS와 BFS [Java]
BOJ 1260 DFS와 BFS 1. 문제 링크 https://www.acmicpc.net/problem/1260 2. 문제 해설 그래프에서의 dfs와 bfs를 할 수 있는지를 묻는 문제이다. 인접 리스트를 이용하여 그래프를 표현해주고 dfs와 bfs를 돌려주면 된다. 주의할 점 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 점이다. : 인접 리스트에서 각 정점의 원소들을 오름차순으로 정렬해주면 쉽게 해결할 수 있다. 2. dfs를 비재귀적인 방식으로 풀 경우 재귀적인 dfs와 방문 순서가 다를 수 있다. : 나는 dfs를 재귀적인 방식으로 풀었지만, 재귀적인 방식이 아닌 stack을 이용해서 풀 경우 방문 처리를 제대로 해주지않으면 재귀적인 방식과 방문 순서가 ..
BOJ 2004 조합 0의 개수 [Java]
BOJ 2004 조합 0의 개수 1. 문제 링크 https://www.acmicpc.net/problem/2004 2. 문제 해설 어떤 숫자 n의 끝자리 0의 개수는 n을 소인수분해 했을 때 10을 얼마나 가지고 있느냐와 같다. 10을 얼마나 가지고 있느냐는 2 x 5 쌍을 얼마나 가지고 있느냐를 의미한다. 소인수분해를 했을 시 2와 5를 모두 가지고 있을 때, 2와 5의 갯수 중 작은 값이 2 x 5 쌍의 갯수와 같다. nCm = n! / (r! x (n - r)!) 이다. 우리는 조합의 값을 구할 필요는 없다. 단지 2와 5의 갯수만 구하면 정답을 구할 수 있다. n! / (r! x (n - r)!) 에서 2의 갯수를 어떻게 구할 수 있을까? n! / (r! x (n - r)!) 의 2의 갯수 = n..
BOJ 1676 팩토리얼 0의 개수 [Java]
BOJ 1676 팩토리얼 0의 개수 1. 문제 링크 https://www.acmicpc.net/problem/1676 2. 문제 해설 중고등학교 때 배웠던 수학의 기본 내용과 관련된 문제이다. 어떤 숫자 n의 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수는 n을 소인수분해 했을 때 10을 얼마나 가지고 있느냐와 같다. 10을 얼마나 가지고 있느냐는 2 x 5 쌍을 얼마나 가지고 있느냐를 의미한다. 예를 한번 들어보겠다. 240의 경우 소인수분해하면 2^4 x 3 x 5 이다. 2는 4개나 있지만 함께 짝을 맞춰줄 5는 1개 뿐이다. 즉, 2와 5를 모두 가지고 있다면 2와 5의 갯수 중 작은 값이 2 x 5 쌍의 갯수와 같다. 이제 팩토리얼에서 2 x 5 쌍의 갯수를 구하는 것을 어떻게 처리할..
BOJ 1149 RGB거리 [Java]
BOJ 1149 RGB거리 1. 문제 링크 https://www.acmicpc.net/problem/1149 2. 문제 해설 DP문제를 풀 때는 개인적으로 점화식을 세우는 것이 절반 이상이라고 생각한다. 일단 문제를 이해해보자. 문제를 읽어보면 각 집마다 빨강, 초록, 파랑 3가지 색 중 1개를 선택해서 칠할 수 있다. 또 추가적인 조건이 있는데 아래와 같다. - 1번 집의 색은 2번 집의 색과 같지 않아야 한다. - N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. - i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 복잡하게 쓰여있지만 결국 말하고자하는 바는 이웃한 집과는 색이 달라야한다는 것이다. 구하고자 하는 정답은 위 조건을 만족하면서 모든 집을 칠하..
BOJ 12100 2048 (Easy) [Java]
BOJ 12100 2048(Easy) 1. 문제 링크 https://www.acmicpc.net/problem/12100 2. 문제 해설 5번을 이동시키는데 각 이동마다 4개 방향으로 가지를 뻗쳐나갈 수 있는 백트래킹 문제이다. 문제를 읽어보면 구현해야할 기능은 크게 2가지다. 첫번째는 블록을 이동시키고 합치는 부분이고, 두번째는 백트래킹 과정을 통해 5번을 이동시키면서 모든 상황을 살펴 보는 부분이다. 두 기능을 어떻게 구현할지 생각해보자. 1. 블록을 이동시키고 합치는 기능 - move 메서드 백트래킹 과정에서 매 이동마다 4개의 방향을 선택할 수 있다. 즉, 매 이동마다 4개의 가지를 뻗는다. 그러므로 지금까지의 상황이 담긴 map 배열과, 이동시킬 방향을 인자로 받아야한다. 방향은 동, 서, 남,..