Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처LCS 2 골드 4 📖 문제 LCS 문제와 다른 점은 LCS를 출력해야한다는 것이다.단순히 순차적으로 탐색하면서LCS에서 길이가 1인 처음 만나는 문자LCS에서 길이가 2인 처음 만나는 문자이런식으로 풀면 안된다. 문자열이 같은 문자가 연속으로 주어지는 경우 잘못된 LCS를 구하게 되기 때문이다. AAACCCAACCA A A C C AA 1 1 1 1 1A 1 2 2 2 2 A 1 2 2 2 3C 1 2 3 3 3C 1 2 3 4 4C 1 2 3 4 4 이렇게 위에서부터 순차적으로 for문 탐색시 AAAC가 되버린다.답은 AACC 이다. 때문에 가장 마지막 위치에서 이전 대각위, 왼쪽, 위쪽을 탐색하여 같은 길이 값이면 그 곳으로 이동하고3곳이 다 다르다면 현재 자신이..

🧫 문제 분석 ✔️ 출처파이프 옮기기 1 골드 5 📖 문제 BFS로 89%에서 시간초과 떠서 별짓을 다 하다가 질문게시판에 map[n][n] == 1일때 예외처리를 하면 된다 해서 했는데 통과했다. DP로 풀 생각은 들었는데 방향을 DP로 어떻게 표현할지 모르겠어서 무작정 BFS로 일단 풀었다.  방향 정하는 방식을 좀 이상하게했다.  DP로 하는 법을 이해해 보고 그림으로 그려봤다 dp로 현재 들어오는 방향에 대해서 다 구하면 된다 . 🔅 문제 풀이import java.io.*;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main { static int[] dy =..

🧫 문제 분석 ✔️ 출처LCS 골드 5 📖 문제 최장 공통 부분 수열로 알고리즘 시간에 배웠었다. 근데 배운거랑 직접 구현해본거랑 차이가 심한 것을 느꼈다. 이 문제를 못푸니 배낭문제도 못푼다. LCS에 대한 이해가 있었다면 배낭 문제를 쉽게 풀 수 있을 것이다.  현재 비교하는 두 문자가 같다면 이전 최장 공통 부분 수열 길이에 + 1을 하여 LCS를 갱신한다. 두 문자열의 길이를 각각 n과 m이라 할 때,DP 테이블 dp는 인덱스 i∈[0,n]  j∈[0,m] 범위를 기반으로 구성된다. i-1, j-1까지 진행 했을때 LCS 길이 + 현재 공통 문자가 나왔으므로 길이가 1 증가때문에 dp[i-1][j-1] + 1이 된다.  같지 않다면 dp[i-1][j], dp[i][j-1] 중 큰 값을 유지한다..

🧫 문제 분석✔️ 출처가장 큰 정사각형 찾기 level 2📖 문제 2번 시도후 푼 문제다. 1차 시도 정 사각형을 찾는게 문제인데 처음에는 1차원 배열에 각 열에 대한 개수를 세서최솟값을 갱신하면서 카운트를 하고최솟값과 카운트 값이 같다면 가장 큰 정사각형 후보로 넣는 식이였다.당연히 틀렸고, 시간초과났다.  2차 시도문득 생각해보니 DP에 대해 배웠을 때 값을 누적하고 원하는 부분의 값을 얻는 방법이 떠올랐다.dp[i][j] - dp[i-1][j] - dp[i][j] + dp[i-1][j-1] 여기에 정사각형 한 변의 길이를 더해주고 영역 값을 구한 뒤  정사각형 넓이 == 영역 값  ? 한 변 길이 + 1 , 정사각형 넓이 최신화  이런식으로 하면 되지 않을까 라는 생각에 해봤는데 성공했다. 정사..

🧫 문제 분석 ✔️ 출처오르막 수 실버 1 📖 문제 깊이 별로 나누되 0~10까지 에 대해서 동적프로그래밍을 한다. 중요한 점수는 0으로 시작할 수 있다는 것이다.  현재 깊이의 각 수는 이전 깊이의 현재 수부터 9까지의 개수 합을 더하면 된다.   수 \ 깊이12301깊이 1의 0~9까지 : 10깊이 2의 0~9 까지 : 5511깊이 1의 1~9까지 : 9깊이 2의 1~9까지 : 4521깊이 1의 2~9까지 : 8깊이 2의 2~9까지 : 36 잘 모르겠다면 노드로 직접 그려보면 바로 알기 쉽다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws I..

🧫 문제 분석 ✔️ 출처RGB 거리 실버 1 📖 문제 DP 문제로현재 집 비용 + 이전 집에서 현재 집 열이 아닌 2 곳 중 가장 적은 비용을 가진다. 점화식을 세워보면 이렇다. dp[i][j] = Math.min(dp[i][j+1], dp[i][j+2]) + house[i][j];물론 한 행에 집은 3개이므로 현재 열을 제외한 다른 집 중에서 가장 적은 비용을 선택하므로% 연산이나 if문을 써서 현재 집 열을 피하면 된다.   🔅 문제 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ..

✔️ 출처쉬운 계단 수 실버 1 📖 문제중복 연산이 많이 일어나고 반복적이다.  이참에 다시 학교에서 배운 DP의 적용 요건을 복습하겠다.  최적 부분구조(Optimal substructure)큰 문제의 최적 해에 하위 문제의 최적 해가 포함하위 문제들의 중복 (overlapping recursive calls)재귀적 해법으로 풀면 같은 하위 문제에 대한 호출이 심하게 중복 재귀적으로 깊이만큼 0~9까지 +1 -1을 하면서 생성하다보면 엄청난 중복이 생김이전의 깊이에서 얻은 갯수를 재활용할 수 있을 것 같음. DP를 적용해보자 우선 0과 9는 1가지 밖에 없다.0 → 19 → 8따라서 0 과 9는 따로 처리하고 1~8까지는 -1 +1 숫자가 계단 수이니 이전 깊이의 -1 +1 숫자의 개수를 더한다.  ..

🧫 문제 분석 ✔️ 출처가장 긴 증가하는 부분 수열 실버 2 📖 문제 DP 문제로 현재 값이 이전 값보다 크다면 이전 값의 수열 개수와 현재 값의 수열 개수중 더 큰 값을 취하면 된다.  // j = i - 1 ~ 0까지if (arr[j]  문제의 예시로 현재 4번째 30이라고 하자 10 dp[4]는 처음 값은 0이므로 dp[3]의 값을 가진다. dp[3]은 1이다. (3번째 10은 이전에 증가하는 수열이 없고 10밖에 없음)그다음 2번째 20 dp[2] 는 2이므로 dp[4] = 2이고 이 연산이 끝나면 dp[4]에 30도 카운팅해주면 3이된다.   이 풀이에서 중요한 것은 수열의 크기가 1일 때는 수열의 길이도 1이라는 것이다.   🔅 문제 풀이import java.io.*;import java..

🧫 문제 분석 ✔️ 출처설탕 배달 실버 4 📖 문제 풀었던 문제를 보다가 꼭 다시 풀라고 메모를 적어놔서 다시 풀었다. DP로 풀 수 있는 문제이다. 3 과 5로 나눠 떨어지지 않는 1 , 2, 4, 7 은 -1로 3 5 은 1로 미리 초기화한다.6도 미리 2로 초기화한다. N - 3과 N - 5 중 더 작은 값을 취하고 +1해주면 dp[N] 이 된다.  N에서 3키로를 한 봉지를 담고 [N-3] 키로일때 얻은 봉지 최솟값과N에서 5키로를 한 봉지를 담고 [N-5] 키로일때 얻은 봉지 최솟값 중 더 작은 값을 취하는 것이다. dp[i] = Math.min(dp[i - 3], dp[i - 5]) + 1;       🔅 문제 풀이import java.io.*;public class Main { p..

🧫 문제 분석 ✔️ 출처파도반 수열 실버 3 📖 문제  DP문제다. 중복 연산이 포함되어있다.  12번째는 12 + 4 로 번호를 매겨보면 11번째 + 7번째 를 더한 것이다.  그런데 4또한 3 + 1이며 번호를 매겨보면6번째 + 2번째 를 더한 것이다.   이를 점화식으로 보면dp[n] = dp[n-1] + dp[n-5]  이렇게 볼 수 있다.  이전값 + dp[n-5] 가 아닌 이유는 이전 값 또한 어떠한 숫자들의 덧셈 결과일 수 있기 때문이다.   🔅 문제 풀이import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new ..