본문 바로가기

DP7

[ps java] BOJ 1149 RGB 거리 해설 DP를 학습할 수 있는 좋은 문제다! [실버1]https://www.acmicpc.net/problem/1149  문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.입력첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초.. 2025. 1. 31.
[ps java] BOJ 1912 연속합 해설 (카데인 알고리즘) DP를 학습하기 좋은 웰-노운 문제이다 [실버2] https://www.acmicpc.net/problem/1912 문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.출력첫째 줄에 답을 출력한다.예제 입력 11010 -4 3 1 5.. 2025. 1. 31.
[ps java] 재귀 -> DP 변환 예시 코드(BOJ 9184) https://www.acmicpc.net/problem/9184재귀를 DP로 바꾸는 문제이다 [실버2]재귀 호출만 생각하면 신이 난다! 아닌가요?  아래와 같은 재귀 호출 알고리즘 코드가 있다하지만 a b c 에 15 15 15 만 입력하더라도 실행하는 데에 너무 많은 시간이 걸린다따라서 우리는 아래의 코드를 DP로 변형해 볼 것이다import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); whi.. 2025. 1. 19.
[ps java] 피보나치 수열 알고리즘(재귀, DP) 우리가 일반적으로 알고 있는 피보나치 수열에 대한 재귀 알고리즘은 다음과 같다import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); System.out.println(fibonacci(n)); br.close(); } private static int fibonacci(int n) { if (n == 0) {.. 2025. 1. 19.
코딩테스트 빈출 유형 정리 [코딩테스트 주요 알고리즘]- 구현 및 시뮬레이션 - 문자열 처리(해시테이블 or 스택)- 완전 탐색(브루트 포스)- 이진 탐색(매개변수 탐색)- 그래프 탐색(DFS, BFS)- 백트래킹- DP- 그리디- 투포인터  [가끔 나오는 알고리즘]- 정렬- MST(크루스칼)- 최단경로(다익스트라, 벨만-포드, 플로이드-와샬)- 위상정렬- 모든 쌍 최단경로 문제- 분리집합- 트리의 지름 구하기- 트라이 2024. 8. 4.
[알고리즘] ep5-3++) 분할통치법 vs DP 문제) 여행의 최소비용을 구하는 알고리즘을 작성하라.airtelDC(분할통치 버전)와 airtelDP(동적프로그래밍 버전)를 구현하고 실행시간을 비교 프로그램 요구사항: 1)  각 해결버전의 정방향, 역방향 버전 가운데 자유롭게 하나를 선택하여 구현하라. 2)  출력예시: 최종적으로 다음과 같이 인쇄되어야 한다. ※ 참고1) 아래는 MAX = 30인 경우의 인쇄결과임.2) X.XXXXXXXX는 cputime in milliseconds.  주의:반드시 아래 가이드라인의 main 함수 내용과 동일하게 실행하고 출력을 구하라.n = 6로 한 테스트실행 결과가 수작업실행 결과와 일치하는지 확인한 후 n = MAX로 한 본실행을 시도할 것.경로가 아닌 최소비용만을 요구하는 문제이므로, 만약 최소비용 경로가 두 .. 2024. 7. 24.
[알고리즘] ep5-3) 방향그래프 ㅁ방향그래프(directed graph): 모든 간선이 방향간선인 그래프 응용: 일방통행 도로, 항공노선, 작업 스케줄링 방향 DFS 알고리즘에서, 네 종류의 간선이 발생한다1. 트리간선(tree edges): 새로운 정점 방문 시 사용되는 간선2. 후향간선(back edges): 현재 정점에서 이미 방문한 정점으로 돌아가는 간선3. 전향간선(forward edges): 조상의 정점에서 자손의 정점으로 향하는 간선4. 교차간선(cross edges): 같은 레벨 또는 다른 서브트리의 정점으로 향하는 간선 방향그래프 G의 두 정점 u와 v에 대해 만약 u에서 v로의 방향경로가 존재한다면, "u는 v에 도달한다(reach)" 또는 "v는 u로부터 도달 가능(reachable)하다"라고 말한다  방향그래프 G.. 2024. 7. 23.

티스토리툴바