알고리즘39 줄-세우기 줄-세우기 백준 2252번 문제 https://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 1. 문제 2. 풀이 2.1 풀이 방법 이 문제에서 학생들의 키를 비교한 관계를 그래프로 나타내면 DAG(Directed Acyclic Graph)가 된다. 따라서 학생들의 키를 위상 정렬을 사용해서 정렬할 수 있다. 2.1.2 Directed Acyclic Graph DAG는 말 그대로 사이클이 없는 방향 있는 그래프를 .. 2022. 8. 23. 부분수-열의 합 그 2 부분수-열의 합 그 2 백준 1208번 문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 주어진 수열의 부분 수열의 합을 조합을 이용해서 구하고 그 값이 S일 때 count를 하는 방식으로 해당 문제의 답을 구할 수 있다. 그러나 이 문제에서 수열의 길이 N의 최댓값은 40이다. 즉, 부분 수열을 구하는 경우가 최대 2^40 이 될 수 있다. 따라서 단순히 주어진.. 2022. 8. 17. 골-드바흐의 추측 골드바흐의 추측 백준 6588번 문제 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 에라토스테네스의 체를 사용해서 테스트 케이스의 최대 값(= 100,000)까지 각 숫자가 소수인지 아닌지를 판별한다. 소수로 나누려는 숫자의 절반까지 탐색하면서 해당 숫자를 소수로 뺀 나머지가 소수인지 판별한다. 2.2 코드 2.2.1 makePrimeSet 주어진 size까지의 숫자들이 소수인지 .. 2022. 8. 11. 정육면체 전개-도 정육면체 전개-도 백준 1917번 문제 https://www.acmicpc.net/problem/1917 1917번: 정육면체 전개도 세 개의 입력 데이터가 주어지며, 각각의 입력 데이터는 여섯 개의 줄로 이루어져 있다. 각 데이터는 여섯 개의 줄에 걸쳐 여섯 개의 숫자가 빈 칸을 사이에 두고 주어진다. 숫자는 0 또는 1로 이 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 정육면체는 6개의 면으로 이루어져 있기 때문에 각 면에 번호를 붙일 수 있다. 예를 들어 정육면체가 주어졌을 때 특정 면을 0이라고 한다면 다음과 같이 번호를 붙여 볼 수 있다. [정육면체_면 번호] 위 그림은 정육면체의 아랫면을 0이라고 했을 때, 0면을 기준으로 위 -> 1, 오른쪽 -> 2, 아래 -> 3,.. 2022. 8. 9. 이전 1 2 3 4 5 6 7 8 ··· 10 다음
