Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처1의 개수 세기 골드 2 📖 문제 BigInteger 로 풀었는데 굳이 안써도 long타입으로 커버쳐지나보다.2^i 인 수의 1의 개수를 누적합으로 구하는데 너무 큰 범위까지 구해서 그렇다.10^16이하까지만 구하면됐는데 ... 포스팅한 이유는 사실 다른사람의 코드를 이해하기 위함이다. https://tussle.tistory.com/1022 이 분의 풀이를 이해하고 정리해보겠다.i = i번째 자리일때 최댓값까지의 1의 개수 i = 2 이면 000~ 111 까지의 1의 개수를 구하는 것이다. i = 3 : 0000 ~ 1111까지의 1의 개수 2^n일때 1의 개수 dp[n] = dp[n-1] * 2 + 2^n if (n == 0) dp[0] = 1;이런 점화식이 나오는데..

🧫 문제 분석 ✔️ 출처텀 프로젝트 골드 3 📖 문제 그래프 탐색을 하되 Stack + Set 조합으로 풀었다. 근데 DFS로 푸는게 정석인가보다. test case142 1 2 3answer : 2wrong : 무한루프 DFS로 다시 풀었을때 시간 초과가 났던 문제의 코드 private static void dfs(int current) { visited[current] = true; int next = students[current]; if (!visited[next]) { dfs(next); } else { if (finished[next]) return; // 이미 팀 구성을 한 학생이면 더이상 탐..

🧫 문제 분석 ✔️ 출처음악프로그램 골드 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[..