lgvv98

BOJ 11053 가장 긴 증가하는 부분 수열 ✅ dp라는데 진짜 어려웠다. 우선 알고리즘 풀이법이 이해가 가지 않았다. 주어진 값이 10 20 10 30 20 50 있다고 가정하자. list 10 20 10 30 20 50 dp 1 2 1 3 2 4 코드를 보면 이해할 수 있는데, 어떤 수를 기준으로 나보다 작은 수를 비교한다. 나를 기준으로 내 앞을 비교한다. 나보다 작은 수(j)라고 하면 dp[j]는 dp[j]보다 작은 값들이 몇개 있는지 저장한다. 그게 가장 긴 부분 수열의 합이기 때문이다. 제일 중요한 것은 실제 문제 풀이에서 이를 떠올려야 한다는 점이다. 그렇다면 점화식을 어떻게 생각할 수 있을까?dp문제의 경우에는 그냥 손으로 쓰다보면 특정한 패턴을 찾을 수 있다.list를 놓고, 나보다 작..

BOJ 2579 계단 오르기 ✅ 점화식을 이용한 DP문제였다. 나동빈 책을 공부하면서 비슷한 문제를 해결하려는 노력을 했었는데, 진짜 너무나도 어려웠다. 여기서는 점화식을 세우기 위해 문제의 마지막 조건의 초점을 맞추는데, 마지막 계단은 꼭 밟아야 한다. 이 문장을 기준으로 점화식을 설계해보자!!!! 마지막 계단을 꼭 밟아야 하므로, 마지막 계단을 밟는 케이스를 보자면1. O X O O (끝 계단과 바로 이전 계단을 밟음, 3연속은 안된다, 근데 최댓값을 찾아야 하므로 전전전칸도 포함한다.)2. ? O X O(끝 계단과 그 전전 계단을 밟음) 케이스 1에서는 끝 패턴이 저걸로 고정 케이스 2에서는 끝 패턴이 저렇게 고정 ? 자리는 어떤게 올지 모른다는 말 -> 따라서 수식에 반영하지 않는다. 이를 점화식..

BOJ 11726 2 x n 타일링 ✅ BOJ 11726 2 x n 타일링 이 문제는 생각보다 어려웠다. 사실 나동빈 알고리즘 dp편에서 본 기억이 있는데, 이를 직접 풀어보려니까 도저히 생각이 나지 않았다. 사실 책의 해설도 잘 이해가 가지 않았는데, dp를 보면 볼수록 수학적인 사고가 강력하게 필요한 것 같다. 풀이와 해설이 이해가 가지 않아서 다른 분의 블로그를 참고하였다. 1x2, 2x1 두개의 타일이 있다. n = 1 : | 1개 n = 2 : ||, = 2개 n = 3 : |||, =l, l= 3개 n = 4 : llll, ll=, l=l, =ll, == 5개 n = 5 : lllll, lll=, ll=l, l=ll, =lll, l==, =l=, ==l 8개 이런 패턴을 찾을 수 있다. 참고한..

BOJ 10610번 30 ✅ 후 오랜만에 생각보다 어려웠음 처음에 문제보고 잘 이해가 안가서 문제 설명 다른 사람이 해둔거 쓱 본다음에 풀려고 했는데, 어떻게 해야할 지 몰라서 재귀를 돌렸음 🟠 [처음 내 접근 방식] 1. 인풋을 String으로 받는다. 2. 받은 String을 [Int] 배열로 만든 후 내림차순으로 정렬한다. 3. 0이 포함되어 있지 않다면, 30의 배수가 될 수 없음으로 바로 "-1"을 리턴하고 종료한다. ex) "2931" -> [9, 3, 2, 1] 4. 재귀를 통해서 9xxx, 3xxx 등 조합 가능한 네자리 수를 전부 만들어 낸다. 4-1. 이때 재귀의 종료 조건에서 4자리 수가 완성되면, 30으로 나누어서 30의 배수인지 아닌지 판단하고, 이 값들 중에서 max값을 갖고 있..