분류 전체보기282 1700. 멀티탭 스케줄링 (Python) 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 페이지 교체 알고리즘 중 하나인 OPT(Optimal Replacement, 최적 교체)를 생각하면 된다. 일단 멀티탭 구멍에 맞게 각 전기용품을 꽂은 다음 현재 멀티탭에 없는 전기용품을 사용해야 할 경우 멀티탭을 사용 중인 용품 중 가장 먼 미래에 사용될 용품의 플러그를 빼고 새로운 용품의 플러그를 꽂도록 구현해주면 된다. 코드 import sys # 제거해야 할 전기용품을 찾기 위한 함수 def removePlug(idx): maxIdx = -1 ite.. 2022. 3. 7. 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. 이전 1 ··· 15 16 17 18 19 20 21 ··· 47 다음
