3-8 해쉬-2 코드 질문
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을 사용한 방법에 대한 더 많은 관점을 원하실 경우, 아래의 관련 질문을 참고하시면 도움이 될 것입니다:
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
수강평 이벤트
0
34
2
코딩테스트 처음인데 이런 공부방법이어도 괜찮을까요
0
70
2
3-3 정렬-2 선택정렬 로직
0
43
2
링크드 리스트 끝에서 k번째 값 출력하기
0
46
2
LinkedList 과제 Fast, slow 포인터
0
50
2
투포인터 시간복잡도
0
53
2
수강평 작성 후 자료
0
53
2
수업교재 링크 오류
2
114
2
프로그래머스에서 제출 후 채점시 틀림ㅠ
0
133
2
1-10 알고리즘 더 풀어보기(2) 질문 있습니다
0
76
2
문제 풀이 방식 관련 질문입니다!
0
88
2
1-5 알고리즘과 친해지기 (2) - 최빈값찾기 질문 있습니다
0
94
2
수업자료 pdf 받고싶습니다
0
108
2
강의 자료 오류 수정
0
75
1
2-10 더하거나 빼거나 관련 질문입니다
0
63
2
3-8 해쉬 -2
0
49
2
Linked List Element Delete Explanation Problem
0
69
2
강의3-4 스택 탑 문제
0
74
2
코드스니펫 입출력 케이스에 오류가 있는것 같아요
0
100
3
링크드 리스트 원소 찾기 구현 방식 질문드립니다.
0
76
2
1874 - 스택 문항
0
81
2
DP Java 예제 자료형 오버플로우 문제
0
100
2
4-9 4주차 숙제중 농심라면 문제
0
111
2
DFS 에서 스택을 사용하는 이유
1
187
3