전체 글

[Beakjoon] 백준 2217번 Python

Beakjoon 2217, 로프 solved.ac Silver4 Greedy알고리즘 문제 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도..

[Beakjoon] 백준 2036번 Python

Beakjoon 2036, 수열의 점수 solved.ac Gold5 Greedy알고리즘 문제 n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 정수의 곱이 점수가 된다. 이를 반복하여 수열에 아무 수도 남지 않게 되었을 때, 점수의 총 합의 최대를 구하는 프로그램을 작성하시오. 예를 들어 -1, 5, -3, 5, 1과 같은 수열이 있다고 하자. 먼저 1을 제거하고, 다음으로는 5와 5를 제거하고, 다음에는 -1과 -3을 제거했다고 하자. 이 경우 각각 점수가 1, 25, 3이 되어 총 합이 29가 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주..

[Beakjoon] 백준 1715번 Python

Beakjoon 1715, 카드 정렬하기 solved.ac Gold4 Greedy알고리즘, 우선순위 큐 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 ..

[Beakjoon] 백준 1931번 Python

Beakjoon 1931, 회의실 배정 solved.ac Silver1 Greedy 알고리즘 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용 표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에..

[Beakjoon] 백준 11000번 Python

Beakjoon 11000, 강의실 배정 solved.ac Gold5 Greedy 알고리즘, 우선순위 큐 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) 출력 강의실의 개수를 출력하라. Solution import heapq n ..

[Beakjoon] 백준 10610번 Python

Beakjoon 10610, 30 solved.ac Silver5 Greedy 알고리즘 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어 한다. 미르코를 도와 그가 만들고 싶어 하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라. Solution number = input() numList = list(map(int, str(number))) numList.sort(..

[군대] 지방사는 사람들을 위한 자대 후방으로 빠지는 방법

100% 후방으로 빠진다는 장담은 못하지만 경험상 80% 이상은 후방으로 자대 배치를 받았습니다. 현재는 2작사 예하 사단에서 운전병 모집을 하고 있지 않으니 모집을 시작하면 아래의 내용을 참고해주세요 2작사 예하 신병교육대의 운전병으로 입대 2작전사령부 예하의 신병교육대에 운전병으로 입대를 하게 되면 100% 경산에 있는 2야전 수송 교육연대(2수교)로 배치를 받게 됩니다. 2 작사 예하의 신병교육대를 가지고 있는 사단 31사단 32사단 35사단 37사단 39사단 50사단 53사단 광주 충남 공주 전북 임실 충북 증평 경남 함안 대구 부산 저는 충북 증평에 있는 37사단 신병교육대대 2중대에 입대해서 2 야수교로 갔습니다. 운전 경력이 거의 없었던 저는 중형차량 운전병 보직을 받았고 4주간 교육 끝에 ..

[Beakjoon] 백준 2875번 Python

Beakjoon 2875, 대회 or 인턴 solved.ac Bronze3 Greedy 알고리즘 문제 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.) 백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다. 여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야 하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다. 입력 N을 입력받는다. N..

[Beakjoon] 백준 11047번 Python

Beakjoon 11047, 동전 0 solved.ac Silver4 Greedy 알고리즘 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. Solution coin, money = map(int, input().s..

[Greedy] 1이 될때까지

이것이 코딩 테스트다 with Python 기출 : 2018 E 기업 알고리즘 대회 Greedy 알고리즘 문제 어떠한 수 N이 1이 될 때까지의 다음 두 과정을 반복적으로 선택하여 수행한다. N에서 1을 뺀다. N을 K로 나눈다. N이 K로 나누어 떨어질 경우 N을 K로 나누고 그렇지 않을 경우 N에서 1을 뺀다. 입력조건 첫째줄에 N(2 ≤ N ≤ 100,000) 과 K(2 ≤ K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 K보다 항상 크거나 같다. 출력조건 첫째줄에 N이 1이 될때까지 1번 혹은 2번의 과정을 수행해야하는 횟수의 최솟값을 출력한다. Solution n, k = map(int, input().split()) count = 0 while ..