소수 찾기 프로그램 방법 n-1까지 구하기 O(n) n-1 까지 소수를 모두 구하는 다이나믹 프로그래밍으로 알고리즘 짜기 소수 배열을 만들어서 소수 배열만 돌면서 나누어지는지 판단 O(n) 소수 배열을 만드는 데에 O(n) => 메리트 없음 루트 n까지 돌리면서 짝수 제외하기 O(sqrt(n)) 조건 추가 몇 개의 소수( 3, 5 )를 가지고 해당 수의 배수이면 뛰어넘기 3, 5 계산 시 나누어떨어지지 않았으면 해당 수의 배수에도 나누어떨어지지 않음 구현 시 주의 해당 수가 3으로 나누어떨어지는지, 5로 나누어떨어지는지를 계산하려면 모듈러 연산을 사용해야하는데 시간이 오래 걸림 변수 하나씩 지정하고 1씩 더하는 방법으로 구성 3과 5의 공배수가 나오면 먼저 거치는 3의 if문에서 continue 됨으로 ..

Quick sort '알고리즘' 전공 수업시간에 나온 과제인 '1000만개 데이터 정렬 후 해시 값 구하기'를 하면서 정리한 내용이다. 분할 정복 방법을 통해 구현되는 정렬 방법 시간 복잡도 최악 : O(n^2) 평균 : O(nlogn) 설계를 통해서 개선 가능한 부분 구현 과정 pivot을 선택한다. 위쪽 포인터가 낮은 쪽으로 가면서 피벗보다 작은 수를 찾는다. 아래쪽 포인터가 높은 쪽으로 가면서 피벗보다 큰 수를 찾는다. 두 포인터가 가리키는 요소를 교환한다. 2-4를 반복한다. 두 포인터가 교차한다면 현재 피벗과 해당 위치의 값을 교환한다. 피벗과 피벗보다 작은 section, 피벗보다 큰 section으로 나누고 각 section에 대해 1-5를 실행한다. section의 크기가 0 또는 1이면 ..