Algorithm/개념정리 (9) 썸네일형 리스트형 에라토스테네스의 체(소수 찾기) C++ / 과정 / 시간복잡도 :: DANIDANI 알고리즘 개념 고대 그리스 수학자 에라토스테네스가 만들어 낸 방법으로, 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 빠르고 정확하게 소수를 찾는 알고리즘 n까지의 소수를 알고 싶을 때, n^1/2 이하의 수의 배수만 지우면 된다. 과정 배열 생성 후 초기화한다. (1은 소수가 아니니 지우고 시작) 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. 2를 제외한 2의 배수를 지운다. 3을 제외한 3이 배수를 지운다. 반복 남아있는 수가 소수! 코드 vector arr(n+1); arr[1] = true; for(int i = 2; i 이분 탐색(Binary Seaerch) C++ / 장단점 / 시간복잡도 :: DANIDANI 알고리즘 개념 정렬이 되어있는 배열에서 데이터를 찾을 때, 원하는 탐색 범위를 두 부분으로 나눠 찾아간다. 중간 값과 비교해서 탐색 범위를 절반씩 줄여간다. 과정 정렬을 한다. left 값과 right 값의 중간값인 mid를 정한다. 찾고자 한 값과 mid와 비교후, mid보다 작으면 right = mid -1, mid보다 크면 left = mid + 1로 설정한다. left > right가 될 때까지 반복한다. 코드 int binarysearch(int key, int left, int right){ long long mid = (left + right) / 2; if(left 힙정렬(Heap Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI 알고리즘 개념 완전 이진트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬 방 불안정 정렬에 속한다. 최대 힙의 루트가 원소의 최댓값이라는 점을 활용하여 정렬을 수행하는 방법이다. 루트를 제외한 힙이 재정렬되는 과정이 반복되면서 정렬이 이루어진다. 과정 최대 힙을 구성한다. 루트를 힙의 마지막 원소와 교환한다. 마지막 원소를 제외하고 나머지 원소에 대해서 반복한다. 정렬된 원소를 제외하고 최대 힙에 원소가 1개 남으면 정렬을 종료한다. 최대 힙 재구성 과정 노드 i(=n/2)와 그 자식 노드(2i, 2i+1) 중 큰 값과 비교하여 자식 노드가 더 크면 노드 i와 교환한다. i의 값을 1씩 감소시킨 후 i>0 인 경우에 대해서 위 과정을 반복한다. 코드 트리에서 index 0은 사용하지 않으니 arr [.. 병합정렬(Merge Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI 알고리즘 개념 분할 정복 방법을 통해 구현한다. 안정 정렬에 속한다. 레코드 리스트를 반으로 나누어 2개의 서브 리스트로 분할하고, 각 서브 리스트에 이 과정을 재귀적으로 적용하여 더 이상 분할이 불가능할 때까지 반복한다. 분할이 완료된 이후에는 이웃하는 두 개의 파티션을 서로 병합하여 정렬을 완료한다. 과정 분할: 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복: 부분 배열을 정렬한다. 결합: 정렬된 부분 배열들을 하나의 배열에 병합한다. 2개의 리스트의 값들을 처음부터 하나씩 비교하여 더 작은 값을 새로운 리스트로 옮긴다. 둘 중 하나가 끝날 때까지 반복한다. 둘 중 하나가 먼저 끝나면 나머지 리스트의 값들을 전부 넣는다. 새로운 리스트를 원래 리스트로 옮긴다. 코드 int arr[100000.. 퀵정렬(Quick Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI 알고리즘 개념 분할 정복 방법을 통해 큰 문제를 작은 문제 단위로 쪼개면서 해결된다. 불안정 정렬에 속한다. 보통 프로그래밍 언어에서 sort의 내부적으로 사용된다. 임의의 기준 수 pivot을 선택하여 정렬 대상 수들을 pivot 값보다 작은 그룹과 큰 그룹으로 분할한다. pivot은 작은 그룹과 큰 그룹 사이로 이동시킨다. 분할된 각 그룹에 대해서 재귀적으로 또다시 pivot을 정하고 동일한 과정을 반복한다. 원소가 1개가 되어 더 이상 분할이 불가능할 때까지 반복한다. 알고리즘 배열 내부에서의 분할 과정 i는 왼쪽 끝, j는 오른 쪽 끝 위치로 둔다. pivot을 첫번째 항목으로 선택하고(때에 따라 랜덤이나 중간 값을 선택할 수도 있음) pivot보다 큰 값을 만날 때까지 i값을 1씩 증가시키고, .. 삽입정렬(Insertion Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI 알고리즘 개념 이미 정렬되어 있는 리스트에서 새로운 수를 추가하는 과정이다. 비교 대상인 수가 자신의 자리를 찾을 때까지 왼쪽으로 이동한다. 과정 첫 번째에 위치한 수(인덱스 0번 위치의 수)는 이미 정렬이 완료되었다고 가정한다. 정렬 리스트의 오른쪽에 있는 정렬되지 않은 수(인덱스 1번 위치의 수)는 자신의 앞에 있는 수와 크기를 비교하여 앞쪽 수가 더 크면 자리를 바꾼다. 인덱스 2번 위치의 수도 왼쪽으로 전진 하면서 자기 자리를 찾는다. 더 이상 정렬된 대상 원소가 없을 때까지 반복한다. 코드 int j, temp; for (int i = 1; i = 0 && temp < arr[j]; j-.. 거품정렬(Bubble Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI 알고리즘 개념 항목의 키 값을 풍선에 비유한 것으로 값이 클수록 더 높이 올라가도록 한다. 가장 큰 값의 키가 오른쪽 끝으로 이동하고, 그다음 큰 값이 그 옆으로 이동하는 과정을 반복한다. 과정 첫번째 수와 두 번째 수를 비교해서 큰 수가 오른쪽에 위치하게 교체한다. 두 번째 수와 세 번째 수를 비교해서 큰 수가 오른쪽에 위치하게 교체한다. 가장 오른쪽에 도달할 때까지 1,2번을 반복한다 오른쪽 끝에 최대값이 도달하였음으로 이 수를 제외하고 나머지 수에 대해서 수가 1개가 남을 때까지 1~3번 과정을 반복한다. 코드 int temp; for(int i = 0; i arr[j+1]){ temp = ar.. 선택정렬(Selection Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI 알고리즘 개념 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 첫 번째 자리에는 첫 번째~마지막 원소 중 가장 작은 원소를, 두 번째 자리에는 두 번째~마지막 원소 중 가장 작은 원소를... 과정 주어진 배열에서 최솟값을 찾는다. 그 최솟값과 맨 앞에 위치한 값을 교체한다.(swap) 맨 앞에 위치한 값을 제외한 나머지 배열에 대해서 같은 방법으로 교체한다. 코드 for (int i = 0; i < n; i++){ int minIdx = i; for (int j = i + 1; j < n; j++){ if (arr[j] < arr[minIdx]) minIdx = j; } int temp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx].. 이전 1 2 다음