PS
프로그래머스 Lv.2 게임 맵 최단거리 [Java]
1. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/1844 2. 문제 해설 최단거리를 찾는 대표적인 문제이다. 이렇게 최단거리를 찾아야하는 문제는 bfs를 이용하여서 푸는 것이 편하다. 처음에 풀었을 때는 dfs도 간만에 구현해볼 겸하고 dfs로 풀었다가 시간 초과로 효율성 테스트를 통과하지 못했다. bfs는 목적지에 도착했을 때, 최단거리로 방문하는 것이 보장되지만 dfs는 모든 경우의 수를 다 보기 때문에 더 오랜 시간이 걸리기 때문이다. 3. 코드 보기 import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; class Solution { class..
BOJ 15685 드래곤 커브 [Java]
BOJ 15685 드래곤 커브 1. 문제 보기 https://www.acmicpc.net/problem/15685 2. 문제 해설 구현 문제다. 구현 문제는 내가 구현해야할 기능이 무엇인가를 파악하면 풀이의 방향이 보인다. 이 문제는 2가지 기능을 구현해주면 된다. 첫번째는 드래곤 커브를 그리는 기능, 두번째는 그린 후 크기가 1×1 인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 파악하는 기능이다. 두 기능을 구현해보자. 1. 드래곤 커브를 그리는 메서드 - drawDragonCurve 메서드 이 메서드를 구현하는 것이 상당히 어려웠다. 정확히 말하자면 구현이 어려웠다기보다는 드래곤 커브가 세대가 늘어날 때 추가되는 선의 규칙을 찾는 과정이 쉽지가 않았다. 세대가 늘어날때 드래곤 커브..
BOJ 14499 주사위 굴리기 [Java]
BOJ 14499 주사위 굴리기 1. 문제 링크 https://www.acmicpc.net/problem/14499 2. 문제 해설 구현 문제에서는 크게 어떤 기능을 구현해야할지를 우선적으로 생각하는 편이다. 하나의 명령의 흐름은 명령을 받으면 주사위를 굴리고 주어진 조건에 따라 값을 업데이트 해주는 것이다. 그러므로 구현해야할 기능은 크게 2가지이다. 첫번째는 주사위를 굴리는 메서드, 두번째는 주사위를 굴린 후 값을 업데이트 하는 메서드이다. 1. 주사위를 굴리는 메서드 - roll 메서드 주사위를 굴리는 건 노가다 방식으로 해결했다. 주사위 정보를 담고 있는 배열과 똑같은 배열을 하나 만들어준다. 그 후 이동하는 방향에 따라 바뀌는 주사위 정보를 바꿔준다. 2. 주사위를 굴린 후 값을 업데이트 하는 ..
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. 기준일보다 일찍 피는 꽃들 중에서 가장..