분류 전체보기

조건1. 연속된 몇 개의 수일지는 모른다. (한 개 이상 선택)2. 연속된.3. 최대 합을 구해야 한다. 부분합을 구해서 dp 배열에 부분합의 max 값을 갱신해주고 그 dp 배열의 max 값을 구하면 최대 합이 구해진다. d[i-1] + list[i] 는 현재 원소 i 를 포함하는 최댓값의 후보이다. d[i-1] 에 list[i] 를 더한 게 현재 원소 보다 크다면 계속 더해나가는 것이 최댓값이 유지가 되는 것이고 d[i-1] 에 list[i] 더한 게 list[i] 보다 작다면 d[i-1] 는 음수라는 것이고 그러면 list[i] 부터 새롭게 연속합을 시작해야 한다. n = int(input())list = list(map(int,input().split()))dp = [0] * nfor i in r..

11053 가장 긴 증가하는 부분 수열을 제법 내 힘으로 풀고 자신감이 생겨서 연계된 문제인 가장 긴 증가하는 부분 수열 4 문제를 풀었다. 겁도 없이 골드 문제를 손댄 죄...Solutionn = int(input())list = list(map(int,input().split()))dp = [1] * nresult = []for i in range(n) : for j in range(i) : if list[i] > list[j] : dp[i] = max(dp[i] ,dp[j]+1) # i 에서의 최적의 해를 갱신해준다. max_length = max(dp) # 가장 긴 증가하는 부분의 길이- 먼저 가장 긴 증가하는 부분 수열의 길이를 구한다.m..

프론트엔드만 하던 나는... 주는 API 를 받아서 활용만 해봤지 준 적은 당연히 없다. 이번에 백엔드를 처음 하면서 열심히 코드를 따라 치며 기능 구현을 하고 이걸 어떻게 프론트에게 내가 받던 body (API) 방시긍로 주지...? 하고 솜씻너가 되었다. 프론트 오빠 미안... 이런 나라서... MVC 어쩌고가 중요한 것 같긴 한데 thymeleaf 를 써서 view resolver 에러를 봤던 것 같긴 한데... 아니 API 는 언제 만드는 거지?Spring 에서 컨텐츠 전달 방식Spring 전달 방식은 정적 content, MVC & 템플릿 엔진, API 방식 등 크게 세 가지로 나누어진다. 템플릿 엔진템플릿 엔진이란 템플릿 양식과 특정 데이터 모델에 따른 입력 자료를 합성하여 결과 문서를 출력하..

알고리즘 기초를 풀면서 수학 문제만 풀다가 나도 남들이 말하는 dp 문제라는 걸 풀게 됐다! 뿌듯해요 Dynamic Programming 은 동적 프로그래밍이다. 복잡한 문제를 작은 문제로 분해하여 해결하는 알고리즘 기법 중 하나이다. 분할 정복과 유사하며 중복되는 부분 문제가 발생할 때 한 번만 계산하고 그 결과를 메모이제이션하여 다른 비슷한 부분 문제들이 다시 발생할 때 메모이제이션한 결과를 가져와 재활용한다.  동적 프로그래밍을 적용하기 위해서는 두 가지 조건을 만족해야한다. 전체 문제의 최적해가 부분 문제의 최적해로부터 구해질 수 있어야 하는 최적 부분 구조 (Optimal Substructure) 와 부분 문제가 중복되어 여러 번 반복 계산되어야 하는 중복되는 부분 문제 (Overlapping ..