profile
내가 다시 보기 위해 기록합니다.
post-thumbnail

<종만북> 08. 동적계획법_합친 LIS (JLIS, Joined Longest Increasing Subsequence

앞에서 LIS 문제는 많이 다뤘다. 하지만 이번에 다룰 내용은 더 심화된 JLIS 문제이다. 근데 책에서는 난이도가 하 라고 되어있다..하하..예를 들어 '1 3 4 7 9'은 '1 9 4'와 '3 4 7'의 JLIS이다. 문제는 정수 수열 A, B가 주어질 때 JLI

2021년 10월 24일
·
0개의 댓글
·
post-thumbnail

<Baekjoon>#11055가장 큰 증가하는 부분 수열 (Bigget increasing subsequence) c++

먼저 Ai에 값을 입력 받으면서 Bi에도 값을 똑같이 넣어준다.A의 부분수열이 증가수열이면서 현재 비교대상값(Bi) 보다 이전까지의 합+ 현재값 (Bj+Aj)이 더 큰 경우 이 값을 현재 비교대상값(Bi)에 넣어준다.코드 짜면서도 자꾸 헷갈려서 표에 값을 채워가며 생각

2021년 10월 10일
·
0개의 댓글
·
post-thumbnail

<Baekjoon>#14002가장 긴 증가하는 부분 수열4 (Longest increasing subsequence 4) c++

바로 앞에서 풀었던 문제가 부분 수열의 길이만 출력하는 거라면, 이번에는 가장 긴 증가하는 부분수열도 출력해야 한다. dp의 값이 가장 큰 A의 값부터 시작해서 하나씩 작아지게 역순으로 B에 push_back 한다. (처음에 dp의 값이 가장 작은 A값부터 B에 pus

2021년 10월 10일
·
0개의 댓글
·
post-thumbnail

<Baekjoon>#11053 가장 긴 증가하는 부분 수열 (Longest increasing subsequence) c++

종만북 P.232 최대 증가 부분 수열 문제를 해결하는 완전 탐색 알고리즘을 공부하다가 도저히 이해가 안 돼서 일단 다른 사람들이 풀어 놓은 코드를 참고해서 코드를 작성했다.중첩 for문을 사용하여 Ai의 값과 Ai 이전의 값 Aj, 예를 들면 A5일 경우 A0부터 A

2021년 10월 10일
·
0개의 댓글
·