6. 감독관 배치 알고리즘 (재귀)

1. 개요

N개의 고사실에 총 감독관 1명과, 부 감독관 K명을 넣어서 최소의 감독관 수를 구하시오.

단, 총 감독관과 부 감독관의 학생 감시 능력은 다르고, 총 감독관은 반드시 한 명 들어가야 함.

N개의 고사실마다 시험보는 학생 수는 다르다.

설명만 길고 문제 자체는 간단하기에 반복문으로 쉽게 풀릴 수 있는 것이지만 재귀로 깔끔하게 풀고 싶어져서

한참을 헤맸다.

왜냐하면 반복 계산이 있는 것도 아니고, 그냥 반복문처럼 돌아가는 재귀였는데 너무 어렵게 생각해서

메모이제이션 써보겠다고 모든 경우를 다 검사하는 재귀 코드를 짰다가 이리저리 돌고 돌다 그냥 마지막에

깔끔히 짰다. 결국은 1차 반복이다.

일단 데이터 크기 1000까지는 빠르게 돌아간다.

다만 5000개 이상 부터 내 컴퓨터 환경에서는 스택 오버플로우 발생해서 그 이상 테스트를 하려면 반복으로 짜야한다.

메모이제이션을 넣어서 조금 더 개선할 수 있는 방법을 찾고 싶지만 코드가 무너질 것 같아서 일단 재귀만 올린다.

재귀 점화식은 모든 방에 총 감독관을 넣었을 때, 모든 경우를 비교하는 Brute_Force()로 작성했다.

조금 더 톡톡 튀는 아이디어가 있어서 속도를 줄일 수 있다면, 좋겠지만 가장 깔끔한건

총 감독관의 능력과 딱 맞아 떨어지는 방을 찾거나, 아니면 총 감독관의 능력을 빼고 남은 인원이

부 감독관의 능려고가 딱 맞아 떨어지는 경우가 이상적이기 때문에 속도를 위해 줄여나간다면

이런 방식으로 찾는게 아마 더 빠를 것이라 생각한다.

하지만 이번에는 가장 간결하게 짜고 싶어서 이 방법을 선택했다.

2. 문제

여러 개의 시험장이 있고 각 시험장마다 임의의 응시자들이 존재한다.

이 응시자들을 모두 감독하기 위한 감독관 배치 문제이다.

감독관은 ‘총감독관’과 ‘부감독관’ 이렇게 두 종류가 있다.둘은 같은 방안에서 감시할 수 있는 응시생들의 숫자가 다르다.

총감독관은 모든 감독관을 통틀어서 오로지 1명만 존재하며 무조건 존재해야 한다.

부감독관은 여러 명을 사용해도 된다.

각 시험장에서 모든 응시생들을 감시해야 한다.

시험장의 수, 시험장 마다 존재하는 응시생의 수가 주어졌을 때 필요한 최소 감독관의 수를 구하는 것이 문제이다.

시험장 마다 존재하는 응시생의 수는 다르다.

테스트 케이스(시험장의 수, 시험장 마다 존재하는 응시생 수, 총감독관 감시가능 응시생 수, 부감독관 감시가능 응시생 수)는 30개가 주어진다.

작성한 프로그램이 모든 결과를 도출하는데 걸리는 시간은 1초 이내여야 한다.

3. 코드

3-1) 각 방의 인원에 따른 총 감독관 계산 알고리즘

3-2) 각 방의 인원에 따른 부 감독관 계산 알고리즘

3-3) n까지의 최소 감독관 구하기 알고리즘

3-4) 출력 데이터 크기 5

3-5) 출력 데이터 크기 10

3-6) 출력 데이터 크기 100

3-7) 출력 데이터 크기 1000

4. 정리

오늘 정말 운좋게도 삼성전자 서류에 합격했다.

지금껏 4번 다 떨어져서 SSAT 시험 한 번 못봤는데, 정말 마지막이라고 생각하고 지원한 것이 합격해서 다행이다.

비록, 다음 테스트가 SW개발 직군이기 SSAT가 아닌 코딩 역량 테스트 직무, 즉 알고리즘 테스트를 치르겠지만

더욱 더 연구하고 준비하고 공부해서 반드시 내가 할 수 있는 만큼 올라가보고 싶다.

분명 괴물들 많이 만나고 오겠지.

두려우면서도 한편으론 기대된다.