Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처최적의 행렬 곱셈 level 3📖 문제 DP로 풀은 문제행렬의 곱을 복습하자면 A(3X5) 와 B(5X7)의 크기의 행렬이 있을때 구 행렬을 곱하면AB = 3X5X7 이된다. 행렬 A, B, C... 이렇게 있을 때ABCD를 만드는 조합은ABC DAB CDA BCD 이렇게 3가지 가 있고ABCDE는 A BCDEAB CDEABC DEABCD E4가지가 있다 여기서 규칙성을 찾을 수 있고 이를 점화식으로 나타낼 수 있다.시작과 끝을 지정하고, 중간을 지정해서 분할한 후 최소값을 찾는 것이다.// A: s,mid까지 곱한 행렬의 행 크기, B: mid+1,e 까지 곱한 행렬의 열 크기DP[s][e] = min(DP[s][mid] + DP[mid+1][e] + multiply(A..

🧫 문제 분석 ✔️ 출처점프 골드 4 📖 문제 dp 문제갈 수 없는 돌들이 있으므로 여러가지 경우의 수가 있기에 가장 먼저 출발한 것이 먼저 도착하는 것이 아니다.각 돌에 도착할때 몇 점프로 도달했는지를 체크해줄 필요가 있다. 따라서 2차원 DP로 풀어야하는데 N*N 은 너무 커서 문제 조건에 맞지 않는다. 점프를 해도 결국 연속으로 누적된 x + 1이 가장 클 것이므로 연속으로 x + 1 이 누적되었을때 1만까지의 값은 142 정도이다.넉넉하게 150으로 잡았다. 따라서 2차원 DP는 몇칸으로 현재 번호의 돌에 도착했는지 체크하면서 몇 번 점프했는지 값을 찾는다.dp[현재 돌][몇 칸 점프해서 왔는지 점프 길이 : x] 탐색에는 BFS 탐색을 사용한다. x-1, x, x+1 칸으로 점프하는 각각..

🧫 문제 분석 ✔️ 출처내리막 길 골드 3 📖 문제 나의 가장 약한 부분인 DP 연습 기간을 잡아 DP문제를 풀어보려한다. DFS + DP로 풀었다.중복 탐색 방지를 위해 static으로 방문처리 배열을 만들어서 처리했다.약간 백트래킹 느낌으로 BFS + 우선순위 큐 풀이도 있다고 한다.생각해보면 탐색은 점점 높이가 낮은 곳으로 이동하므로 높이가 낮은 순으로 큐에 넣으면중복없이 풀어낼 수 있다는 것이다. 탐색 조건에 뭔가 우선순위를 매길 수 있다면 우선순위 큐를 떠올려 보자 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int N, M; static int[][] dp; static int[][] ..

