전체 글1316 [백준] 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. [알고리즘] 탐욕법 (Greedy Algorithm) • 그리디 알고리즘이란? 각각의 수행시점에서 가능한 해 중 가장 최적해를 찾아 나가는 알고리즘. 즉 근시안적인 최적해를 찾는다고 할 수 있으며 이러한 근시안적 최적해들을 모아서 최종적으로 문제의 최적해를 구한다. 그러나 경우에 따라 수행시점마다의 선택이 해당 시점에 대해서는 부분적으론 최적이지만, 그 선택들을 수집해 최종으로 도출한 해답이 전체적으로 최적이라는 보장은 없다. 위의 예시에서 해당 트리를 그리디로 접근 시 가장 큰 수는 6이라는 결과가 나오지만 실제로 가장 큰 수는 99이므로 그리디 알고리즘이 최적해를 구하지 못하게 된다. • 그리디로 접근하여 최적해를 구하기 위해 2가지 조건 1) 탐욕적 선택 속성 (Greedy Choice Property) : 이전의 선택이 이후에 영향을 주지 않음. 2.. 2022. 5. 3. 이전 1 ··· 216 217 218 219 220 다음
