코딩관계론

SET이 빠른 이유 set은 데이터를 해싱하여 내부적으로 해시 테이블에 저장합니다. 해시 테이블의 경우 해시 함수를 주어진 입력에 대해서 해시 키 값이 존재하기에 인덱싱이 매우 빠르다. 또한 파이썬의 set은 내부적으로 c언어로 구현되어 있어 파이썬 인터프리터보다 빠르다. 또한 set은 중복을 허용하지 않기에 데이터의 크기가 작아져서 해시테이블의 충돌을 방지하며 연산 속도를 향상시킨다 따라서 set은 대용량 데이터를 다룰 때에도 빠른 속도를 보장할 수 있다. 하지만, set은 해시 함수의 충돌(Collision) 문제를 고려해야 한다. 충돌은 서로 다른 두 개의 키가 동일한 해시값을 가질 때 발생합니다. 충돌이 발생하면 set은 해시 테이블에서 다른 곳에 해당 요소를 저장합니다. Set에서 사용되는 해시..

아이디어 도출 방법 주어진 문제는 search배열(n)에서 특정 숫자(m)를 찾는 문제였다. 하지만 배열의 길이가 크고, 찾고자 하는 특정 숫자가 많아지면 이중반복문으로는 해결하기 어렵다. 따라서 이중 반복문을 제거하고, 주어진 배열에서 더 빠르게 탐색할 수 있는 알고리즘이 필요한데 이것이 이분 탐색이다. 이분 탐색은 기존의 O(n)의 시간 복잡도를 O(logn)으로 줄여준다. 이런 방법을 사용한다면 기존의 O(n*n)의 시간 복잡도에서 O(nlogn) + O(mlogn)으로 개선할 수 있다. 또한 이분 탐색을 하기 전 필수적으로 수행되어야 할 것은 '특정 배열'(주어진 숫자를 찾고자 하는 배열)이 정렬되어 있어야 한다. 최종 결과 n = int(input()) search = list(map(int, ..