반응형 알고리즘/동적계획법(DP)4 [LeetCode] 118. Pascal's Triangle | LIM 문제 https://leetcode.com/problems/pascals-triangle/description/ Pascal's Triangle - LeetCode Can you solve this real interview question? Pascal's Triangle - Given an integer numRows, return the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it as shown: [https://upload.wikimedia.o leetcode.com Given an integer numRows, return the.. 2023. 5. 28. [LeetCode] 1143. Longest Common Subsequence | LIM 문제 https://leetcode.com/problems/longest-common-subsequence/ Longest Common Subsequence - LeetCode Can you solve this real interview question? Longest Common Subsequence - Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string genera leetcode.com Given two strings text1 and t.. 2023. 5. 26. [백준] 18353번: 병사 배치하기 | LIM 📚문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자. 이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다. 병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가.. 2023. 2. 5. 동적계획법(DP) 동적계획법은 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫습니다. 동적계획법이 어떤 부분에서 동적으로 프로그래밍이 이루어진다는 말은 아닙니다. 동적계획법은 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 것입니다. 동적계획법의 조건은 이러합니다. 1. 작은 문제가 반복하여 일어나는 경우(중복이 있는 경우) 2. 같은 문제는 구할 때마다 정답이 같은 경우 이러한 위와 같은 조건을 만족하는 경우에만 동적 프로그래밍을 사용할 수 있습니다. 작은 문제의 결과 값이 항상 같다는 점을 이용해서 큰 문제를 해결하는 방법입니다. 이와 같은 특성을 이용하여 한 번 계산한 작은 문제를 저장해놓고 다시 사용을 할 .. 2021. 2. 9. 이전 1 다음 반응형
