Algorithm/Baekjoon12 [백준] 2631번: 줄세우기-자바(Java) / LIS, DP, 이분탐색 📍 문제 링크 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 📍 문제 접근 위치를 옮기는 아이들의 수가 최소이다. => 주어진 순서에서 순서가 올바른 가장 긴 부분을 찾고, 그 외의 아이들을 옮기자. => dp배열을 이용하여 LIS를 구하는 문제 => 이분탐색을 이용해서도 풀어보자! 📍 코드 보기 // dp배열을 이용한 LIS 구하기 방법 // dp[i] : i번째 수를 끝으로 하는 최장길이 public class Main { static Buffe.. 2022. 4. 28. [백준] 2629번: 양팔저울-자바(Java) / DP 📍 문제 링크 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 📍 문제 접근 입력조건은 다음과 같다. 추의 개수: 30개 이하, 추의 무게: 500g 이하 구슬의 개수: 7개 이하, 구슬의 무게: 40000g 이하 따라서 추로 만들 수 있는 최대의 무게는 15000g이 된다. (모든 추가 500g이라고 가정) 초과된 범위의 구슬은 무조건 구할 수 없다는 것을 생각하지 못해서 ArrayIndexOutOfBounds 에러가 났었다. 추를 가지고 할 .. 2022. 4. 25. [백준] 1926번 그림 - 자바(Java) / bfs&dfs 📍 문제 링크 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 📍 문제 접근 그림은 1로 표시되어 있고, 가로나 세로로 연결된 경우 하나의 그림이다. 이차원 배열로 도화지를 선언하고, 인접한 위치 중에 1인 경우 탐색한다. => bfs, dfs 그림의 넓이 => 변수를 선언하여 탐색할 때마다 증가시키고, 탐색 종료 후 최대값을 갱신하자. 그림이 하나도 없는 경우 넓이를 0으로 출력해야 한다. 📍 코드 보기 public class BOJ_S1_1926.. 2022. 4. 22. [백준] 1003번 : 피보나치함수 - 자바(Java) / 다이나믹프로그래밍(DP) 📍 문제 링크 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 📍 문제 접근 처음엔 i번째 피보나치 수를 호출할 때, 호출되는 0과 1의 출력횟수를 담는 이차원 배열 dp를 만들려고 했다. 이 때의 점화식은 다음과 같다. dp[i][0] = dp[0][i-1] + dp[0][i-2] dp[i][1] = dp[1][i-1] + dp[1][i-2] 위와 같은 접근으로 dp 배열을 채우던 중 또 다른 규칙을 발견했다. dp 0 1 2 3 4 5 6 7 .. N 0 1 0 1 = fibo(1) 1 = fibo(2) 2 = fibo(3) 3 = fi.. 2022. 4. 20. 이전 1 2 3 다음