inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-A

3-A 완탐 시간초과 질문

해결된 질문

122

김찬민

작성한 질문수 9

0

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

http://boj.kr/32d8365f752d4ea7a3ec61b9ad94f90c

안녕하세요 큰돌님. 저의 풀이는 combi 함수가 아닌 원복을 하며 완전탐색으로 풀이를 진행했습니다.

하지만 시간초과가 발생하여 어느 부분에서 시간 초과가 발생하는지, 그리고 시간초과가 발생하지 않을 라면 저의 코드에서 어떤 부분을 수정해야 하는지 알 수 있을까요??

항상 좋은 강의 해주셔서 감사드립니다 :)

c++ 코딩-테스트

답변 1

0

큰돌

안녕하세요 찬민님 ㅎㅎ

	for (auto it : chi)
	{
		if (visited[it.first][it.second]) continue;
		visited[it.first][it.second] = 1;
		select_chi.push_back(it);
		go();
		visited[it.first][it.second] = 0;
		select_chi.pop_back();
	}

이 코드를 보시면 이 재귀함수의 시간복잡도를 알 수 있는데요.

chi의 최대 크기는 13.

함수당 기저사례인 m까지 진행하므로 최대 13^m정도의 시간복잡도임을 알 수 있습니다.

여기서 m의 최대는 마찬가지로 13입니다. 즉, 13^13의 큰 시간복잡도를 가지기 때문에

시간초과가 발생하는 것 같습니다.

 

감사합니다.

코딩테스트 참고문헌 질문

0

37

2

4-P 질문 있습니다.

0

36

3

4-N 문제 수정 요청

0

30

1

2-T 질문

0

39

1

코딩 살구클럽 가입 문의

0

74

2

코딩살구클럽 가입문의

0

80

2

3-K private case 질문

0

76

2

안녕하세요. 코딩살구클럽 문의드립니다!

0

88

2

7:41 듣다가 질문합니다

0

93

2

코드 리뷰 요청드립니다!

0

87

2

코딩살구클럽 계정 문의

0

84

2

SK하이닉스 대비 강의수강

0

226

3

코딩살구클럽 등록부탁드립니다.

0

82

2

7-F 재귀로 풀시 런타임애러

0

82

1

1-N 문제 질문입니다. (+ 채점오류)

0

86

2

코딩살구클럽 가입 확인 부탁드립니다.

0

88

2

직장인 코테 합격 공부방법 문의

0

136

2

코딩살구클럽 가입 방법

0

104

2

6-H 체점 관련 질문

0

83

1

채점서버 연결 관련 질문입니다

0

111

2

삼성 s직군

0

95

1

삼성 코테 없어짐

0

240

1

코딩살구클럽 가입부탁드립니다

0

93

2

코딩살구클럽 가입 요청 확인부탁드립니다

0

77

2