baekjoon73 백준 알고리즘: 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. 백준 알고리즘: 2606번 바이러스 문제 정보 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 핵심 그래프 탐색 알고리즘을 통해서 연결된 노드를 탐색하는 것! 여러 그래프 탐색 알고리즘을 사용할 수 있겠지만, 나는 깊이 우선 탐색을 사용하여 풀이하였다 map을 어떻게 입력 받고 구성할 것이며 visited를 확인해주는 것이 매우 중요하다 하지만 그렇게 어렵지는 않았던 것 같다 풀이 package solving; import java.io.*; import java.util.*; class Main { public static void main(Str.. 알고리즘/Java 2023. 10. 25. 백준 알고리즘: 2178번 미로 탐색 문제 정보 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 핵심 BFS 알고리즘을 활용하여 문제를 풀이한다 큐를 사용할 때, Node 클래스를 만들어서 현재 위치와 Depth를 기록하고 이를 활용하였다 또한 현재 위치가 Invalid한지 확인하는 것, 갈 수 있는 위치인지(해당 Map의 값이 1인지) 확인하는 것 또한 빠뜨릴 수 있다 내가 가장 생각을 많이 했던 부분은 다음과 같다 while (!queue.isEmpty()) { Node popItem = queue.poll(); int row = popItem.row; int col = p.. 알고리즘/Java 2023. 10. 24. 백준 알고리즘: 1697번 숨바꼭질 문제 정보 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 핵심 ㅇㅇ 풀이 처음 풀이(실패) : DFS -> Timeout DFS 알고리즘을 활용하여 처음 풀이를 시작하였다 하지만 경우의 수가 무수히 많이 나오기 때문에, 전체 경우의 수를 모두 구하기에는 어려움이 있었던 것 같다 아무리 빨리 중단하도록 코드를 작성하여도, 결국에는 특정 조건에 만족하지 않으면 거의 모든 경우의 수를 확인해 봐야만 하기에 이 코드는 이 문제에서 효율적이지 않은 코드였다 import java.io.Buf.. 알고리즘/Java 2023. 10. 23. 이전 1 ··· 5 6 7 8 9 10 11 ··· 15 다음
