전체 글1273 [알고리즘] 동적 계획법 (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. [백준] 11399 ATM - Greedy / Java • 문제 링크 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net • 풀이 과정 앞 사람의 인출시간이 짧을수록 뒤의 인원이 부담해야 할 시간이 줄어드므로 소요시간을 오름차순으로 정렬한다. 이 후 인원 당 소요된 시간을 앞 사람이 소요한 시간까지 포함해 누적한 값으로 temp 변수에 구하고 각각 cnt 변수에 모두 더해 필요한 시간의 합의 최솟값을 구한다. • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import ja.. 2022. 5. 2. 이전 1 ··· 209 210 211 212 213 다음
