백준71 백준 알고리즘: 7576번 토마토 문제 정보 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 핵심 역시 이전 문제와 비슷한 BFS(너비 우선 탐색)을 활용하여 풀이하는 문제이다 이 문제에서 하루가 지나면 익은 토마토의 상하좌우의 익지 않은 토마토들은 익은 토마토로 변하게 되는데, 모든 익지 않은 토마토가 익은 토마토가 될 때까지의 최소 날짜를 출력하는 것이다 하지만, 1. 익지 않은 토마토(0)가 모두 익은 토마토(1)로 변했음을 어떻게 파악할지 2. 익은 토마토로 변했을때 최소 날짜는 어떻게 카운팅하는 것이 좋을지 이 두가지.. 알고리즘/Java 2023. 11. 14. 백준 알고리즘: 2206번 벽 부수고 이동하기 문제 정보 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 핵심 얼마나 효율적으로 케이스를 분리해서 문제를 풀이하는가.. 가 중요한 것 같다 (모든 문제가 그렇지만) 이 문제는 BFS(너비 우선 탐색)을 활용하여 풀이하는 문제이며 모든 경우의 수를 확인해야 하는 문제가 아니고 최단 거리를 구하는 문제이기 때문에 DFS는 적합하지 않을 것 같다는 판단을 하였다 중간에 막혔던 부분이 있고, 그 부분을 해결해 나갔던 과정과 함께 풀이를 해보도록 하겠다 살짝 소개하자면, 벽은 반드시 한 개만.. 알고리즘/Java 2023. 11. 13. 백준 알고리즘: 1149번 RGB거리 문제 정보 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 핵심 DP 알고리즘으로, 점화식을 어떻게 세우는지가 중요한 것 같음 해당 문제의 경우에는, 결국 이전 집의 색이랑 같지 않으면 되기 때문에 현재 위치에서 만약 빨간색(R)을 골랐다면? dp[현재위치][빨간색 선택] = (dp[직전위치][파랑색 선택], dp[직전위치][초록색 선택]) 중 최소값 + 현재위치에서 빨간색을 선택할 때의 비용 이 된다 그러므로 이를 Java 언어로 점화식을 작성해 보면 (0: R, 1:G, 2:B) dp.. 알고리즘/Java 2023. 11. 13. 백준 알고리즘: 1465번 1로 만들기 문제 정보 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 핵심 효율적인 알고리즘의 구현 풀이는 두가지 방식으로 진행해 보았다 - BFS(Breath First Search) - DP(Dynamic Programming) - Bottom-up 방식 이 문제를 풀이하는데에 더욱 효율적인 알고리즘은 DP였으며 많이 접하지 못했던 유형이라 언제 이러한 알고리즘을 적용시켜야 하는지에 대해서 알게 되었던 것 같다 추가로 Top-down 방식의 풀이도 존재하는데, 더 효율적인 풀이가 있을 것 같아서 이에 대해서는 공부를 좀 더 하고 올리려고 한다 풀이 1. BFS를 활용한 풀이 import java.io.*; import java.u.. 알고리즘/Java 2023. 10. 25. 백준 알고리즘: 1003번 피보나치 함수 문제 정보 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 핵심 피보나치는 역시 DP(Dynamic Programming) 아닐까요? 피보나치의 특징인 f(n) = f(n-2) + f(n-1) 는 다음을 의미하기도 합니다 f(n)을 이루는 0의 개수와 1의 개수 = f(n-2)를 이루는 0의 개수와 1의 개수 + f(n-1)을 이루는 0의 개수와 1의 개수 따라서, 일반적인 피보나치 풀이처럼 풀되 0의 개수와 1의 개수를 더해가며 풀이하면 쉽게 풀이할 수 있을 것! 내 풀이의 경우 Fibo class를 만들어서, instance variable로 numberOfZero(0이 나타나는 개수)와 numberO.. 알고리즘/Java 2023. 10. 25. 이전 1 ··· 4 5 6 7 8 9 10 ··· 15 다음
