[백준] 9252번 - LCS 2 (한줄평) 이전에 풀었던 LCS를 잘 이해하고 있다면 쉽게 풀 수 있었던 문제! 메모리, 시간 복잡도를 개선할 수 있는 방향으로 코드를 짜기 위해 고민해야하므로 나중에 한 번 쯤 다시 풀어보는 것이 좋을 것 같다 유사 문제: 9251 https://hseungyeon.tistory.com/311 [다이나믹 프로그래밍] ★★ 9251번 - LCS [백준] 9251번 - LCS (한줄평) 접근 방식은 맞았지만 점화식을 세우지 못해 어려웠던 문제.. 1차원 리스트로 접근하는 방식은 아예 생각하지도 못했고 이해하기도 어렵다.. 무조건 복습해야할듯하 hseungyeon.tistory.com 이 문제는 LCS 길이와 LCS를 구하는 문제로 DP테이블에 LCS를 바로 기록하는 방식과..
[백준] 9251번 - LCS (한줄평) 접근 방식은 맞았지만 점화식을 세우지 못해 어려웠던 문제.. 1차원 리스트로 접근하는 방식은 아예 생각하지도 못했고 이해하기도 어렵다.. 무조건 복습해야할듯하다 두 문자열의 LCS 길이를 구하는 문제다. 이 문제는 각 문자열의 길이를 하나씩 늘려가며 두 문자열의 LCS를 반복적으로 구하는 것이 핵심이다!! dp 테이블을 2차원 혹은 1차원 리스트로 풀이하는 방식 2가지가 있는데 1차원 리스트를 이용하여 구현항 방식이 조금 더 효율적인 방식이다. 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴것을 찾는 문제 (풀이1) 2차원 리스트 이용 풀이 시간: 50분 이내 1) 문제 해결 아이디어 dp 테이블을 2차원 리스트로 생성하여 푼 방식이다. 1. ..
[백준] 12865번 - 평범한 배낭 (한줄평) 냅색 문제인지 모르고 풀었던... 생각보다 더 어려웠던 문제로 복습이 꼭 필요하다!!! 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. N개의 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구하는 문제다. 이 문제는 전형적인 냅색 문제다. 1. 분할가능 배낭 문제(Fractional Knapsack Problem) 담을 수 있는 물건이 나누어질 때(설탕 몇 g) - 물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 쉽게 해결이 가능! - 배낭이 감당할 ..
[백준] 1912번 - 연속합 (한줄평) 점화식을 세우는데 헷갈리긴 했지면 결국 혼자서 풀어낸 문제! 나중에 한번쯤 복습해보면 좋을 것 같다~ 풀이 시간: 20분 이내 1) 문제 해결 아이디어 크기가 n인 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합의 최댓값을 구하는 문제다. 처음에 이 문제가 헷갈렸던 이유는 i번째 원소(graph[i])를 포함 시키는 경우, 포함 시키지 않는 경우 2가지로 나눠야한다고 생각했기 때문이다. 그래서 자꾸 이상한 답이 나왔다... 이 문제에서 중요한 점은 연속된 숫자를 선택한다는 것이고 최소 1개이상의 수를 선택해야 한다는 점이다. 1. i번째 원소 선택, (i -1)번째 원소 선택한 경우, (i - 2)번째는 선택할 수도 있고 안할 수도 있다. 그러므로 i번째..
[백준] 2565번 - 전깃줄 (한줄평) 최장 증가 부분 수열과 유사한 문제라고 생각했지만 막상 잘 해결이 안됐던 문제.. 복습이 필요하다!! 유사 문제: 11053 https://hseungyeon.tistory.com/304 [다이나믹 프로그래밍] ▲ 11053번 - 가장 긴 증가하는 부분 수열 [백준] 11053번 - 가장 긴 증가하는 부분 수열 (한줄평) 풀었던 문제지만 다시 풀려니 기억이 잘 안나서 어려웠던 문제.. 꼭 복습이 필요하다!!! 풀이 시간: 30분 이내 유사 문제: https://hseungyeon.ti hseungyeon.tistory.com 풀이 시간: 30분 이내 1) 문제 해결 아이디어 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 ..
[백준] 11726번 - 2xn 타일링 (한줄평) 쉽게 해결할 수 있었던 문제! 유사 문제: https://hseungyeon.tistory.com/287 [다이나믹 프로그래밍] ▲ 문제3 - 바닥 공사(223p) [이코테] 문제3 - 바닥 공사(223p) (한줄평) 코드는 짧으나 점화식을 떠올리기가 쉽지 않았던 문제로 복습이 꼭 필요!! 풀이 시간: 30분 이내 1) 문제 해결 아이디어 가로 길이: n, 세로 길이: 2 인 직 hseungyeon.tistory.com 풀이 시간: 10분 이내 1) 문제 해결 아이디어 가로 길이: n, 세로 길이: 2 인 직사각형 바닥을 1*2, 2*1 2가지 타일로 채울 수 있는 경우의 수를 10007로 나눈 나머지를 구하는 문제다. 이 문제는 다이나믹 프로그래밍의 기..
[백준] 11722번 - 가장 긴 감소하는 부분 수열 (한줄평) LIS 알고리즘을 알면 쉽게 풀 수 있었던 문제! 유사 문제: 11053, 11054 https://hseungyeon.tistory.com/304 [다이나믹 프로그래밍] ▲ 11053번 - 가장 긴 증가하는 부분 수열 [백준] 11053번 - 가장 긴 증가하는 부분 수열 (한줄평) 풀었던 문제지만 다시 풀려니 기억이 잘 안나서 어려웠던 문제.. 꼭 복습이 필요하다!!! 풀이 시간: 30분 이내 유사 문제: https://hseungyeon.ti hseungyeon.tistory.com https://hseungyeon.tistory.com/305 [다이나믹 프로그래밍] 11054번 - 가장 긴 바이토닉 부분 수열 [백준] 11054번 - ..
[백준] 11054번 - 가장 긴 바이토닉 부분 수열 (한줄평) LIS 응용 문제로 LIS(최장증가부분수열)알고리즘을 안다면 쉽게 풀 수 있었던 문제! 풀이 시간: 15분 이내 1) 문제 해결 아이디어 n이 1이상 1000이하인 길이가 n인 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 구하는 문제다. 수열 S가 어떤 수 Sk를 기준으로 (S1 Sk+1 > ... SN-1 > SN)을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. Sk를 기준으로 왼쪽은 가장 긴 부분 증가 수열, 오른쪽은 가장 긴 부분 감소 수열을 구하면 풀 수 있는 문제다. 가장 긴 부분 감소 수열을 구하기 위해서 입력받은 수열을 reverse해야한다는 것을 잊지말자! 2) 소스코드 n = int(input()) # ..
