1-K 시간초과 문의드립니다.
https://www.acmicpc.net/source/61767351
처음에 선생님이 알려주신 알고리즘은 전혀 생각 못해서
초기에 했던 방법인데요,
순열을 이용하면서
시간초과 안 나오게 하는 방법이 있을까요?^^
답변 2
1
안녕하세요, 인프런 AI 인턴이에요.
주어진 문제에서 시간초과가 발생하는 이유는 단순히 문제를 전체적으로 탐색하기 때문입니다. 따라서, 이 문제의 경우 순열을 이용한 방법보다는 백트래킹을 이용하는 것이 좋습니다. 백트래킹을 이용하면 불필요한 탐색을 줄일 수 있어서 시간 복잡도를 줄일 수 있습니다.
또한, 정답과 상관없는 탐색을 줄이기 위해 가지치기(pruning) 기법을 이용할 수 있습니다. 가지치기란, 탐색 중에 더 이상 의미 없는 노드를 탐색하지 않고 가지치기하여 시간 복잡도를 줄이는 기법입니다.
따라서, 순열 대신 백트래킹과 가지치기를 이용하면 시간초과를 줄일 수 있을 것입니다. 이에 대한 자세한 설명과 코드는 인터넷에서 찾아볼 수 있으니 참고해보시길 바랍니다.
좋은 결과 있길 바라요! 감사합니다.
4 - A
0
29
2
코딩살구클럽 입장이 안됩니다
0
76
2
4-F 경우의 수 질문입니다.
0
34
2
코딩살구클럽 가입이 안됩니다.
0
79
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
60
1
교안 158페이지 문의드립니다
0
46
2
코딩살구클럽 관련 건의사항
0
117
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
45
1
진행 방법 질문드립니다!
0
81
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
64
2
2주차 개념#12 트리 순회
0
32
2
백준사이트가 종료된다고 합니다.
0
316
2
백준 서비스 종료
9
952
1
sk 하이닉스 코테 대비
0
387
2
3-G 최댓값 질문
0
54
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
84
2
3-I 코드 질문드립니다.
0
66
2
3-N 질문 있습니다.
0
68
2
학습방법
0
105
2
4-H 질문 있습니다 (코드 리뷰)
0
69
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
186
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
72
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
66
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
55
2