3- k 시간복잡도
69
작성한 질문수 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 문제에 대한 기존의 답변 참조하시길 권장드립니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
40
2
2주차 개념#12 트리 순회
0
22
2
백준사이트가 종료된다고 합니다.
0
265
2
백준 서비스 종료
9
835
1
sk 하이닉스 코테 대비
0
365
2
3-G 최댓값 질문
0
50
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
82
2
3-I 코드 질문드립니다.
0
62
2
3-N 질문 있습니다.
0
66
2
학습방법
0
101
2
4-H 질문 있습니다 (코드 리뷰)
0
66
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
167
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
69
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
64
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
50
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
67
2
함수별 시간복잡도
0
72
2
3-h 질문입니다.
0
49
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
53
2
1-I 문제 질문 드립니다.
0
76
2
2-P 질문입니다.
0
56
1
mac에서 시작하기 관련
0
90
2
5-Q 질문
0
63
2
풀이 코드 질문
0
64
2