[백준 알고리즘]
-
백준 1766 문제집 | C++[백준 알고리즘]/[C++] 2021. 3. 29. 13:50
이번 포스팅은 백준 1766번 문제집입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 기본 알고리즘 위상정렬 Topological Sort 우선순위 큐 Priority Queue 풀이 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. line 14 priority_queue pq; 오름차순 정렬..
-
백준 1005 ACM Craft | C++[백준 알고리즘]/[C++] 2021. 3. 29. 13:44
이번 포스팅은 백준 1005번 ACM Craft입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 기본 알고리즘 위상 정렬 Topological Sort 풀이 최소 시간을 갱신하는 조건 line49 result[next] = max(result[next], result[cur] + time[next]); 정점 next의 최소 건설 시간은 선행 정점이 모두 지어진 시간에 자신의 건물을..
-
백준 2056 작업 | C++[백준 알고리즘]/[C++] 2021. 3. 29. 13:39
이번 포스팅은 백준 2056번 작업입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 기본 알고리즘 위상 정렬 Topological Sort 풀이 최소 시간을 갱신하는 조건 line42 result[next] = max(result[next], result[cur] + time[next]); 정점 next의 최소 건설 시간은 선행 정점이 모두 지어진 시간에 자신의 건물을 짓는 시..
-
백준 1516 게임 개발 | C++[백준 알고리즘]/[C++] 2021. 3. 26. 12:51
이번 포스팅은 백준 1516번 게임 개발입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 기본 알고리즘 위상 정렬 Topological Sort 풀이 최소 시간을 갱신하는 조건 line56 result[next] = max(result[next], result[cur] + time[next]); 정점 next의 최소 건설 시간은 선행 정점이 모두 지어진 시간에 자신의 건물을 ..
-
백준 2437 저울 | C++[백준 알고리즘]/[C++] 2021. 3. 25. 10:50
이번 포스팅은 백준 2437번 저울입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 기본 알고리즘 그리디 알고리즘 셸 정렬 사용함 벡터와 sort 함수를 사용하면 코드의 길이와 실행 시간을 단축할 수 있다. 풀이 자연수 배열에서 배열 원소에 1이 존재하고, 배열의 (i-1)번째 원소까지의 누적합 sum에 대해 arr[i] > N; for (int i = 0; i > list[i]; } /*셸 정렬..
-
백준 2230 수 고르기 | C++[백준 알고리즘]/[C++] 2021. 3. 24. 10:41
이번 포스팅은 백준 2230번 수 고르기입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/2230 2230번: 수 고르기 첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다. www.acmicpc.net 기본 알고리즘 투 포인터 셸 정렬 사용함 벡터와 sort 함수를 사용하면 코드의 길이와 실행 시간을 단축할 수 있다. 전체 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 2..
-
백준 14567 선수과목 (Prerequisite) | C++[백준 알고리즘]/[C++] 2021. 3. 23. 10:20
이번 포스팅은 백준 14567번 선수과목 (Prerequisite)입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 기본 알고리즘 위상 정렬 (Topological Sort) 풀이 위상 정렬하면서 출력 배열(과목 번호가 인덱스)에 수강 학기 수를 저장한다. 1학기 부터 시작하므로 result 배열을 1로 초기화 한다. q 1 4 6 result[i] 1 1 1 cur = 1 q 1 4 6 2 3 result[i]..
-
백준 2109 순회강연 | C++[백준 알고리즘]/[C++] 2021. 3. 18. 13:17
이번 포스팅은 백준 2109번 순회강연입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 기본 알고리즘 우선순위 큐 priority queue 풀이 한 대학의 강연은 한 번만 간다. 입력 p | 20 2 10 100 8 5 50 d | 1 1 3 2 2 20 10 입력 값을 pair로 묶어 벡터에 저장 후 d를 기준으로 오름차순 정렬 {1, 10} {1..