분류 전체보기1323 [백준] 1931 회의실 배정 - Greedy / Java • 문제 링크 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net • 풀이 과정 • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; public class Main { public static void main(String[] ar.. 2022. 5. 8. [백준] 2217 로프 - Greedy / Java • 문제 링크 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net • 풀이 과정 • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.StringTokenizer; public class .. 2022. 5. 6. [알고리즘] 동적 계획법 (Dynamic Programming) • 동적 계획법이란? 복잡한 문제를 풀기 위해서 여러 개의 하위 문제로 분해하여 결과를 저장한 후, 그것을 결합하여 최종적인 목적에 도달하는 알고리즘 최적화 기법이다. Dynamic Programming 이라는 다소 과하다 싶은 명칭의 어원은 1950년대 수학자 Richard Bellman에 의해 고안되었다. 당시 ”Programming”이라는 말은 실제로 컴퓨터의 코딩처럼 프로그래밍을 의미하는 것은 아니었다. 이때 프로그래밍이 의미하는 것은 "계획"과 "결정"이었다. ”Dynamic” 이라는 단어는 벨먼이 문제의 시가변적이며 다단계적인 특성을 포착하기 위함으로써 선택했고, ”Programming” 은 훈련이나 군수 물자 운송을 위한 최적의 프로그램을 찾기 위해 특정 방법을 사용하는 것을 가리키는 용어였.. 2022. 5. 6. [백준] 1890 점프 - Dynamic Programming / Java • 문제 링크 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net • 풀이 과정 이 문제의 경우 게임판과 메모이제이션할 배열을 따로 입력받지 않아도 풀이가 가능하다. 우선 n + 1 * n + 1 크기의 dp 배열을 생성하고 dp[1][1] = 1 로 시작점을 초기화한다. 반복문에서 dp[i][j] 가 0일 경우, 해당 위치로 이동 가능한 경우의 수가 1개 이상이 아님을 의미하므로 처리하지 않는다. 입력받은 dist 값은 현재 위치에서 이동 가능한 거리이며 우측, 하단 방향으로 그 거리만큼 이동했을 때.. 2022. 5. 5. [백준] 15486 퇴사 2 - Dynamic Programming / Java • 문제 링크 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net • 풀이 과정 아래 링크는 n의 범위가 다르지만 내용은 같은 문제로 완전 탐색으로 풀이했고 이번엔 DP로 풀이했다. [백준] 14501 퇴사 - Brute Force / Java • 문제 링크 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net • 풀이 과정 해당 문제는 재귀를 활용하여 완전 탐색(Brute Force) 으로 해결하거나 동적 계획법(DP graycod.. 2022. 5. 4. [백준] 14501 퇴사 - Brute Force / Java • 문제 링크 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net • 풀이 과정 해당 문제는 재귀를 활용하여 완전 탐색(Brute Force) 으로 해결하거나 동적 계획법(DP) 으로도 해결 가능하다. 아래 링크에서 내용은 같지만 N의 범위가 넓은 "퇴사 2" 는 DP로 해결했고 이 문제는 완전 탐색으로 풀이했다. [백준] 15486 퇴사 2 - DP /Java • 문제 링크 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ P graycode.tistory.com 우선 총 상담.. 2022. 5. 4. 이전 1 ··· 217 218 219 220 221 다음
