인프런 커뮤니티 질문&답변
작성한 질문수
저.. 시간복잡도 관련 질문입니다.(로직 거의 비슷한 거 같은데, 시간초과가 나서요)
해결된 질문
24.08.05 18:26 작성
·
105
0
안녕하세요, 강의를 듣고 계신 여러분!
여러분의 학습을 돕기 위해 질문 안내를 드리고자 합니다.
1. chatGPT를 이용해보기
단순한 의문은 chatGPT를 이용해도 해답을 찾을 수 있는 경우가 종종 있습니다!
2. 강의의 어떤 부분에 대한 질문이고, 어떤 부분이 궁금한지 명확히 알려주세요!
강의의 어느 파트에서 의문을 느끼고, 어떤 부분이 궁금한지를 명확히 제시해 주시면 답변에 도움이 됩니다!
자신은 어떻게 이해했는지 또한 적어주면 좋습니다!
강의 중 브루트포스 알고리즘 마지막
백준 1342번 행운의 문자열 문제입니다.
순열로 접근한 처음 코드 시간 초과 후
선생님 강의 설명을 들으면서 백트래킹으로 수정했는데요,
근데,, 로직은 거의 차이가 없고
다만 초기화나 선언 등 순서의 차이 같은데,
저는 시간 초과를 해결 하지 못했고,
선생님 코드를 복붙,,, 했더니 성공하더라구요 😓
그래서 어떤 차이 분석을 할 수 있을지 질문 남깁니다.
코드는 아래와 같고 풀이2번을 참고하였습니다.(시간초과 코드입니다)
import sys
input = sys.stdin.readline
s = input()
choice = []
dic = dict()
chars = set()
cnt = 0
for l in s:
chars.add(l)
if l not in dic: dic[l] = 0
dic[l] += 1
def dfs(level):
global cnt, choice, dic
if level == len(s):
cnt += 1
return
for l in chars:
if dic[l] == 0: continue
if (not choice) or (choice[-1] != l):
dic[l] -= 1
choice.append(l)
dfs(level + 1)
dic[l] += 1
choice.pop()
dfs(0)
print(cnt) 답변 2
1
2024. 08. 07. 20:34
안녕하세요. zhu님!
sys.stdin.readline을 사용하신게 문제로 보여집니다.
sys.stdin.readline은 입력의 끝에 개행 문자를 포함합니다. 이를 처리하지 않으면 문자열의 길이가 예상보다 길어질 수 있으며, 이는 문자열을 순회하는 DFS 함수의 성능에 영향을 미칠 수 있습니다.
아무래도 채점 과정에 사용한 문자열 중 개행 문자와 관련된 문자열이 포함되어 시간 초과가 난 것으로 추측됩니다.
따라서 input = sys.stdin.readline을 빼주시거나, s = input().rstrip()로 개행을 제거하여 문자열을 받으면 정상적으로 시간초과 없이 정답처리 되는 것을 확인 하실 수 있습니다.
혹시라도 sys.stdin.realine을 사용하시려면, 다음과 같이 사용하시는걸 추천드립니다.
import sys
input = lambda: sys.stdin.readline().rstrip()
또 궁금하신 점 있으시면 언제든 질문 부탁드립니다.
감사합니다. :)
1
2024. 08. 07. 18:32
안녕하세요, 인프런 AI 인턴입니다.
주신 코드를 분석해보면, 시간 초과의 주된 원인은 아마도 매 dfs 호출 시마다 for l in chars: 루프가 chars의 모든 원소에 대해 실행되기 때문일 것입니다. 여기서 chars는 입력된 문자열에서 중복을 제거한 문자들의 집합입니다. 이 접근법은 특히 문자열 s의 길이가 길고, 사용되는 문자의 종류가 많을 때, 각 dfs 단계에서 많은 반복을 발생시킬 수 있습니다.
최적화 방안으로는, 백트래킹 과정에서 불필요한 반복을 줄이기 위해 이미 사용한 문자나 특정 조건을 만족하지 않는 문자에 대한 검사를 더 효율적으로 할 수 있는 방법을 모색해보는 것입니다. 예를 들어, 선택된 문자열의 조건을 만족하면 다음 문자 선택에 있어서 더 좋은 선택을 할 수 있는 방향으로 로직을 조정할 수 있습니다.
또 하나의 중요한 부분은 실행 시간에 영향을 미칠 수 있는 입력 방식입니다. input = sys.stdin.readline은 입력을 더 빠르게 받기 위해 사용되지만, 문자열의 마지막에 ‘\n’이 포함될 수 있으니 처리에 유의해야 합니다. 만약 코드 상에서 이 부분이 적절히 처리되지 않았다면, 기대와 다른 동작을 할 수 있습니다.
선생님의 코드와 주신 코드 사이의 차이 분석에 있어서, 선언의 순서나 초기화 방식 외에도, 각각의 조건문과 반복문이 알고리즘의 효율성에 어떻게 영향을 미치는지를 세심하게 분석해보는 것이 중요합니다. 특히 백트래킹 알고리즘은 그 구조상 작은 차이가 전체 성능에 큰 영향을 미칠 수 있으므로, 선생님의 코드와의 세부적인 차이를 다시 한번 꼼꼼히 확인해보시기 바랍니다.