Cherry & Cherish

문제 : 서로 다른 정수 N개가 주어지면 정렬한 상태로 리스트 A에 저장한다. 그런 다음 리스트 B에 저장된 M개의 정수에 대해 A에 들어있는 수인지 이진 탐색을 통해 확인하려고 한다. 전체 탐색 구간의 시작과 끝 인덱스를 l과 r이라고 하면, 중심 원소의 인덱스 m=(l+r)//2 이고, 이진 탐색의 왼쪽 구간은 l부터 m-1, 오른쪽 구간은 m+1부터 r이 된다. 이때 B에 속한 어떤 수가 A에 들어있으면서, 동시에 탐색 과정에서 양쪽구간을 번갈아 선택하게 되는 숫자의 개수를 알아보려고 한다. 다음은 10개의 정수가 저장된 리스트 A에서 이진 탐색으로 6을 찾는 예이다. 6은 탐색 과정에서 양쪽을 번갈아 가며 선택하게 된다. 예를 들어 10을 찾는 경우 오른쪽-오른쪽 구간을 선택하므로 조건에 맞지 않..

문제 : 퀵 정렬을 구현해 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..

문제 : 24시간 운영되는 물류센터에는 화물을 싣고 내리는 도크가 설치되어 있다. 0시부터 다음날 0시 이전까지 A도크의 사용신청을 확인해 최대한 많은 화물차가 화물을 싣고 내릴 수 있도록 하면, 최대 몇 대의 화물차가 이용할 수 있는지 알아내 출력하는 프로그램을 만드시오. 신청서에는 작업 시작 시간과 완료 시간이 매시 정각을 기준으로 표시되어 있고, 앞 작업의 종료와 동시에 다음 작업을 시작할 수 있다. 예를 들어 앞 작업의 종료 시간이 5시면 다음 작업의 시작 시간은 5시부터 가능하다. 접근 : 종료 시간을 기준으로 정렬해서 값을 갱신한다. 풀이 : T = int(input()) for tc in range(1, T+1): N = int(input()) arr = [list(map(int, input..

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