Cherry & Cherish

문제 : 퀵 정렬을 구현해 N개의 정수를 정렬해 리스트 A에 넣고, A[N//2]에 저장된 값을 출력하는 프로그램을 만드시오. 접근 : 퀵 정렬 알고리즘을 적용했다. 풀이 : def quick_sort(arr): if len(arr) pivot: high.append(num) else: equal.append(num) return quick_sort(low) + equal + quick_sort(high) T = int(input()) for tc in range(1, T+1): N = int(input()) arr = list(map(int, input().split())) ans = quick_sort(arr) print(f'#{tc} {ans[N//2]}') 사실, 정렬 라이브러리로 훨씬 간편하게 ..

문제 : 자연수 N에 몇 번의 연산을 통해 다른 자연수 M을 만들려고 한다. 사용할 수 있는 연산이 +1, -1, *2, -10 네 가지라고 할 때 최소 몇 번의 연산을 거쳐야 하는지 알아내는 프로그램을 만드시오. 단, 연산의 중간 결과도 항상 백만 이하의 자연수여야 한다. 예를 들어 N=2, M=7인 경우, (2+1) *2 +1 = 7이므로 최소 3번의 연산이 필요한다. 접근 : bfs를 활용해 방문 체크 후 연산을 진행한다. 풀이 : from collections import deque def bfs(N, M): queue = deque() queue.append((N, 0)) check = {} while queue: item, count = queue.popleft() if check.get(it..

문제 : 화물이 실려 있는 N개의 컨테이너를 M대의 트럭으로 A도시에서 B도시로 운반하려고 한다. 트럭당 한 개의 컨테이너를 운반 할 수 있고, 트럭의 적재용량을 초과하는 컨테이너는 운반할 수 없다. 컨테이너마다 실린 화물의 무게와 트럭마다의 적재용량이 주어지고, A도시에서 B도시로 최대 M대의 트럭이 편도로 한번 만 운행한다고 한다. 이때 이동한 화물의 총 중량이 최대가 되도록 컨테이너를 옮겼다면, 옮겨진 화물의 전체 무게가 얼마인지 출력하는 프로그램을 만드시오. 화물을 싣지 못한 트럭이 있을 수도 있고, 남는 화물이 있을 수도 있다. 컨테이너를 한 개도 옮길 수 없는 경우 0을 출력한다. 접근 : 그리디 문제이므로, 정렬을 활용해 문제를 풀 수 있다는 접근은 쉽다. 가장 적재용량이 높은 트럭이 가장 ..