백준
BOJ 2457 공주님의 정원 [Java]
BOJ 2457 공주님의 정원 1. 문제 링크 https://www.acmicpc.net/problem/2457 2. 문제 해설 그리디 알고리즘을 이용하여 푸는 문제이다. 백준 문제 중 1931번 회의실 배정과 비슷한 결을 가진 문제이다. 1931번을 풀어보지 않았다면 먼저 풀어보도록 하자. https://www.acmicpc.net/problem/1931 다시 문제로 돌아와서, 일단 그리디를 이용해서 풀면 될 것 같다는 생각은 들었지만 그리디를 이용하려면 검증이 필요하다. 매번 최선의 선택을 한 것이 전체적으로 봤을 때도 최선의 답이라는 것을 검증해야한다. 그 전에 일단 내가 어떻게 문제를 그리디적으로 접근했는지 살펴보자. 1. 3월 1일을 기준일로 잡는다. 2. 기준일보다 일찍 피는 꽃들 중에서 가장..
BOJ 9663 N-Queen [Java]
BOJ 9663 N-Queen 1. 문제 링크 https://www.acmicpc.net/problem/9663 2. 문제 해설 퀸이 체스판에서 서로 공격할 수 없으려면 3가지 조건을 다 만족해야한다. 같은 행, 같은 열, 대각선 상에 퀸이 존재하면 안된다. 여기서 우리가 퀸을 한 행에는 한개씩만 두기로 해보자. 그렇다면 퀸이 같은 행에 존재하는 경우는 없으므로 조건 중에 1가지는 생각하지 않아도 된다. 1차원 배열을 이용하여서 퀸의 위치를 표현했다. queen[i] = j 라고 하면, i번째 행의 퀸은 j열에 존재한다라는 의미이다. 퀸을 놓는 것은 백트래킹 과정을 이용하여 간단하게 해결가능하다. 23~37줄의 solve 메서드를 살펴보자. solve 메서드의 매개변수는 r로 현재 행을 의미한다. 그러므..
BOJ 11559 Puyo Puyo [Java]
BOJ 11559 Puyo Puyo 1. 문제 링크 https://www.acmicpc.net/problem/11559 2. 문제 해설 문제에서 요구하는 구현해야할 기능을 크게 3가지로 나누어보겠다. 1. 터트릴 뿌요를 파악하기 - bfs 메서드 : 같은 색 뿌요가 4개 이상 연속되는 경우를 찾아야한다. bfs, dfs를 이용하면 되겠다는 생각이 들었는데 dfs를 이용하면 ㅗ, ㅜ 같은 모양으로 연속되있는 경우를 처리하기가 까다롭기에 bfs를 이용하기로 결정하였다. 같은 색 뿌요가 연속되는 경우 list에 담아 list의 크기가 4 이상이면 터트릴 수 있고 아닌 경우는 터트릴 수 없는 방식으로 처리하고자 하였다. 2. 뿌요를 터트리기 - explode 메서드 : list에 담겨 있는 뿌요를 빈 칸으로 만..
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..