inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

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

3-K와 문제의 단순화

3-K 시간초과 질문

123

Gitae Kim

작성한 질문수 7

0

안녕하세요, 선생님. 새해복 많이 받으시길 바랍니다.

 

3-K(#3179, 백조의 호수) 문제를 강의내용 기반으로 혼자 짜보았는데 2%채점 중에 항상 시간초과가 발생하여 질문 드립니다. 코드는 아래 링크와 같습니다.

http://boj.kr/9a423cb3ee32415a8e66d7d1516881fe

 

기탐색한 큐를 재탐색하지 않도록 q.size가 끝날 때마다 q를 tempQ로 교체하도록 코드는 수정하였으나, 어디선가 불필요한 중복탐색이 발생하는 것으로 예상됩니다.

다만, 저 혼자서는 해당 중복탐색 부분을 발견 못하여 도움을 요청 드립니다...

 

감사합니다.

c++ 코딩-테스트

답변 2

1

큰돌

안녕하세요 기태님 ㅎㅎ

전반적으로 잘 짜셨는데요.

한가지 틀린 부분이 있습니다.
원래 void Qclear(queue<pair<int, int>> q)처럼 값으로 전달하면, 함수 내부에서 비운 큐가 복사본에만 적용되므로 전역 큐에는 영향을 주지 않습니다.
따라서 queue<pair<int, int>> &q_ref와 같이 참조로 받아 swap을 사용하여 실제 큐의 내용을 비우워야 합니다.

 

이렇게 고쳐보시겠어요?

void Qclear(queue<pair<int, int>> &q)
{
    queue<pair<int, int>> empty;
    swap(q, empty);
}

 

감사합니다.

0

Gitae Kim

덕분에 해결됐습니다 감사합니다!

0

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. Gitae Kim님.

백준 3197번 백조의 호수 문제에서 시간 초과가 발생하신 것에 대해 걱정되시겠습니다. 이 문제는 BFS와 큐를 활용하여 얼음과 호수의 상태를 시뮬레이션해야 하는 고난도 문제 중 하나입니다. 일반적으로 시간 초과 문제는 다음과 같은 이유로 발생할 수 있습니다:

  1. 큐 연산의 비효율성: shift() 연산을 많이 사용한 경우 큐의 맨 앞을 제거하는데 비용이 많이 드니, 인덱스를 이용한 접근으로 변경하면 성능이 향상됩니다.
  2. 중복 탐색: 방문한 노드를 다시 탐색하지 않도록 합니다. 이 경우, 방문 배열을 적절히 활용해야 합니다.
  3. 무거운 초기화(Resetting): 탐색이 끝날 때마다 큐나 배열을 계속해서 초기화하는 경우, 필요 없는 초기화 과정이 성능에 영향을 줄 수 있습니다.

다음은 비슷한 문제에 대한 답변 링크입니다. 참고하시면서 코드 최적화에 대한 힌트를 얻으세요:
- 3-K 시간 초과 질문드립니다
- 3-K 해결 방법

위의 답변 링크들은 강사님의 조언과 함께 최적화 방법을 제공하고 있습니다. 특히, “flood fill” 기법 및 swap()과 같은 최적화된 큐 초기화 방법을 고려해보시면 도움이 될 것입니다.

또한 문제를 해결하시다 보면 불필요한 중복 연산을 줄이고 Q와 tempQ 간의 효율성을 극대화하는 방법을 찾으실 수 있을 것입니다. 추가적으로 궁금하신 점이 있거나 코드 개선에 더 도움이 필요하시면 언제든 질문해 주세요.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

코딩테스트 참고문헌 질문

0

38

2

4-P 질문 있습니다.

0

40

3

4-N 문제 수정 요청

0

32

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

89

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

241

1

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

0

93

2

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

0

77

2