-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
[2-5] 최대선호음식 시간초과..
23.12.19 14:11 작성 조회수 126
0
import sys
N, D, K = map(int, input().split())
bits = [2 ** i for i in range(16)]
st = [0 for i in range(N)]
res = 0
def and_calc(a, b):
if a & b == b:
return 1
return 0
def DFS(L, S, bit):
global res
if L == K:
temp = 0
for i in range(len(st)):
temp += and_calc(bit, st[i])
res = max(temp, res)
return
for i in range(S, D + 1):
DFS(L + 1, i + 1, bit + bits[i])
return
for i in range(N): # N
input_value = list(map(int, sys.stdin.readline().split()))
for bit in range(len(input_value)):
if bit == 0:
continue
st[i] += bits[input_value[bit] - 1]
DFS(0, 0, 0)
print(res)
영상과 유사하게 구현을 했는데도 시간 초과가 나서요..
어디가 문제인지 잘 모르겠습니다..
파이썬이라서 그런건지.. 😢
답변을 작성해보세요.
0
인프런 AI 인턴
2023.12.21
안녕하세요, 인프런 AI 인턴입니다. 사용자님께서 제공해주신 코드를 봤을 때 Python의 성능 문제가 있어 시간 초과가 발생할 수 있는 몇 가지 부분을 짚어볼 수 있습니다.
- DFS 호출
- K가 클 경우 DFS의 깊이가 깊어지면서 시간 복잡도가 기하급수적으로 증가합니다. K와 D의 값에 따라 시간 초과가 발생할 수 있습니다.
- 비트 연산 최적화
- Python에서 비트 연산이 C++에 비해 상대적으로 느릴 수 있습니다. 하지만, 이 문제는 비트 연산 자체보다는 DFS에서 중복된 상태를 방문하는 것이 더 큰 문제일 가능성이 높습니다.
- 입력 처리 속도
sys.stdin.readline()을 사용하셨는데, 이는 이미 입력 받는데 걸리는 시간을 최소화하는 방법입니다.
해결 방법으로는 다음을 고려해보실 수 있습니다:
- 알고리즘 개선
- 백트래킹을 사용하여 필요 없는 상태는 빠르게 배제하고 DFS를 더 빠르게 하도록 할 수 있습니다.
- 불필요한 연산 제거
- 반복문 내에서 불필요한 연산이 없는지 점검해보세요. 예를 들어,
and_calc함수 내부에서return 1이나return 0대신bool타입을 직접 반환하는 것이 약간의 성능 향상을 가져올 수 있습니다.
- 더 빠른 언어 사용
- Python이 C++에 비해 속도가 느린 것은 사실입니다. 시간이 중요한 문제에서는 C++과 같은 성능이 더 뛰어난 언어를 고려해볼 수도 있습니다.
위의 내용을 참고하여 코드의 성능을 개선해보시길 바랍니다. 추가적으로 도움이 필요하시면 인프런 Q&A나 커뮤니티 포럼을 통해 도움을 요청해보세요.
답변 1