알고리즘/DP31 [백준 7579] 앱 / 자바 / dp(기초) #문제 레벨: G4알고리즘: dp(기초)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/7579 #문제 풀이 dp에 담기는 것은 i의 비용으로 비활성화하는 앱들의 비용 합계를 나타낸다.M으로 dp배열을 만들면 메모리 초과가 날 것을 직관적으로 알 수 있다. dp 배열을 cost로 잡는다. 이 dp는 이차원배열 풀이와 일차원 배열 풀이가 있다.이차원 배열 풀이dp[i][j] 에서 i는 1~i 앱까지 탐색했는지 나타내고 j는 cost를 나타낸다. 즉, dp 배열은 1 ~ i번까지 탐색하여 cost j를 이용하여 최대한 비울 수 있는 메모리를 나타낸다. 일차원 배열 풀이dp[i]에서 i는 i의 cost가 주어졌을 때 최대한 비울 수 있는 .. 2024. 8. 30. [백준 9095] 1, 2, 3 더하기 / 자바 / dp #문제 레벨: S3알고리즘: dp풀이시간: 30분 힌트 참조 유무:https://www.acmicpc.net/problem/9095#문제 풀이 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]이와 같은 점화식이 세워진 이유는 이러하다. dp[4] = dp[3] + dp[2] + dp[1] 를 예시로 들어 설명해보겠다. dp[1] = 1; // 1 dp[2] = 2; // 1+1, 2 dp[3] = 4; // 1+1+1, 1+2, 2+1, 3dp[4]는 dp[1] 마지막에 3을 붙이면 되고 dp[2] 마지막에 2를 붙이면 된다. dp[3] 마지막에 1를 붙이면 된다.1+31+1+2, 2+21+1+1+1, 1+2+1,.. 2024. 8. 25. [백준 1149] RGB거리 / 자바 / dp(기본) #문제 레벨: S1알고리즘: dp(기본)풀이시간: 30분힌트 참조 유무:https://www.acmicpc.net/problem/1149#문제 풀이 위 문제느 dp 기본 문제이다. 점화식을 도출하고 그를 코드로 구현하는 것이다. 위 문제의 점화식은 아래와 같다. // 빨강으로 칠할 경우 dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + costs[i][0] // 초록으로 칠할 경우 dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + costs[i][1] // 파랑으로 칠할 경우 dp[i][2].. 2024. 8. 23. [백준 2533] 사회망 서비스 / 자바 / dp + dfs #문제 레벨: G3알고리즘: dp + dfs 풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/2533#문제 풀이 dp와 dfs를 섞은 문제이다. 이 문제에서 얻을 수 있는 점은 두가지이다.첫 째, 그래프를 배열로 표현하는 것. 둘 째, 큰 문제를 작은 문제로 쪼개는 방법.셋 째, vistied배열 대신 parentNode로 판별하는 방법(중복 탐색 예방)넷 째, dp 구현방식위 문제는 dp[node][0], dp[node][1]를 가지는 이차원 배열로 풀어내야 한다. 가장 아래에 있는 리프 노트부터 시작하여 루트 노드의 dp 값을 채우는 방식이다. 예를 들면 dp[5][0] 은 노드 5가 얼리어답터가 아닐 때이다. 그러니 반드시 부모(.. 2024. 7. 11. [백준 1937] 욕심쟁이 판다 / 자바 /dp #문제 레벨: G3알고리즘: dp풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/1937#문제 풀이 위 문제를 순수 dfs 코드로 풀면 O(n x n x n x n)입니다. 값을 대입해보면 500 x 500 x 500 x 500 = 625억입니다. 시간제한은 2초이므로 2억 초과인 625억은 시간제한 초과입니다. 특별한 규칙이 없으니 dfs임은 확실하고 시간복잡도를 줄이기 위해서 dp를 도입해야 합니다. dp를 도입한다는 것은 이미 방문한 경로는 반복해서 가지 않는 것을 의미합니다. 그럼 각 배열을 한 번씩만 방문하면 되기 때문에 시간 복잡도는 O(n x n)입니다. 이만 오천으로 넉넉히 통과할 수 있습니다. (한 번씩만 방문하면 되므로.. 2024. 7. 10. [백준 11066] 파일 합치기 / 자바 /dp #문제 레벨: G5알고리즘: dp 풀이시간: 1힌트 참조 유무:https://www.acmicpc.net/problem/11066#문제 풀이 그리드 문제로도 착각할 수 있지만 연속된 파일들만 합칠 수 있기 때문에 그리드 문제는 아니다. (그리드 문제라면 파일을 합치고 정렬하고 합치고를 반복하기 때문에 연속된 파일임을 보장하지 않음) dp[i][j] = i ~ j까지 파일 합쳤을 때 최솟값+행은 시작인덱스를 나타내고 열은 끝인덱스를 나타낸다.{2,3}이면 2에서부터 3까지 더했을 때 최솟값이다. dp 배열을 이 방향으로 채워진다. 빨간색 숫자는 채워지는 순서를 뜻한다. 아래 코드르 보면 알겠지만 이중 for문이 뜻하는 것은 파란색 방향을 말하는 것이다.가장 깊숙히 있는 fo.. 2024. 7. 10. [백준 14002] 가장 긴 증가하는 부분 수열4 / 자바 / dp #문제 레벨: G4알고리즘: dp풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14002#문제 풀이 [1번째 시도: 실패]멍청한 풀이. 시간복잡도 n으로 풀 수 있지 않을까? 그리드 형식으로 랭킹을 매기는 방식. 혹시 나와 같은 사람이 있을까봐 기입해두었다. skip해도 된다.package project;import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(.. 2024. 7. 10. [백준 17070] 파이프 옮기기1 / 자바 / dp #문제 레벨: G5알고리즘: dp 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/17070#문제 설명 문제에서 놓칠 수도 있는 부분 몇 가지만 짚고 넘어가겠습니다.1. 파이프는 90~180도까지 +45도 or -45만 움직일 수 있다.2. 대각선 파이프는 4칸을 차지한다. 그 4칸 중 벽(1)이 있으면 안 된다. 이 문제는 dfs 또는 dp로 풀 수 있습니다. dfs로 풀 수 있는 이유는 입력최대값이 작아서 그렇습니다. 저는 dp를 공부중이기 때문에 dp를 사용해서 풀겠습니다. #알고리즘 설명 dp를 알려면 이 유형은 꼭 알아두었으면 좋겠습니다. 이 문제에서 어떻게 dp를 이용하냐면, 각 위치에 도착할 수 있는 경우의 수를 담는 것입니.. 2024. 7. 10. dp 뿌시기 1(feat 양치기) 이 글은 고급 알고리즘인 dp의 이해를 위해 작성하였습니다. 다른 알고리즘 같은 경우 설명과 코드를 보면 이해가 단 번에 이해가 갔지만, dp의 경우에는 일반적 사고와는 달라 이해하기 쉽지 않았습니다. 이를 위해 dp의 다양한 유형을 분석하므로써 dp의 사고흐름을 정확히 이해하기 위해 작성하였습니다. 아래 문제들은 백준 골드 정도 되는 문제들로 구성되어있습니다. 문제풀이에서 가장 중요한 건 어떤 알고리즘인지 파악하는 게 중요하기 때문에 dp문제라는 것을 미리 알고있지만, 문제를 처음 보았을 상황을 가정해서 dp 문제풀이를 해보도록 하겠습니다. 또, 하나 dp의 사고과정을 위해 작성한 글이기 때문에 코드를 직접 작성하지 않겠습니다. #1번째 문제: 백준10942 팰린드롬?https://www.acmic.. 2024. 7. 9. 이전 1 2 3 4 다음
