본문 바로가기
반응형

다이나믹3

[알고리즘] Maximum Length of Repeated Subarray 포인트 LCS 를 물어보는 문제입니다. LCS 도 2가지 종류가 있습니다. 1. Longest Common Substring 과 2. Longest Common Subsequence 입니다. 1. Longest Common Substring 는 최장 공통 문자열로 '연속된' 공통 문자에 관한 것입니다. 2. Longest Common Subsequence 는 부분 수열중 최장의 길이를 나타내는 것입니다. 2개다 연관이 되어 있으나 점화식은 다를 수 있으니 주의하시기 바랍니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 예시) [0,0,0,0,0], [0,0,0,0,0] [0, 0, 0, 0, 0, 0] [0, 1, 1, 1, 1, 1] [0, 1, 2, 2, 2, 2] [0, 1, 2, 3,.. 2021. 7. 8.
[알고리즘] 코딩 테스트를 위해 알아야 하는 문제들 먼저 이 글은 복수 전공자 및 비전공자 분들을 위한 글입니다. (물론 전공자 분들이 보셔도 됩니다) 저는 복수 전공자로서 코딩 테스트가 막막함이 있어 이것을 해결하고자 적어보는 글입니다. 알고리즘 목록 완전검색 - 브루트포스 순열 (next_permutation) > stl 조합 (재귀) 비트 마스크 비트 마스크 #include #include using namespace std; vector a; int main(){ int n, m; cin>>n>>m; a.resize(n); for(int i=0; i>a[i]; int answer = 0; for(int i=1; i 2021. 5. 17.
[알고리즘] Maximum Subarray + 배열에서 부분 최대합을 구하는 방법 어느 순간 1100 명께서 저의 글을 읽어 주셨습니다. 정말 부족한 글이지만 잘 쓰도록 하겠습니다. 포인트 배열에서 부분합을 구하는 방법은 정말 다양하게 있을 수 있습니다. 먼저 LeetCode 문제를 풀어보고 이어서 다른 것들도 써보는 시간이면 좋겠습니다. 저는 다이나믹 프로그래밍으로 해결을 하였습니다. O(n) 즉, 배열을 전부 순회를 하는 경우 답을 구할 수 있다는 뜻입니다. 값을 계속 저장을 해나가면서 만약 더하려고 하는 값이 0 이하일 경우 0으로 초기화한 후 계속해서 더해나가는 것입니다. python class Solution: def maxSubArray(self, nums: List[int]) -> int: result = 0 presum = 0 # DP 를 이용한 방법 for index .. 2021. 5. 17.
반응형

티스토리툴바