Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처사수빈탕 골드 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..

🧫 문제 분석 ✔️ 출처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로도 충분히 풀 수 ..

🧫 문제 분석✔️ 출처케익 배달 골드 3📖 문제 현재 위치에서 다음 배달 위치까지 가는데문제에서 고객의 위치까지 가거나 고객의 상하좌우 인접 격자점까지 가야한다했다. 따라서 고객의 위치까지가는 방법을 5가지로 볼 수 있다.고객의 위치를 x,y 로 표현할때 1. (x, y)2. (x-1, y)3. (x,y-1)4, (x+1, y)5, (x, y+1) 이렇게 5가지의 경우로 나눠서 DP로 풀면된다. 필자는 DFS + DP로 풀었는데 생각보다 느렸고, 다른사람들 코드를 보고 이해해본 방법 2가지도 작성하겠다.🔅 문제 풀이 [본인 풀이]import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import..

🧫 문제 분석 ✔️ 출처정상회담 골드 3 📖 문제 조합을 이용한 DP 문제 이 문제의 경우 직접 손으로 그려봐야 명확히 이해가 가능하다. 그렇지 않아도 그려볼 수 있는 문제는 손으로 직접 그려보면 이해도 잘되고 쉽게 문제의 해결방법을 얻을 수 있다. (나는 그랬다..) 문제를 봤다면 알듯이 인원이 짝수여야지만 가능하다. 우선 임의의 한 점을 선택하고 양옆의 사람과 악수했을 때 경우의 수를 구한다.임의의 1명 + 왼쪽 = 2명 , 이 2명을 제외한 나머지가 악수하는 경우의 수 : dp[n-2] 임의의 1명 + 오른쪽 = 2명 , 이 2명을 제외한 나머지가 악수하는 경우의 수 : dp[n-2] 여기에 더해 왼쪽 1명을 지나 2칸 뒤에 있는 사람과 악수하는 경우의 수 : dp[2] * dp[n-4]..

🧫 문제 분석✔️ 출처여행 골드 4📖 문제 문제를 읽어보면 최단경로 다익스트라를 좀 변형해서 최장경로로 풀면 되지 않을가 싶은 생각이 들었는데문제에서 'M개 이하의 도시를 지나는' 조건이 있기에 좀 어려울 것 같다는 생각이 들었다. 따라서 DP로 풀었다.N번 도시까지 오는데 M개의 도시를 지나 먹은 기내식 최대 값을 구한다. 1 -> 3 10 3번 도시까지 오는데 2개의 도시를 지나 먹은 기내식 최댓값은 101 -> 2 5 2번 도시까지 오는데 2개의 도시를 지나 먹은 기내식 최댓값은 52 -> 3 3 이전에 2번 도시를 방문한 적이 있는지 확인, 1->2로 방문한 적이 있으므로 2번으로 오는데 먹은 기내식 최댓값..

🧫 문제 분석 ✔️ 출처공통 부분 문자열 골드 5 📖 문제 최장 공통 부분 수열 문제로 str1의 i번째 문자와 str2의 j번째 문자가 공통이라면 (같다면)이전 문자까지 연속된 공통 부분 수열 + 1 (현재 공통 부분) 점화식LCS[i][j] = LCS[i-1][j-1] + 1; (i >= 1, j >= 1) 🔅 문제 풀이import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR..