DP26 [백준 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. [백준 16930] 달리기 / 자바 / bfs + dp #문제 레벨: P3알고리즘: bfs 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/16930#문제 풀이 위 문제는 dp + bfs(우선순위 큐) 문제이다. 기존 비슷한 문제와 다른 점은 1초에 1칸 움직이는 것이 아니라 1 ~ K 개수 만큼 이동할 수 있다는 거다. 그래서 우선순위큐를 사용하더라도 해당 위치에 도달하기 까지가 최소 이동횟수가 아닐 수도 있다. 최소이동횟수가 아닐 것을 이용해 계속 탐색하면 의미가 없지 않은가?(시간초과) 그래서 우린 이때, dp를 도입하는 거다. dp를 도입하여 각 칸에 도달한 최소 이동횟수를 적어준다. 그보다 많다면 break해줘 탐색시간을 줄이는 거다.#풀이 코드 import java.i.. 2024. 8. 13. [백준 2186] 문자판 / 자바 / dp + dfs #문제 레벨: G3알고리즘: dp + dfs풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/2186#문제 풀이 처음 문제를 봤을 때 별 생각없이 아래와 같이 dfs 코드를 짰다. 코드는 문제에 맞게 구현됐다. 단지, 시간 초과가 날 뿐이다...잠시 이 dfs 코드를 흝어봐주고 내려와주라.dfs코드import java.io.*;import java.util.*;public class Main { static int N, M, K; static char[][] board; static String word; static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, .. 2024. 8. 11. [백준 1103] 게임 / 자바 / dfs + dp #문제 레벨: G2알고리즘: dfs + dp풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/1103#문제 풀이 dfs+dp 코드 구현은 워낙 다양하다. 그래서 자기에게 맞는 코드를 찾아야 한다. 자기가 이해하기 쉬운 코드를 짜야한다. visited배열이 언제 true,false가 되고 dp 값이 어떻게 언제 채워지는지 정확히 이해해야 한다.아래 코드는 한 번씩 이동할 때마다 dp배열에 +1씩 새긴다. 만약 dp 배열에 값이 지금 새겨넣으려는 값보다 큰 경우 그 경로에서는 탐색을 멈춘다. 왜냐하면 이미 이전에 깊이 탐색했다는 뜻으로. vsited배열은 무한루프를 탐색하기 위함이기 때문에 다른경로에 영향을 주면 안된다. 한 경로에서 .. 2024. 8. 3. [백준 2098] 외판원 순회 / 자바 / dp + 브루트 포스 ** #문제 레벨: G1알고리즘: dp + 브루트 포스 + 비트 마스킹풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2098#문제 풀이 TSP(Traveling Salesman Problem)시간 복잡도 O(n^2 * 2^n)모든 경우의 수를 살펴봐야 하는 문제임은 확실하다. 그러나 최악의 상황을 가장해보면 16!이다. 20조 9,227억 8,988만 8천이라는 것이다. ( 11! = 39,916,800 (약 3.99 × 10^7) 안에 들어야 시간복잡도에 통과할 수 있다.) 브루트 포스는 확실한데 시간이 걸린다면 dp 도입을 의심하면 된다. dp + dfs 는 postorder로 코드 구현한다. dp를 재귀함수로 구현하려면 값이 저장된.. 2024. 7. 12. [백준 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를 한다. 특이점은 dfs를 하며 방문한 위치값은 값을 새겨놓고 다시는 방문하지 않는다. 다른 dfs루트로 그 위치를 방문했을 때는 전에 얻어놓은 값을 쓴다. dp[][] 배열 채워지는 과정33 7 5 //입력값1 2 46 8 2210000 //1번째 dp000210000 //2번째 dp000212000 //3번째 dp000212543 //4번째 dp210212543 //5번째 dp210212543 //6번째 dp.. 2024. 7. 10. 이전 1 2 3 다음
