알고리즘 & 함수

코딩테스트에서 소수에 관련된 문제가 은근히 많이나온다.for 문을 2번돌려 일일이 약수를 비교해 구면 쉽겠지만, 숫자가 커지면 엄청나게 많은 시간 O(n^2)이 걸려 시간초과로 실패한다.하지만 에라토스테네스의 체 알고리즘을 사용하게 된다면 O(NlogN)만에 소수를 구

순열, 조합 함수를 안쓰고 풀어왔는데 이 함수들을 사용해 순열과 조합을 만들면 매우 간단하고 짧게 작성해도 풀린다는걸 알았다. 사실, 이런 함수들은 엄청 똑똑한 사람들이 만들어 논거라 복잡도면에서도 빠른경우가 많다. 이들이 만들어논 함수들을 필요한 곳에 알맞게 사용하는

이진 검색은 정렬된 배열에서 원하는 원소를 빠르게 찾을 수 있다. --> O(logn)현재 값이 찾으려는 값보다 작으면 오른쪽으로 이동, 크면 왼쪽으로 이동하는 것을 이용한다. Python에서는 이런 기능을 가진 함수를 제공한다.는 정렬된 a에 x를 삽입할 위치를 알려

두 인접한 원소를 검사하여 정렬하는 방법이다.시간복잡도는 O(n^2)으로 느리지만, 구현하기 매우 쉽다.맨 앞 숫자를 기준 숫자로 정하고 뒤에 있는 숫자 들과 비교하여, 뒤에 있는 숫자가 더 작때마다 서로 교환하는 방식이다.Array = 4,3,1,2,5 일때4부터 비