문제 이해하기
두 개의 리스트 cores와 tasks가 주어졌다고 가정해 보겠습니다. cores[i]는 i번째 서버에서 사용 가능한 코어 수를 의미하고, tasks[i]는 해당 작업을 실행하는 데 필요한 코어 수를 의미합니다. 각 작업은 반드시 단 하나의 서버에서만 실행되어야 하며, 하나의 서버는 여러 개의 작업을 동시에 맡을 수 있습니다. 이때 주어진 코어 용량만으로 모든 작업을 실행할 수 있는지 판단하는 것이 목표입니다.
예를 들어 입력이 cores = [10, 7], tasks = [7, 3, 2, 2, 1]이라면 결과는 True입니다. 첫 번째 서버(코어 10개)에 tasks[0](7)과 tasks[1](3)을 배치하면 정확히 10이 되고, 나머지 작업들(2 + 2 + 1 = 5)은 두 번째 서버(코어 7개)에 모두 들어가기 때문입니다.
풀이 접근 방식: 백트래킹
이 문제는 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 핵심 아이디어는 각 작업을 순서대로 꺼내면서, 현재 배정 가능한 모든 서버에 하나씩 넣어보고 실패하면 이전 상태로 되돌아가 다른 조합을 시도하는 것입니다.
구체적인 진행 순서는 다음과 같습니다.
- solve() 함수를 정의합니다. 이 함수는 cores와 tasks 두 매개변수를 받습니다.
- tasks가 비어 있다면 모든 작업이 성공적으로 배정된 것이므로 True를 반환합니다.
- i를 0부터 cores의 길이 - 1까지 반복하면서:
- cores[i]가 tasks[0]보다 크거나 같으면, cores[i]에서 tasks[0]만큼 차감합니다.
- solve(cores, 첫 번째 작업을 제외한 tasks)의 결과가 참이면 True를 반환합니다.
- 실패했다면 cores[i]에 tasks[0]을 다시 더해 원래 상태로 복원합니다.
- 모든 서버에 대한 시도가 끝날 때까지 해결책을 찾지 못하면 False를 반환합니다.
예제 코드
다음 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.
def solve(cores, tasks): if not tasks: return True for i in range(len(cores)): if cores[i] >= tasks[0]: cores[i] -= tasks[0] if solve(cores, tasks[1:]): return True cores[i] += tasks[0] return False cores = [10, 7] tasks = [7, 3, 2, 2, 1] print(solve(cores, tasks))
입력
[10, 7], [7, 3, 2, 2, 1]
출력
True
동작 원리와 성능 고려 사항
재귀 호출이 진행될 때마다 남은 작업 목록(tasks[1:])이 하나씩 줄어들고, 각 단계에서 코어를 임시로 할당했다가 실패 시 복원하는 과정을 반복합니다. 이렇게 하면 가능한 모든 배치 조합을 빠짐없이 탐색할 수 있습니다.
다만 최악의 경우 시간 복잡도는 서버 수를 n, 작업 수를 m이라 할 때 지수적으로 증가할 수 있습니다. 실전에서는 필요한 코어가 많은 작업부터 먼저 배정하도록 tasks를 내림차순으로 정렬하면 탐색 공간을 크게 줄여 성능을 개선할 수 있습니다.