알고리즘 문제풀이
-
[백준/BOJ] 11000번 강의실 배정 (C++)알고리즘 문제풀이/백준 2021. 9. 14. 18:56
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 강의실을 적게 사용하기 위해서 시작 시간과 끝 시간의 간격을 최대한 좁혀야 한다. 그러므로 시작 시간을 기준으로 오름차순 정렬하였다. 그리고 우선순위 큐를 이용하여 수업 끝 시간을 넣어준다. 현재 수업의 시작 시간이 우선순위 큐에 들어있는 top의 값보다 크거나 같으면 강의실을 같이 쓸 수 있으므로, pop한 후 우선순위 큐에 현재 수업의 끝 시간을 넣어준다. 반대의 경우에는 pop없이 push만 해준다. 그러면 우선순위 큐에 남은 원소의 수가..
-
[백준/BOJ] 1969번 DNA (C++)알고리즘 문제풀이/백준 2021. 9. 13. 18:52
https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 각 열마다 A, C, G, T가 몇번 나오는지 저장할 수 있는 2차원 배열을 선언한다. 합이 가장 작은 DNA은 결국 한 열을 기준으로 각 행마다 빈도수가 많이 나온 것들로 구성하면 된다. TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT -------------- TAAGATAC 해밍 디스턴스는 n에서 각 행마다의 빈도수..
-
[백준/BOJ] 1931번 회의실 배정 (C++)알고리즘 문제풀이/백준 2021. 9. 13. 18:07
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 해결의 아이디어는 가장 끝나는 시간이 작은 회의실을 시작으로, 가능한 한 끝나는 시간 작은 회의실을 계속 고르면 되는 문제이다. 따라서 입력을 끝나는 시간을 기준으로 오름차순 정렬한다. (끝나는 시간이 혹시 같다면 시작 시간을 기준으로 오름차순) 그리고 반목문을 통해 현재 선택한 회의실의 끝나는 시간과 다음 회의실의 시작시간을 비교해가며 회의실을 선택하면 된다. #include #include using namespace std; int cmp(pair a, pair b) { if(a.second == b...
-
[백준/BOJ] 12845번 모두의 마블 (C++)알고리즘 문제풀이/백준 2021. 9. 13. 17:00
https://www.acmicpc.net/problem/12845 12845번: 모두의 마블 영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다. 이번 이 www.acmicpc.net 문제를 잘보면 결국 획득할 수 있는 최대 골드는 레벨이 가장 큰 카드를 시작으로 인접한 카드와 합성을 하는 것이다. 결국은 레벨이 가장 큰 카드와 모든 카드가 합성을 하게된다. 따라서 카드를 내림차순으로 정렬하고 가장 큰 레벨의 카드인 0번 인덱스의 값과 1번부터 n-1번까지의 인덱스 값의 누적합을 구하면 된다. #include #include using namespace std; int cmp(i..
-
[백준/BOJ] 4796번 캠핑 (C++)알고리즘 문제풀이/백준 2021. 9. 13. 16:35
https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 문제는 매우 간단하다. 일단 L = 5, P = 8, V = 20을 예시로 들어보겠다. 1 2 3 4 5 6 7 8 | 9 10 11 12 13 14 15 16 | 17 18 19 20 일단은 P의 크기만큼 V의 구간을 나눠준다. 그럼 8의 크기 구간 2개와 나머지 남은 구간 1개가 나온다. 해당 구간에서 캠핑장을 사용할 수 있는 날짜는 연속된 5일, 진하게 표시된 부분이다. 즉, V를 P로..
-
[백준/BOJ] 13458번 시험 감독 (C++)알고리즘 문제풀이/백준 2021. 9. 12. 21:15
https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 삼성 역량 테스트 기출 문제 : 그리디 시험장의 수 : 3 // 각각의 학생 수 : 3, 4, 5 총감독관이 감독할 수 있는 학생 수 : 2 // 부감독관이 감독할 수 있는 학생 수 : 2 라고 가정해보자. 문제에서 총감독관은 1명밖에 존재하지 않는다고 언급했으므로, 전체 학생수에서 총 감독관이 감독할 수 있는 학생의 수를 빼준다. 그러면 ..
-
[백준/BOJ] 2217번 로프 (C++)알고리즘 문제풀이/백준 2021. 9. 12. 19:21
https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 이 문제의 포인트는 병렬로 로프를 연결했을 때 걸리는 무게의 최대 중량이 가장 낮은 무게를 따라간다는 점이다. 예를들어, 로프가 10, 20, 50 3개가 있다고 가정하자. 세 로프를 병렬로 연결할 경우 각각 최대 중량이 30, 60, 150이다. 이러면 세가지 조건을 모두 만족을 해야하므로, 가장 낮은 무게의 로프인 30까지가 최대 중량이된다. 따라서 로프를 오름차순으로 정렬하고, 작은..
-
[백준/BOJ] 11399번 ATM (C++)알고리즘 문제풀이/백준 2021. 9. 12. 17:13
https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net SJF 스케줄링 알고리즘처럼 구현하면 된다. 인출이 하는데 걸리는 시간을 오름차순으로 정렬한 후 누적합 배열에 넣어주고, 그 배열의 누적 합을 또 구해준다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n, sum = 0; cin >> n; vector v(n), res(n); for..