🤍 전 강의 25% 할인 중 🤍

2024년 상반기를 돌아보고 하반기에도 함께 성장해요!
인프런이 준비한 25% 할인 받으러 가기 >>

  • 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

시간복잡도 질문

23.07.15 21:12 작성 조회수 292

0

안녕하세요. 좋은 강의 감사합니다.

island 카운트 세는 문제에서 시간복잡도를 n^2으로 풀면 안된다고 하셨는데 풀이법에서는 이중포문으로 푸셨더라구요.

이중포문은 시간복잡도를 n^2으로 알고 있는데 이렇게 푸신 이유가 있으신가요?

답변 2

·

답변을 작성해보세요.

0

Ambition님의 프로필

Ambition

2023.11.26

네 제가 보기에는 모든 데이터를 완전탐색으로 순회했기 때문에 사실상 O(n)입니다. 반면에 1차원 배열의 최대 데이터도 n이라고 가정했을 때, 여기에서 이중 for문을 사용하면, 한번 쭉 탐색했던 것을 중복해서 탐색하기 때문에 n(데이터의 수) * n(탐색 횟수) = n^2이라 O(n^2)의 시간복잡도가 걸린겁니다.

-1

인프런 AI 인턴님의 프로필

인프런 AI 인턴

2023.07.17

안녕하세요, 인프런 AI 인턴이에요. 이중 포문은 시간복잡도가 O(n^2)입니다. 이렇게 푸신 이유는 island 카운트 세는 문제에서, 각각의 섬을 찾기 위해 모든 요소를 탐색해야 하는데, 모든 요소를 한 번씩 돌아야 하기 때문입니다. 따라서 이중 포문을 사용하여 해결하셨을 겁니다. 하지만 보다 효율적인 알고리즘을 사용하여 시간복잡도를 개선할 수도 있습니다. 이 부분은 성능 개선에 대한 고려사항이 될 수 있는데, 강의에서는 그런 부분을 다루지 않았을 수도 있으니 참고해주세요.

다른 질문이 있으시면 언제든지 물어보세요. 좋은 공부 되시길 바라요~요.

채널톡 아이콘