Algorithm/Baekjoon117 11000. 강의실 배정 (Python) 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 먼저 입력으로 받은 수업 시간들을 수업의 시작 시간을 기준으로 오름차순으로 정렬한다. 최소힙을 하나 만들어 첫 수업의 끝나는 시간을 넣어주고 강의실을 하나 사용한다. 이제 for문을 통해 두 번째 수업부터 돌면서 현재 수업이 최소힙의 루트에 있는 종료 시간보다 빨리 시작하거나 빨리 끝난다면 해당 시간의 강의실은 사용할 수 없으므로 새로운 강의실을 배정한다. 만약 시작시간이 최소힙의 루트보다 크거나 같을 경우에는 해당 강의실에서 현재 수업을 할 수 있다는 것을 의미하므로 강의실을 새로 배정할 필요가 없다. .. 2022. 3. 7. 2437. 저울 (Python) 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 풀이 입력받은 추의 무게들을 오름차순으로 정렬한 후 차례대로 더해가면서 현재까지 추의 무게들의 합과 다음 추의 무게를 비교하면 된다. 만약 다음 추의 무게가 현재까지 추의 무게들의 합보다 더 크다면 현재까지 추의 무게들의 합 + 1이 답이 된다. 문제를 풀 수 있는 방법을 찾지 못해 풀이를 보고 해결했는데 말로 하는 설명만 봤을 때는 이해가 안갔는데 수직선을 그려서 설명해 주신 분의 풀이를 보고 이해할 수 있었다. 아래 링크를 참고해보자~ https://aerocode.n.. 2022. 3. 6. 1339. 단어 수학 (Python) 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 각 알파벳의 자릿수를 더하여 높은 숫자를 가진 알파벳 순으로 큰 숫자로 바꾸면 된다. 위의 예제에서 첫 번째 단어인 GCF를 보면 G는 100의 자리, C는 10의 자리, F는 1의 자리에 있다. 두 번째 단어인 ACDEB를 보면 A는 10000의 자리, C는 1000의 자리, D는 100의 자리, E는 10의 자리, B는 1의 자리에 있다. 딕셔너리를 사용하여 이를 나타내면 {'A': 10000, 'C': 1010, 'D': 100, 'G': 100.. 2022. 3. 4. 1022. 소용돌이 예쁘게 출력하기 (Python) 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 풀이 문제에서 주어진대로 구현하면 되는 문제다. 하나 주의할 것은 전체 크기만큼 2차원 리스트를 만들고 출력 범위 부분만 출력하게 되면 메모리 초과가 발생하게 된다. 전체 크기만큼 2차원 리스트가 있다고 가정하고 소용돌이를 돌리되, 실제 리스트는 출력 범위 크기로 만들어야 한다. 문제에 나온 예제 1번을 보면 위와 같이 전체 크기만큼 소용돌이를 돌리지만 실제 리스트는 빨간색 네모에 해당하는 부분으로 만들고 해당 범위에 들어왔을 때 리스트의 값을 수정해 주면 된다. 소용돌이가 동작하는 과정은 (오른쪽, 위쪽, 왼쪽, 아래쪽)과 같은 순서로 진행된다. 처음 (0, 0)에 1을 채워놓고.. 2022. 3. 1. 1202. 보석 도둑 (Python) 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 보석과 가방을 담아두는 리스트를 만들고 두 리스트를 오름차순으로 정렬한다(보석의 경우 무게를 기준으로). 문제에서 주어지는 N과 K의 최댓값이 300,000이기 때문에 단순한 방법으로 2중 for문을 사용할경우 시간초과가 발생한다. 시간초과를 방지하기 위해 가방 리스트를 기준으로 for문을 시작한다. 다음으로 보석 리스트에 대하여 for문을 돌면서 현재 가방에 담을 수 있는 무게 이하인 보석들을 .. 2022. 2. 28. 1647. 도시 분할 계획 (Python) 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 최소 신장 트리(MST, Minimum Spanning Tree) 개념을 사용하여 해결할 수 있다. MST를 만들기 위한 알고리즘 중 크루스칼 알고리즘을 사용하였다. 유지비를 오름차순으로 정렬하여 작은것부터 선택하여 사이클이 발생하지 않도록 그래프를 만들어나가면 된다. 원래 N개의 정점이 있는 그래프를 MST로 만들기 위해서는 N-1개의 간선이 필요한데 문제에서는 마을을 두 개의 분리된 마을로 분할한다고 하였다. 그렇기.. 2022. 2. 28. 이전 1 ··· 13 14 15 16 17 18 19 20 다음
