3- k 시간복잡도
92
작성한 질문수 16
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요! 정해를 보며 복습중인데
while 문을 통틀어 NxM 맵을 탐색하니 시간복잡도는 O(NxM)이 맞나요?
while(true){
if(move_swan()) break;
water_melting();
waterQ = water_tempQ;
swanQ = swan_tempQ;
Qclear(water_tempQ);
Qclear(swan_tempQ);
day++;
}
답변 2
0
안녕하세요, 인프런 AI 인턴입니다.
ililil님, 질문 주셔서 감사합니다. 주신 코드에서는 BFS와 같은 탐색이 이루어지고 있기 때문에 시간 복잡도를 고려하는 것이 중요합니다. 질문 주신 부분에 대해 답변을 드리겠습니다.
코드 설명 및 시간 복잡도 분석
move_swan(): 이 함수는 두 백조가 만날 수 있는지 여부를 확인하는 기능으로, BFS 탐색을 사용하여 각 칸을 탐색합니다. 최악의 경우 NxM 크기의 맵 전체를 한 번씩 확인할 수 있습니다.water_melting(): 물이 얼음을 녹이며 확장하는 기능으로, 마찬가지로 BFS와 유사한 방식으로 인접한 모서리를 순차적으로 녹여갑니다. 이 부분에서도 NxM 크기의 모든 칸을 검사할 수 있습니다.
통합된 시간 복잡도
각 반복마다 두 개의 BFS 탐색 수행이 있으며, 이들이 각각 O(NxM)의 시간 복잡도를 가질 수 있습니다. 따라서 while 루프가 반복되는 횟수만큼 실제 시간 복잡도가 증가할 수 있습니다. 실제로 while 루프는 물이 완전히 얼음에서 녹을 때까지 계속해서 반복되며, 그동안의 복잡도는 다음과 같은 요소에 따라 달라질 수 있습니다:
얼음 녹는 속도: 완전히 녹을 때까지의 걸린 날 수를 기준으로 평가.
백조 이동 가능 경로 확장 속도: 백조가 서로 만나기까지의 경로 확장 시간.
이 모듈들이 개별적으로 실행될 때 O(NxM)의 시간을 필요로 하므로, 전체 운영 시간 복잡도는 문제의 특성 및 데이터에 따라 상당히 많아질 수 있습니다.
위 내용이 도움이 되셨길 바랍니다. 질문하신 내용과 관련해 보다 구체적인 도움이 필요하시다면, 백준 3-K 문제에 대한 기존의 답변 참조하시길 권장드립니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
코딩테스트 참고문헌 질문
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





