https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 1씩 증가하는 가장 긴 증가하는 부분 수열의 길이를 구해, 해당 부분 수열이 아닌 다른 숫자들을 앞이나 뒤로 보내는 접근으로 문제를 해결했다. 이때, cache[number] = number 숫자 위치에서 끝나는 1씩 증가하는 부분수열의 길이를 저장하는 다이나믹 프로그래밍을 이용했다. 코드 #include #include #include using namespace std; //가장 긴 증가하는 부분 수..

https://www.acmicpc.net/problem/2465 2465번: 줄 세우기 첫째 줄에는 전체 사람의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에 사람들의 키를 나타내는 양의 정수가 하나씩 주어진다. 여기서 모든 키들은 2×109이하이다. 그리고 마지막 줄에 수열 www.acmicpc.net 키 순위에 대해 해당 키 순위의 키가 몇 개 있는지 rank_cnt에 rank_cnt[키 순위] = 해당 키의 개수 형식으로 저장해 놓고 이를 이용한 합 세그먼트 트리 sum_sgmtt를 만든다. 그리고, 수열 s의 마지막번째부터 어떤 순위에 속하는지 이분 탐색을 통한 세그먼트 트리 쿼리를 통해 찾아내는 과정을 통해 문제를 해결했다. 코드 #include #include #inc..

www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 위상정렬을 이용하여 문제를 해결했다. 코드 #include #include #include #include #include #include #include #include #include using namespace std; int n, m; vector indegree(32001, 0); vector adj[32001]; //위상정렬을 이용 int main() { cin.tie..