전체 글
BOJ 1939 중량제한 [Java]
BOJ 1939 중량제한 1. 문제 링크 https://www.acmicpc.net/problem/1939 2. 문제 해설 처음에는 실수로 시간복잡도를 생각 안하고 접근했다. 공장이 있는 섬 두 개 중 한 지점에서 다른 지점까지 갈 수 있는 모든 경로를 살펴보면서 각 경로마다의 최소의 중량제한을 구하고, 그 값의 최대값을 구하는 방식을 dfs로 구현하였다. 시간복잡도가 O(NM)으로 당연히 시간초과가 나왔다. 시간복잡도를 줄일 수 있는 방법이 무엇이 있을까 고민하다가, 각 다리의 중량제한의 범위가 1 ≤ C ≤ 1,000,000,000 으로 굉장히 큰 것을 보고 이분탐색을 떠올렸다. BFS와 이분탐색을 이용해서 풀 수 있는데, 각 로직의 흐름을 설명해보겠다. 이분탐색 로직 이분탐색을 할 대상은 물품의 중..
프로그래머스 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번째 줄의 코드이다. 몇 번째 톱니바퀴를 돌릴지, 어떤 방향으로 돌릴지 알아야하므로 인자로 받는다. 시계 방향이든 반시계 방향이든 결국 한칸씩 옆으로 옮기는 것이다. 그러므로 기존 톱니바퀴와 정보가 똑같은 임시 톱니바퀴 배열을 만들어 이용해준다. 시계 방향일때와 반시계 방향일때 처리해주는 방..