인프런 커뮤니티 질문&답변
작성한 질문수
3-8 해쉬-2 코드 질문
해결된 질문
작성
·
63
·
수정됨
0
3-8 해쉬 -2
안녕하세요!
설명해주신 코드에서 해쉬를 이용하면 결국 시간 복잡도는 결국 O(N)인데,
아래와 같이 해도 되나요? 아래도 시간복잡도가 O(N)이라고 생각하는게 맞는지 궁금합니다!
all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]
set(all_students)-set(present_students)답변 2
0
안녕하세요 sonapple3님! 좋은 질문 감사합니다
네, 맞습니다! 말씀해주신 set 연산을 사용한 방식도 시간 복잡도가 O(N)입니다.
set()생성all_students를 set으로 변환: O(N)
present_students를 set으로 변환: O(N)
차집합 연산
-두 set 간의 차집합 연산은 O(len(smaller_set))의 시간 복잡도를 가집니다.
이 경우에도 O(N)
따라서 전체 시간 복잡도는 O(N) + O(N) + O(N) = O(N) 입니다!
새로운 방식으로 문제를 풀어보시는 법 매우 좋습니다!!
0
안녕하세요, 인프런 AI 인턴입니다. snoapple3님.
질문 주신 해시 구조를 활용한 코드에 대해서 설명드리겠습니다.
주어진 코드에서 set(all_students) - set(present_students) 구문은 모든 학생의 집합에서 출석한 학생의 집합을 뺀 차집합을 구하는 방식입니다. 이 방식은 Python의 set 자료구조의 특성을 활용한 것으로, 시간이 되게 효율적입니다.
시간 복잡도 분석
Set 변환:
list를set으로 변환하는 작업은 각 리스트의 길이에 비례하여 O(N)입니다. 여기서 N은 리스트의 길이입니다.차집합 연산: 두 집합 간의 차집합 연산은 평균적으로 O(N)에 가까운 시간 복잡도를 보입니다. 이는
set에서 해시 테이블을 기반으로 하고 있기 때문입니다.
따라서 전체 코드는 생성 및 연산 측면에서 O(N + M)로, 여기서 N은 all_students의 길이, M은 present_students의 길이가 됩니다. 결론적으로, 주어진 방식도 시간복잡도가 O(N)으로 효율적입니다.
이 방식을 사용하면 두 집합 간의 차집합을 단순하고 명확하게 구할 수 있어 Python에서 자주 사용하는 테크닉 중 하나입니다.
관련 참고 링크
해시 테이블과 set을 사용한 방법에 대한 더 많은 관점을 원하실 경우, 아래의 관련 질문을 참고하시면 도움이 될 것입니다:
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
감사합니다!