늘 겸손하게

안녕하세요 besforyou입니다. 백준 문제 1260 소개를 시작하겠습니다. 문제 풀이 입력받은 정점과 간선들로 그래프를 생성하고 DFS search, BFS search를 해주면 된다. DFS 탐색 방법 : https://besforyou.tistory.com/122 Depth First Search for a Graph - 그래프 깊이-우선 탐색 안녕하세요 besforyou 입니다 이번 글에서는 그래프의 DFS에 대해 소개하겠습니다. 출처 : https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/ Depth First Search or DFS for a Graph - Geek.. besforyou.tistory.com BFS 탐색..

문제 풀이 그리디 알고리즘을 적용하여 해결 가능합니다. 봉지가 담을 수 있는 무게는 3kg와 5kg 두개이고 설탕의 최대무게는 N이다. 3kg 봉지와 5kg 봉지로 무게 N을 맞출 수 있는 조합을 모두 구한 뒤 3kg 봉지 개수와 5 kg 봉지 개수의 합이 가장 작은 것을 찾아 출력하면 됩니다. 3kg 봉지와 5kg 봉지의 조합은 반복문으로 찾을 수 있습니다. 코드 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import java.util.Scanner; public class Main { public static void main(String [] args) { Scanner sc = new S..

안녕하세요 besforyou 입니다 문제 풀이 어린이들이 줄 서있을때 어린이들의 최소한의 이동으로 줄 정렬을 시킬 수 있는 경우의 이동 횟수를 구하고 싶은것이 문제이다. 이 문제를 쉽게 풀기 위해서는 최소한의 이동 방법을 찾는것이 아니라, 전체 어린이 수에서 연속된 배열의 길이를 빼면 되는 문제이다. 예로 어린이들이 아래와 같이 줄을 섰다고 가정해보자. 2 5 6 1 3 4 여기서 가장 긴 연속된 배열은 2 5 6 1 3 4 2 , 3, 4 이다. 즉 2, 3, 4는 그대로 놔두고 5, 6, 1의 자리만 바꾸어주면 되는것이다. 따라서 정답은 전체 어린이 수 - 가장 긴 연속된 배열이다. 가장 긴 연속된 배열은 dp 로 구한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..

안녕하세요 besforyou입니다 백준 문제 10709번 문제 풀이를 설명하겠습니다 문제 풀이 c가 나온 지점으로부터 오른쪽으로 얼마나 떨어져 있는지를 알아내어 출력하는 문제입니다. 이 문제에 dp 알고리즘을 적용하면 O(H*W) 시간안에 풀어낼 수 있습니다. 1. 구름의 위치 입력값을 받을 2차원 배열 cloud와 정답을 기록할 2차원 배열 ans를 생성합니다. 2. 2차원 배열 ans의 모든 원소값은 -1로 초기화합니다. (memset 이용) 3. 2차원 배열 cloud에 모든 입력값을 저장합니다. 4. for문을 이용하여 cloud의 모든 원소를 순차적으로 참조하는데, 1. 해당 cloud 좌표에 c가 있는 경우 : 0 2. c가 참조되지 않았지만 이전 원소가 -1이 아닌 경우(c가 이전에 이미 읽..