지속 가능한 꾸준함

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 본 문제는 주어진 수열로부터 가장 긴 증가하는 부분 수열의 크기를 계산하는 문제입니다. 해당 문제는 Longest Increasing Subsequence Problem 이라는 영명으로 존재하는 굉장히 유명한 알고리즘 문제였습니다. 저는 다이나믹 프로그래밍 기법을 사용하여 해당 문제를 풀었습니다. 예시를 들어 설명드리도..

https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. LCA 는 Lowest Common Ancestor 의 축약어로써 트리에서 특정 두 노드의 공통 조상(Ancestor) 노드 중에서 Depth 가 가장 큰 노드를 찾는 문제입니다. 이와 관련하여 정리가 잘된 글이 있어 링크를 첨부합니다. https://jason9319.tistory.com/90 저는 아래와 같이 알..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. 본 문제는 조건에 따라 작업의 순서를 구하는 문제입니다. 순서가 정해져있는 작업을 풀때 우리는 위상 정렬(Topology Sort) 알고리즘을 사용할 수 있습니다. 문제를 풂에 앞서 저는 나동빈님의 위상 정렬 강의를 수강하였습니다. 먼저, 문제에 맞게 그래프를 구성해야합니다. 예제를 기준으로 ..