Chadoll

최장 증가 부분 수열(Longest Increasing Subsequence)이란? 원소개 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. 간단히 말해, 가장 긴 증가하는 부분 수열이다. 예시 [6, 2, 5, 1, 7, 4, 8, 3] 이라는 배열에서 최장 증가 부분 수열(LIS)은 [2, 5, 7, 8]이 된다. [2, 5, 7], [2, 4, 8] 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것은 [2, 5, 7, 8]이다. 최장 증가 부분 수열 알고리즘 풀이 방법 최장 증가 부분 수열의 길이를 구할 수 있는 풀이 방법은 크게 2가지가 있다. 동적계획법 (DP, Dyna..

골드 Ⅳ https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 📄 문제 영선회사에는 매우 좋은 문화가 있는데, 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다. 모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬받는다. 직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 ..