백준 줄 세우기2 BOJ 2252 - 줄 세우기 2252번: 줄 세우기 (acmicpc.net) 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 접근방법 이번 문제는 위상정렬 문제라는 것을 사전에 알고 풀었다. 왜 위상정렬로 풀어야할지 생각해봤다. 총 N명의 학생들 중 임의의 두 학생 A와 B의 키만 비교하였다. 그리고 이렇게 잰 키를 통해 줄을 세운다. 이는 A와 B를 정점으로 생각할 때, A와 B는 단방향 간선을 가진 그래프가 된다. 이를 통해, 위상정렬하여 각 정점들의 순서를 정할 수 있기 때문에 위상정렬을 .. 2024. 4. 6. [그리디 #21] BOJ 7570 - 줄 세우기 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 1차 시도 처음에 이걸 그리디로 해결하기 위해서 다음과 같이 생각했다. 1. 앞으로 옮겼을 때, 뒤쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야한다. 2. 뒤로 옮겼을 때, 앞쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야 한다. 그러나 이것은 금방 틀리다는 것을 알 수 있다. 가령 1,2번이 맞다고 하더라도 순서대로 이어져있지 않으면 문제가 된다. 따라서, 순서를 집중해서 공략하는게 좋겠다고 .. 2024. 2. 27. 이전 1 다음
