인프런 커뮤니티 질문&답변
작성한 질문수
이 코드가 더 효율적이죠?
작성
·
83
0
앞 강의인 바둑이 승차 영상을 보며 떠올렸습니다.
n,m = map(int,input().split())
data = [list(map(int,input().split())) for _ in range(n)]
rst = 0
tot = sum(a for a,b in data)
def dfs(num,s,t,tsum):
global rst
if tot - tsum + s < rst:
return
if t > m:
return
if n == num:
rst = max(rst,s)
else:
dfs(num + 1,s + data[num][0],t+data[num][1],tsum+data[num][0])
dfs(num + 1, s, t, tsum + data[num][0])
dfs(0,0,0,0)
print(rst)답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
코드의 효율성에 대한 질문을 주셨네요, 코딩코딩코딩코님.
제공해주신 코드는 깊이 우선 탐색(DFS)를 활용하여 문제를 해결하는 알고리즘입니다. 특정 조건을 만족하는 경우 탐색을 조기에 종료하도록 잘 설계되어 있습니다. 예를 들어, tot - tsum + s < rst 조건을 통해 현재까지의 합(s)에 남은 가능한 최대 합(tot - tsum)을 더해도 이미 찾은 최대 결과(rst)보다 작다면 더 이상 탐색을 진행하지 않습니다. 이는 불필요한 탐색을 줄이고 효율성을 높이는 좋은 방법입니다.
다만, 효율성은 문제의 조건과 입력 데이터의 크기에 따라 달라질 수 있습니다. 복잡한 문제나 큰 데이터가 주어지면 이 코드의 실행 시간도 길어질 수 있습니다. 따라서, 코드의 효율성은 상대적이며, 다양한 테스트 케이스를 통해 검증해 보는 것이 좋습니다.
코드 최적화에 있어서는 다음과 같은 점을 고려할 수 있습니다:
- 재귀 호출의 최적화: 호출되는 재귀 함수의 수를 줄이거나, 불필요한 호출을 줄이는 방법 검토
- 메모이제이션(Memoization) 적용: 이미 계산한 결과를 저장하여 재사용
- 병렬 처리: 가능하다면 병렬 처리를 적용하여 연산 속도 향상
물론 이러한 최적화 방법이 모든 문제에 적용 가능한 것은 아니므로, 문제의 특성을 잘 분석하고 적합한 방법을 선택하는 것이 중요합니다.
도움이 되셨기를 바랍니다. 추가 질문이 있으시면 언제든지 문의해주세요.