지속 가능한 꾸준함

www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. 이제껏 푼 문제 중 가장 어려웠습니다... 다른 분들의 솔루션을 참고해도 이해가 잘 안될정도 였습니다... 먼저, n 자리 계단수의 수(큰 문제)는 n-1 자리 계단수의 수(작은 문제)로 계산될 수 있습니다(다이나믹 프로그래밍 기법을 이용하기에 적합함). 그런데, 문제에서는 단순히 n 자리 계단수의 수를 묻지 않고 n 자리 계단수 중에서 0, 1, 2, ..., 9 를 모두 포함하는 계단수의 수를 묻고있습니다. 이는 문제를 복잡하게 만드는 요소로 이를 계산하기..

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) 알고리즘을 사용할 수 있습니다. 문제를 풂에 앞서 저는 나동빈님의 위상 정렬 강의를 수강하였습니다. 먼저, 문제에 맞게 그래프를 구성해야합니다. 예제를 기준으로 ..