🧫 문제 분석 ✔️ 출처사수빈탕 골드 5 📖 문제 DP문제로 주어진 사탕 바구니 위치로 이동하며 최대 개수를 구하는 문제 한 번 움질일때마다 사탕바구니의 사탕이 -1이 된다. 사탕 바구니를 x,y로 오름차순 정렬해서 DP + DFS 탐색한다. 다른 사람풀이를 보니 bottom-up 으로 푸는 방법도 있다.🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int n, m; static int[][] arr; static int[][] dp; public static void main(String[] args) throws IOException { BufferedReader br = new..

🧫 문제 분석 ✔️ 출처도미노 (Small) 골드 1 📖 문제 DP 풀이 문제였는데나는 우선순위 큐로 풀었다. 각 도미노가 넘어뜨릴 수 있는 최대개수를 구하고우선순위 큐에 넣은 다음 가장 많이 쓰러뜨린 도미노 먼저 꺼낸후해당 도미노를 넘어뜨렸을 때 넘어진 도미노들을 방문체크한다.이를 반복하면 된다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static class Domino { int x, h; long left, right; public Domino(int x, int h) { this.x = x; this.h = h; ..

🧫 문제 분석 ✔️ 출처N포커 골드 2 📖 문제 포함 배제 원리에 대해 배우게 되었다. 말그대로 여러 집합을 합칠때 중복을 빼는 것이다. 짝수 집합일 경우 빼주고홀수 집합일 경우 더한다.세 집합 A,B,CA, B, CA,B,C 면:→ 더하고 빼고 반복. 벤다이어그램으로 봤을때2번째 짝수번째 빼기를 보면3번 빼서 AnBnC가 없어진다따라서 세 집합의 교집합을 더한다. 최종적으로 중복ㅇ벗는 하나의 영역만 계산된다.|B| + |C| + |D| 이경우 BnC가 2개AnB 2개AnC 2개 때문에 1개씩 빼줌 하지만 이러면 AnBnC가 사라짐AnBnC 더함 최종적으로 중복없는 합 집합 생성 🔅 문제 풀이import java.io.*;import java.sql.SQLOutput;import java.uti..

🧫 문제 분석 ✔️ 출처사회망 서비스 (SNS) 골드 3 📖 문제 DP 문제트리를 이용한 DP 문제는 처음이라 좀 어려웠다 처음에는 엣지가 많은 노드 순으로 연결 해제 여부를 따지며 선정하면 되지않나 싶었는데불가능한 케이스가 있어서 바꿨다. 현재 노드를 얼리 아답터로 선정할지 안할지에 대해서 탐색하면된다.DFS+DP 식으로 풀어서 별로일 수 있다. 또한 입력을 받을 때 주의해야한다.방향성을 가지면 안되며 양방향으로 트리를 만들어야한다.그 이유는 단방향시 루트를 가지는 트리가 되는데 이러면 방향에 따라 값이 달라진다. 51 52 12 32 4이런 입력이 들어오면 1을 루트로 설정시2를 탐색할 수 없다. 때문에 양방향으로 설정해야한다. 루트를 1 기준으로 입력이 들어온다는 생각때문에이런 실수를 했다...

🧫 문제 분석✔️ 출처Four Squares 실버 3 📖 문제DP문제 1~n-1까지의 four squares를 구하고 n의 four squares 를 구한다. 단순히 현재 자신의 최대 제곱근의 제곱을 자신의 수에서 뺀 나머지의 four squares를 이용하면 틀린다. 12의 경우최대 제곱근은 3이며 12 - 9 = 3 이므로 dp[3] 의 값을 더해주면 dp[3] (3) + 3^3(1) = 4개 로 최소가 된다 싶겠지만 2^2 + 2^2 + 2^2, 단 3개만으로 12를 완성할 수 있다. 때문에 해당 수의 1~최대 제곱근까지를 탐색해야한다. 점화식dp[i] = Math.min(dp[i - (j*j)] + 1, dp[i]) [i = 2~N , j = 1 ~ sqrt(i)] 🔅 문제 풀이imp..

🧫 문제 분석 ✔️ 출처할로윈의 양아치 골드 2 📖 문제2차원 DP로 좀 많이 복잡하게 풀었다.시간 제한 거의 닿을정도로 ㅋㅋ.. 유니온-파인드Set + 넵샥 알고리즘으로 풀었다.그리고 다른사람 풀이를 봤더니 1차원으로 충분히 가능하다는 것이다. 이번 풀이의 문제점Set으로 아이들의 값을 굳이 배열로 만듦경로 압축을 했어도 중간 부모가 있음을 알지 못했음 (항상 최상위 부모를 찾을려면 find 할 것)1차원 냅샥을 생각했지만 정방향으로만 생각해서 중복 연산될거라고 한 점 - 이는 역방향으로 하면 중복연산하지 않는다. 🔅 문제 풀이import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;impor..

🧫 문제 분석 ✔️ 출처호텔 골드 4 📖 문제배낭문제처음에는 우선 가격대비 효율이 가장 좋은 도시를 찾아서 C / 도시의 고객수 * 가격 + C % 도시의 고객수 를 만족하는 모든 도시의 최소값을 구할라했으나이는 불가능했다. 가격 대비 효율을 단순히 (고객수 - 가격) 순으로 내림차순 정렬하려했으나4 91 5 위의 경우 4 9 가 더 효율이 좋다고 판단해버린다. 즉, 완전 잘못 설계했다. DP로 풀어야하는 문제이다. 각 도시에 대하여 1~C 까지의 가격 최솟값을 구하면된다. 1. 현 도시의 홍보만으로 c를 채우는 경우2. 현 도시의 홍보 1개만 사용하고 나머지 c를 다른 최솟값으로 채우는 경우3. 이전 도시까지와 현재 도시를 비교하여 최솟값을 갱신 그런데 이 문제는 1차원 DP로도 충분히 풀 수 ..