세상을 바꾸는 데이터

문제 링크: https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 풀이: 이 문제의 핵심문장은 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙이다. 먼저 서류심사 순위를 기준으로 오름차순 정렬하자. 서류심사만 기준으로 하면 순위 1등을 제외한 나머지는 선발 대상이 아니다. 여기서 선발 인원수 1을 증가시킨다. (서류심사 1등은 무조건 선발되..

문제 링크: https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 30의 배수는 곧 3의 배수와 같은 말이다. 어떤 수가 3의 배수가 되려면 수에 0이 포함되고, 각 자리 숫자의 합이 3의 배수가 되야 한다. 리스트에 있는 숫자를 문자로 변환하려면 . join을 이용하면 된다. # 10610번 30 # 3의 배수 조건은 일의 자리가 0이거나 각 자리 수의 합이 3으로 나누어 떨어져야 함. n = list(input()) n.sort(reverse=Tr..

문제 링크: https://www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net 앞서 풀은 거스름돈 문제와 유형이 비슷한 문제이다. 작동 시간이 가장 작은 전자레인지의 배수로 전자레인지들로 구성되어 있기 때문에 가장 긴 작동 시간부터 차례대로 돌리면 된다. # 10162번 전자레인지 t = int(input()) # 작동 시간 oper_time = [300, 60, 10] ans = [] count = 0 # 10으로 나누어 떨어지면 -1 출력 if t ..

문제 링크: https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 병렬로 연결하는 것을 우선순위로 고려해야 한다. 입력값(로프가 버틸 수 있는 최대 중량)을 오름차순으로 정렬하고, 전체 로프 사용에서 1개 로프만 사용하는 순서대로 최댓값을 도출한다. max((가장 적게 버틸 수 있는 중량 * n), (2번째로 버틸 수 있는 중량 * (n-1)), ........ , (가장 많이 버틸 수 있는 중량 * 1)) # 2217번 로프 # 그리디 알..

문제 링크: https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 거스름돈 = 1000엔 - 입력값 거스름돈이 작은 수의 배수만큼 있으므로 큰 동전부터 거슬러주면 된다. (그리디 알고리즘의 최적의 해) 동전들의 종류 리스트인 coins를 만들어 큰 동전부터 차례대로 개수를 세주면 된다. # 5585번 거스름돈 #1. 500엔부터 순차적으로 거스름돈을 주면 된다. n = int(input()) # 거스름돈 money = 1000 ..

문제 링크: https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 가장 먼저 '-'를 split( ) 이용해 문자를 나눈다. 나눈 문자 중 +연산이 있는 문자는 더하기로 계산하고 이를 num 변수에 넣는다. 최종적으로 모든 문자에 -를 적용하여 최솟값을 도출한다. 여기서 처음 숫자(num[0])은 -를 앞에 붙이지 않기 때문에 제외한다. # 1541번 잃어버린 괄호 a = input().split('-') num = [] for i..

문제 링크: https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net B에 있는 수를 재배열하면 안 되므로 B의 인덱스 번호를 이용해 문제를 풀어보자. A를 내림차순 정렬, B_index 변수를 만들어 오름차순으로 정렬한 인덱스 번호 값을 반환한다. 이는 S의 최솟값을 도출하기 위해서 실시한다. (A의 가장 큰 값과 B의 가장 작은 값이 곱해져야 한다.) # 1026번 보물 # 1. a를 내림차순 정렬, b 오름차순을 인덱스 번호로 정렬 # 2...

문제 출처: https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 회의실 배정 문제에서 가장 중요한 문장은 " 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. "이다. 해결 방법은 그리디 알고리즘과 정렬을 이용하면 된다. 첫 번째 아이디어: 회의 시간마다 끝나는 시간을 기준으로 오름차순 정렬한 다음에 다음 회의 시작 시간이 >= 회의 끝 나는 시간이라면 최적의 해를 도출할 수 있을까? 하지만 다음과 같은 상황을 고려해야 한다. (1, 5) (5, 7) (5, 6) 위와 같이 입력을 받았다면 (1, 5) ..