PS/BOJ
BOJ 14891 톱니바퀴 [Java]
BOJ 14891 톱니바퀴 1. 문제 링크 https://www.acmicpc.net/problem/14891 2. 문제 해설 구현 문제이다. 문제를 본 후 든 생각은 톱니바퀴 1개를 돌리는 메서드와, 돌린 1개의 톱니바퀴를 기준으로 전체 톱니바퀴를 돌리는 메서드를 구현해주면 해결할 수 있겠다는 것이었다. 2가지 메서드를 구현하면서 생각했던 점을 적어보겠다. 1. 톱니바퀴 1개를 돌리는 메서드 아래 코드에서 72~88번째 줄의 코드이다. 몇 번째 톱니바퀴를 돌릴지, 어떤 방향으로 돌릴지 알아야하므로 인자로 받는다. 시계 방향이든 반시계 방향이든 결국 한칸씩 옆으로 옮기는 것이다. 그러므로 기존 톱니바퀴와 정보가 똑같은 임시 톱니바퀴 배열을 만들어 이용해준다. 시계 방향일때와 반시계 방향일때 처리해주는 방..
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 15686 치킨 배달 [Java]
BOJ 15686 치킨 배달 1. 문제 링크 https://www.acmicpc.net/problem/15686 2. 문제 해설 백트래킹을 이용하는 문제이다. 백트래킹의 대표적인 문제 n과 m 시리즈를 업그레이드한 문제라고 생각한다. 문제를 읽어보면 구현해야할 것은 크게 2가지이다. 1. 치킨 집을 m개 고르기 2. 치킨 집을 m개 고른 각 경우의 수마다 도시의 치킨 거리 구하기 이 2가지 기능을 이용해서 어떻게 전체적인 흐름이 돌아가는지 한번 설명해보겠다. 일단 치킨 집과 집의 위치를 arraylist에 담아준다. 그 후, 백트래킹을 이용하면 치킨 집을 m개 고르는 모든 경우의 수를 구할 수 있다. 여기서 m개를 고른 각 경우의 수마다 도시의 치킨 거리를 구해주고 그 중 최솟값이 정답이 된다. 3. 코..