ALGORITHM (212) 썸네일형 리스트형 백준 7562 나이트의 이동 (Java) 1. 문제 링크 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 나이트가 움직이는 8방향으로 bfs 탐색을 진행한다. 최소 횟수로 움직여야 하기 때문에 방문했는지 확인하기 위해 visit 배열을 이용했다. 사실 1331번 나이트 투어를 풀려고 하는데 나이트가 어떻게 움직이는지 몰라서 이 문제를 먼저 찾아왔다...ㅎ 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util... 백준 4485 녹색 옷 입은 애가 젤다지? (Java) 1. 문제 링크 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 그냥 풀어도 통과는 하지만 dp로 풀었을 때 메모리와 시간 측면에서 훨씬 향상된 모습을 볼 수 있다. 1번 풀이는 완전탐색이고 215676KB 792ms 라는 결과가 나왔다. 2번 풀이는 dp 이고 17848KB 180ms라는 결과가 나왔다. 4. 코드 1. 1번 풀이 import java.io.BufferedReader; import java.io.InputStreamReader; im.. 백준 4963 섬의 개수 (Java) 1. 문제 링크 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 8방으로 bfs 탐색을 진행한다. 섬의 시작이 어디부터인지 몰라서 8방으로 진행했다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.io.IOException; public class Main { stati.. 백준 2580, 2239 스도쿠 (Java) 1. 문제 링크 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 두 문제가 입출력의 공백 차이 뿐이라 함께 가져왔다. dfs 느낌으로 이 숫자일 때 다음 숫자가 가능한지 그 다음은 가능한지... 의 순서로 코드를 진행한다.. 백준 1194 달이 차오른다, 가자 1. 문제 링크 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 비트마스킹을 해야 하는 문제라 조금 어려웠다. 시작점부터 BFS 하면서 해당 위치가 벽/열쇠/문/출구인지에 따라 다른 조건문에 들어간다. 출구가 나오면 최댓값을 갱신하고 return한다. 빈 칸인 경우에는 갈 수 있는 곳이므로 queue에 넣는다. 열쇠가 나올 경우 비스마스킹으로 키를 추가하고 갈 수 있는 곳이므로 queue에 넣는다. 대문자일 경우 해당 문자열을 키가 가지고.. 백준 2632 피자 판매 (Java) 1. 문제 링크 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 피자 조각별 크기를 입력받고 저장하면서 총 크기를 저장한다. 연속적으로 피자 조각을 더해야 하기 때문에 DP 느낌으로 생각했다. 시작 숫자에 따라 연속적으로 이어질 때 항상 마지막 경우는 피자 전체를 의미하기 때문에 뺐다. 피자 전체 조각에서 i+j를 나눠서 배열을 2배 길게 넣은 느낌으로 풀었다. 그때 나온 값이 원하는 크기보다 작으면 해당 크기의 dp를 한다. 두 피자로 각각 만들 .. 백준 1005 ACM Craft (Java) 1. 문제 링크 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 건설 순서가 우선되는 것이 있어서 위상정렬을 한다. 위상 정렬을 하면서 큐에서 꺼낼 때 dp를 다. dp에 있는 값과 지금 온 값 중 더 큰 시간을 저장하면 문제에서 원하는 결과를 얻을 수 있다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.uti.. 백준 17472 다리 만들기 2 (Java) 1. 문제 링크 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 bfs를 이용해 섬을 구분하여 각각 몇번째 섬인지 저장한다. 섬 사이 거리는 dfs를 이용해 다른 섬이 나올 때까지 한다. 그 거리 중 1이 아닌 최소 거리를 저장한다. 최소 스패닝 트리를 이용하여 모든 섬을 연결하는 최소 길를 구한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu.. 이전 1 ··· 7 8 9 10 11 12 13 ··· 27 다음
