🔗문제 링크
✅ 문제 유형
백트래킹, 브루트포스
🤔 문제 풀이
6개의 팀이 축구 조별 예선 과정에서 승,무,패를 획득할 수 있는 경우의 수를 찾는 문제입니다. 6개의 팀이 모두 한 경기씩 치르기 때문에 조합을 생각하여 6C2 = 15 로 한 조에 치러지는 모든 경기의 수를 알 수 있습니다.
한 경기당 3개의 결과(승, 무, 패)가 나타날 수 있습니다. 한 경기당 3개 총 경기는 15개이므로 시간 복잡도는 3^15 로 표현할 수 있습니다. 3^15 는 14,000,000이므로 1초에 코드가 1억 번 돌아간다고 생각하면 코드를 잘 짠다면 충분히 돌아갈 것으로 예상할 수 있습니다.
저는 모든 경기의 경우의 수를 완전 탐색하여 result 딕셔너리에 기록하였습니다. 그렇기 때문에 입력된 경기 내용이 result 딕셔너리에 있다면 1을 출력하고 딕셔너리에 경기 내용이 없다면 0을 출력하는 코드를 설계했습니다.
모든 경기의 경우의 수 탐색은 완전 탐색 기법의 하나인 백트래킹으로 구현하였습니다. 백트래킹 코드는 아래와 같습니다. 현재 경기의 결과를 note 리스트의 위치에 알맞게 수정합니다. 그리고 재귀 함수를 통해 다음 대진표의 경기를 진행시킵니다.
---
Input
a,b : 경기를 치를 두 팀
status : 승,무,패를 결정
note : 현재까지 기록한 경기 기록
depth : 현재까지 진행한 경기의 수
---
def match(a,b,status,note,depth) :
# 현재 경기 기록
if status == 0: #승
aIDX = position[a]
bIDX = position[b]
note[aIDX] += 1
note[bIDX+2] += 1
if answer[aIDX] < note[aIDX] or answer[bIDX+2] < note[bIDX+2] :
return
elif status == 1: #무
aIDX = position[a]
bIDX = position[b]
note[aIDX+1] += 1
note[bIDX+1] += 1
if answer[aIDX+1] < note[aIDX+1] or answer[bIDX+1] < note[bIDX+1] :
return
elif status == 2: # 패
aIDX = position[a]
bIDX = position[b]
note[aIDX + 2] += 1
note[bIDX] += 1
if answer[aIDX+2] < note[aIDX+2] or answer[bIDX] < note[bIDX] :
return
if depth == 15: #15경기를 모두 진행했다면
result[str(note)] = 1
return
nextA ,nextB = allMatch[depth] #다음 경기의 두 상대
match(nextA,nextB,0,note[:],depth+1) #다음 경기로 재귀
match(nextA, nextB, 1, note[:], depth + 1)
match(nextA, nextB, 2, note[:], depth + 1)🚀 문제 해결
# 트러블 슈팅 이전의 코드
def match(a,b,status,note,depth) :
# 현재 경기 기록
if status == 0: #승
aIDX = position[a]
bIDX = position[b]
note[aIDX] += 1
note[bIDX+2] += 1
elif status == 1: #무
aIDX = position[a]
bIDX = position[b]
note[aIDX+1] += 1
note[bIDX+1] += 1
elif status == 2: # 패
aIDX = position[a]
bIDX = position[b]
note[aIDX + 2] += 1
note[bIDX] += 1
if depth == 15: #15경기를 모두 진행했다면
result[str(note)] = 1
return
nextA ,nextB = allMatch[depth] #다음 경기의 두 상대
match(nextA,nextB,0,note[:],depth+1) #다음 경기로 재귀
match(nextA, nextB, 1, note[:], depth + 1)
match(nextA, nextB, 2, note[:], depth + 1)저는 맨 처음에 match 함수 안에 승, 무, 패를 기록하여 모든 경기의 경우의 수를 조사하는 알고리즘을 짰고 복잡도가 3^15 이기 때문에 통과할 줄 알았습니다. 하지만 시간 초과가 났고 로컬에서 테스트 케이스 입력 후 결과가 나오기까지 10초가 지나 결과가 나왔습니다.
우선 재귀문을 단순하게 만들었기 때문에 기본적인 코드의 연산수(1초당 1억) 문제는 아닌 걸로 생각했습니다. 혹시 내가 설계한 시간 복잡도와 실제 코드가 돌아가는 시간 복잡도가 다른가? 라는 생각이 들어 전역 변수를 CNT를 재귀문에 선언했고, 함수 시작 시 CNT 값을 +1 해주는 로직을 추가해 총 함수의 호출이 몇 번 일어나는지 검사해 봤습니다.
검사 결과 처음 설계단에서 생각했던 복잡도가 정확히 맞았고, 총 함수의 호출은(3^15 + 3^14 + ‘’’ ‘’’ + 3^2+3^1) 로 총 2000만 번이 조금 넘게 함수의 호출이 이루어짐을 확인할 수 있었습니다.
1초에 1억이 돌아간다는 가정하에 함수의 코드도 간단하기 때문에 충분히 코드가 돌아갈 것으로 예상되었지만, 왜 몇 십 배 느린 실행 속도를 보였을까요? 바로 함수의 오버헤드 때문입니다. 함수는 컨텍스트 스위칭을 해야 하는 오버헤드를 가지고 있기 때문에 컨텍스트 스위칭이 2000만 번 넘게 실행 되었으니 매우 느렸을 수 밖에 없습니다.
그렇다면 어떻게 위의 문제를 해결했을까요? 🤔 저는 두 가지 방법을 생각했습니다.
🌟 i) 꼬리재귀를 이용한 컴파일러 최적화 ii) 완전 탐색 과정 가지치기
재귀 함수의 컨텍스트 스위칭을 없애기 위해 컴파일러를 최적화하는 재귀 방식인 꼬리 재귀도 해당 코드에서는 승, 무, 패 세 가지로 나뉘기 때문에 꼬리 재귀를 사용할 수 없었다고 생각해 2번 가지치기 방법을 선택하였습니다.
가지치기의 경우 생각해봅시다. 현재 알고리즘은 모든 경기의 내용을 탐색하고 있습니다. 잘 생각해 보면 굳이 그럴 필요가 있을까요 ? 만약 A팀이 5승을 거두었다고 생각해 봅시다. A 팀이 5승을 거둔 경우가 있는지 찾기 위해 재귀하는 과정에서 1패라도 패한 경우 이후의 내용을 탐색해 봤자 더 의미가 있을까요 ? 위의 가지치기 과정을 코드로 구현한다면 현재 팀의 승, 무, 패를 기록할 때 기록한 값과 입력 시 주어지는 승, 무, 패 각각을 비교해 기록 내용이 크다면 더 이상의 탐색은 무의미하기 때문에 함수를 종료시키면 됩니다.
if status == 0: #승
aIDX = position[a]
bIDX = position[b]
note[aIDX] += 1
note[bIDX+2] += 1
#아래의 if문을 이용한 가지치기
if answer[aIDX] < note[aIDX] or answer[bIDX+2] < note[bIDX+2] :
return📖 코드
result = {}
team = ['A','B','C','D','E','F']
allMatch = []
for i in range(6):
for j in range(i+1,6):
allMatch.append([team[i],team[j]])
position = {'A': 0, 'B': 3, 'C': 6, 'D': 9, 'E': 12, 'F': 15}
def match(a,b,status,note,depth) :
if status == 0: #승
aIDX = position[a]
bIDX = position[b]
note[aIDX] += 1
note[bIDX+2] += 1
if answer[aIDX] < note[aIDX] or answer[bIDX+2] < note[bIDX+2] :
return
elif status == 1: #무
aIDX = position[a]
bIDX = position[b]
note[aIDX+1] += 1
note[bIDX+1] += 1
if answer[aIDX+1] < note[aIDX+1] or answer[bIDX+1] < note[bIDX+1] :
return
elif status == 2: # 패
aIDX = position[a]
bIDX = position[b]
note[aIDX + 2] += 1
note[bIDX] += 1
if answer[aIDX+2] < note[aIDX+2] or answer[bIDX] < note[bIDX] :
return
if depth == 15:
result[str(note)] = 1
return
nextA ,nextB = allMatch[depth]
match(nextA,nextB,0,note[:],depth+1)
match(nextA, nextB, 1, note[:], depth + 1)
match(nextA, nextB, 2, note[:], depth + 1)
for i in range(4):
answer = list(map(int,input().split()))
note = answer[:]
match('A', 'B', 0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 1)
match('A', 'B', 1, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 1)
match('A', 'B', 2, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 1)
if result.get(str(answer)) != None :
print(1, end=' ')
else:
print(0, end=' ')배운 것
- 백트래킹할 때 깊은 복사,얕은 복사시를 한 번 더 짚고 넘어가자.
- 시간이 애매할 때는 가지치기를 생각하자.
- 꼬리재귀는 저렇게 반복적인 호출에서 불가능하다.
refactoring
위의 과정을 가독이 좋게 리팩터링 하였습니다.
(1600 Byte -> 1000 Byte)
result = {}
team = ['A', 'B', 'C', 'D', 'E', 'F']
allMatch = []
for i in range(6):
for j in range(i + 1, 6):
allMatch.append([team[i], team[j]])
position = {'A': 0, 'B': 3, 'C': 6, 'D': 9, 'E': 12, 'F': 15}
def match(depth, note):
if depth == 15:
result[str(note)] = True
return
for i in range(len(note)):
if note[i] > answer[i]:
return
a, b = allMatch[depth]
aIDX = position[a]
bIDX = position[b]
# 승
note_win = note[:]
note_win[aIDX] += 1
note_win[bIDX + 2] += 1
match(depth + 1, note_win[:])
# 무
note_draw = note[:]
note_draw[aIDX + 1] += 1
note_draw[bIDX + 1] += 1
match(depth + 1, note_draw[:])
# 패
note_lose = note[:]
note_lose[aIDX + 2] += 1
note_lose[bIDX] += 1
match(depth + 1, note_lose[:])
for _ in range(4):
answer = list(map(int, input().split()))
match(0,[0]*18)
if str(answer) in result:
print(1, end=' ')
else:
print(0, end= ' ')
