PCCP 모의고사 1회차 - 2번 문제
코딩테스트 준비
해당 썸네일은 Wonkook Lee 님이 만드신 Thumbnail-Maker 를 이용하였습니다
바로 문제로 들어가자
🥢 문제
당신이 다니는 학교는 매년 체육대회를 합니다. 체육대회는 여러 종목에 대해 각 반의 해당 종목 대표가 1명씩 나와 대결을 하며, 한 학생은 최대 한개의 종목 대표만 할 수 있습니다. 당신의 반에서도 한 종목당 1명의 대표를 뽑으려고 합니다.
학생들마다 각 종목에 대한 능력이 다르지만 이 능력은 수치화되어 있어 미리 알 수 있습니다. 당신의 반의 전략은 각 종목 대표의 해당 종목에 대한 능력치의 합을 최대화하는 것입니다.
다음은 당신의 반 학생이 5명이고, 종목의 개수가 3개이며, 각 종목에 대한 학생들의 능력치가 아래 표와 같을 때, 각 종목의 대표를 뽑는 예시입니다.
학생 테니스 탁구 수영 석환 40 10 10 영재 20 5 0 인용 30 30 30 정현 70 0 70 준모 100 100 100 테니스 대표로 준모, 탁구 대표로 인용, 수영 대표로 정현을 뽑는다면, 세 명의 각 종목에 대한 능력치의 합은 200(=100+30+70)이 됩니다.
하지만, 테니스 대표로 석환, 탁구 대표로 준모, 수영 대표로 정현을 뽑는다면 세 명의 각 종목에 대한 능력치 합은 210(=40+100+70)이 됩니다. 이 경우가 당신의 반의 각 종목 대표의 능력치 합이 최대가 되는 경우입니다.
당신의 반 학생들의 각 종목에 대한 능력치를 나타내는 2차원 정수 배열 ability가 주어졌을 때, 선발된 대표들의 해당 종목에 대한 능력치 합의 최대값을 return 하는 solution 함수를 완성하시오.
🏄🏾♂️ 솔루션
제한사항이 10 by 10이다. 그렇게 되면 최악의 케이스에서 10! 만큼의 연산이 필요하고 이는 3,628,800 으로 완전 탐색이 가능하다.
- DFS를 통해 처리해야 좋을 것 같다.
- BFS로 처리를 할 때 이미 선택된 학생을 체크하는 부분에서 시간복잡도가 증가한다.
- 얼마나 증가하냐? 최악의 경우 10 * 10 을 곱해야 한다 (모든 학생 점수 체크 * 특정 종목에 해당 학생 배치 가능한지 경우의 수)
- 그렇게 되면 전체 연산이 3억을 넘어가게 되므로 시간초과가 난다.
- python의 permutations 를 써도 된다.
- 이 부분은 개인적으로 지양하는데 내부 메소드에 의존하면 기본적 코드 실력이 떨어지는 것 같다.
코드
def dfs(ability, score, col):
global answer, people, sports, visited
if col== sports:
answer = max(score, answer)
return
for p in range(people):
if visited[p]:
continue
visited[p] = True
dfs(ability, score+ability[p][col], col+1)
visited[p] = False
def solution(ability):
global answer, people, sports, visited
answer, people, sports = 0, len(ability), len(ability[0])
visited = [False for _ in range(people)]
dfs(ability, 0, 0)
return answer
🏐 분석 및 후기
- 시간복잡도 : 앞서 말했듯 최악의 경우 10! 만큼의 연산 / 수식으로 표현하면
- n = 스포츠 종목
- m = 사람 수
- Complexity = O(m!) / n에 따라 작아지지만 Big-O 표기법 사용
- 공간복잡도 : O(m) - visited 체크용
앞서 BFS로 풀지 말아야 할 이유를 길게 설명했는데 그 이유는 내가 BFS로 풀었기 때문이다. 당연히 시간초과가 떴다.
DFS 써야 하는 류의 문제들을 익히자~!
