Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처음악프로그램 골드 3 📖 문제 위상정렬 문제로 간단하게 위상정렬 풀이를 하면된다.진입차수가 0인 것만 BFS 탐색을 해주고 중복 탐색을 하지 않게 처리만 잘 해주면 간단한 문제다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static StringBuilder sb = new StringBuilder(); static int[] indegree; static List[] graph; static boolean[] visited; static int orderCount = 0; public static void main(String[] args) throws IOExcepti..

🧫 문제 분석 ✔️ 출처세 용액 골드 3 📖 문제 기존 두 용액 문제에서전체를 투포인터로 두고 투 포인터를 제외한 곳을 이분탐색으로 해서 풀려했으나당연히 모든 용액이 3가지씩 조합되지 않기에 계속해서 틀렸다. 나의 약한 부분중 하나가 이런 부분인 것 같다. 꼭 3개이상 , 여러개 등 조합해야하는 문제나 비슷한 문제들을 만나면하나를 고정하고 푼다는 이런 생각을 떠올리지 못한다. 까먹지 않기위해 블로그에 박제한다. 그리고 기껏 long type으로 계산해야한다고 메모해놓고 또 (long)으로 캐스팅안해서 틀렸다... 🔅 풀이 시도 import java.io.*;import java.util.*;public class Main { static int[] solutions; static in..

🧫 문제 분석 ✔️ 출처두 배열의 합 골드 3 📖 문제 누적합 + HashMap 문제 부 배열은 연속된 i~j까지의 합을 의미한다. A와 B의 부배열의 합이 T가 되는 쌍의 개수를 구한다. A배열에서 나올 수 있는 모든 누적합을 구하고, (key : 누적합, value : 개수)로 해시 맵에 저장한다.B배열도 마찬가지로 진행한다. 예시A배열의 누적합1 4 5 7 3 4 6 1 3 2이것들을 다 Map 에 저장 B배열을 키값(b배열 누적합)으로 순회하면서 T-(b배열의 누적합)이 A누적합이 저장된 해시 맵에 있는지 확인후개수를 곱해서 구한다. 47퍼에서 틀렸었는데 개수는 Integer 범위를 넘어설 수 있기때문이다. 따라서 Long 타입으로 변경해주었다.🔅 문제 풀이import ja..

🧫 문제 분석✔️ 출처케익 배달 골드 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..

🧫 문제 분석✔️ 출처극장 좌석 실버 1📖 문제 피보나치 수열 문제vip 영역일때는 이전 값을 이어받는다 현재 좌석을 기준으로 현재 좌석을 고정한 경우의 수 + 현재 좌석이 왼쪽 좌석과 교환했을 때 경우의 수를 구하면 된다.1 2 3 4 이고 현재 4라면1 2 3 | 4 로 4를 고정하고 1 2 3까지 의 경우의 수 dp[3]+1 2 | 4 3 으로 3과 교환하고 1 2 까지의 경우의 수 dp[2] 를 더한다 즉 점화식은if (isVip[i] || isVip[i-1]) : dp[i] = dp[i-1]else : dp[i] = dp[i-1] + dp[i-2] vip 좌석은 따로 기록해놓고피보나치 수열을 연산할때현재 좌석 혹은 이전 좌석이 vip 좌석이면 dp[..

🧫 문제 분석 ✔️ 출처암호코드 골드 5 📖 문제 DP 문제 연습셋DFS + DP (메모이제이션)으로 풀었는데 좀 더럽게 풀었다.DP[암호의 각 인덱스][알파벳 인덱스] 이렇게 2중 배열로 생각해서 풀었다. 그런데 알파벳은 고려대상이 아니다. 다른 사람 풀이를 보고 이해한 것도 정리한다. 0에 대한 모든 경우의 수를 처리했는데 그럴필요가 없었다... 그리고 DFS로 풀때 idx 즉, 인덱스만 신경쓰면 충분히 풀이가 가능했다. 나는 굳이 알파벳 수치 값을 파라미터로 넘겼는데 그럴 필요없이 현재 선택한 수가 알파벳 변환이 가능한지 여부로 따지고 가능하다면 다음 인덱스로 넘어가는 식으로 하면된다. 비슷한 문제 포스팅https://progis.tistory.com/85🔅 문제 풀이 [내 풀이 To..

🧫 문제 분석 ✔️ 출처상자넣기 실버 2 📖 문제 LIS 문제DP, 이분탐색 둘다 풀 수 있다. 최장 증가 부분수열 풀이로 풀면된다. 하다가 찾은 반례 42 4 2 2정답 : 2오답 : 1 🔅 문제 풀이 [DP]import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(S..