CS/알고리즘

알고리즘 - 버블 정렬(Bubble Sort)

버블정렬 이웃하는 숫자를 비교하여 작은 수를 앞 쪽으로 이동시키는 과정을 반복하여 정렬하는 알고리즘이다. 버블정렬의 시간복잡도는 O(N^2)이다. 한 번의 Loop에 요소의 갯수만큼 비교를 하며 총 Loop는 요소의 개수번 돈다. 정렬할 수: 15, 2, 6, 27, 24, 9, 8, 13,10, 1, 5 실행 결과 0 회전 결과: 2 6 15 24 9 8 13 10 1 5 1 회전 결과: 2 6 15 9 8 13 10 1 5 24 2 회전 결과: 2 6 9 8 13 10 1 5 15 24 3 회전 결과: 2 6 8 9 10 1 5 13 15 24 4 회전 결과: 2 6 8 9 1 5 10 13 15 24 5 회전 결과: 2 6 8 1 5 9 10 13 15 24 6 회전 결과: 2 6 1 5 8 9 1..

알고리즘 - 알고리즘

알고리즘이란 이름은 페르시아 수학자 알라콰즈미(al-Khwarizmi 서기 780 ~ 850년)로부터 유래되었다. 알고리즘은 문제를 해결하는 단계적 절차 또는 방법이다. 입력이 주어지고, 수행 결과인 해(또는 답)을 출력한다. 알고리즘의 특성 - 정확성 알고리즘은 주어진 입력에 대해 올바른 해를 주어야 한다. - 수행성 알고리즘의 각 단계는 컴퓨터에서 수행이 가능하여야 한다. - 유한성 알고리즘은 유한 시간 내에 종료되어야 한다. - 효율성 효율적일수록 그 가치가 높아진다. 알고리즘은 항상 시간적, 공간효율성을 갖도록 고안되어야한다. 알고리즘의 분류 - 분할 정복 - 그리디 - 동적 계획 - 근사 - 백트래킹 - 분기 한정 그 외에도 확률 개념이 사용되는 랜덤, 병렬, 분산, 양자 알고리즘 등이 있다.

알고리즘 - 동전 거스름돈

물건을 사고 거스름돈을 동전으로 받아야 한다면? 예를 들어 거스름돈이 730원인 경우 가장 적은 수의 동전을 받기 위해서 1. 730원에서 500원짜리 몇 개? 1개 -> 730 - 500 = 230 2. 230원에서 100원 짜리 몇 개? 2개 -> 230 - 200 = 30 3. 30원에서 50원짜리 몇 개? 0개 4. 30원에서 10원짜리 몇 개? 3개 500원짜리 1개 200원짜리 2개 10원짜리 3개 쓸데없이 재귀함수 소스코드) void change(int money){ if (money >= 500) { int fivehun = money / 500; printf("500원 짜리: %d개\n", fivehun); change(money % 500); } else if(money >= 100){..

알고리즘 - 이진탐색(Binary Search)

이진탐색(Binary Search), K찾기 - 오름차순으로 데이터를 정렬한다. - 중간 숫자와 K비교한 후 같으면 탐색 성공 - K가 작으면 앞부분 반에서 같은 방법으로 K를 찾고 - K가 크면 뒷부분 반에서 같은 방법으로 K를 찾는다. 값이 보다 크다면 mid + 1 ~ high / 2 값이 보다 작다면 low ~ mid - 1 / 2 void binarysearch(int a[], int high, int target){ int low = 0, mid; //첫 최솟값은 0 while (low

알고리즘 - 순차탐색(Sequential Search)

최대 숫자 찾기 가장 큰 숫자가 적힌 카드를 찾는 한 가지 방법은 카드의 숫자를 하나씩 비교하면서 본 숫자들 중에서 가장 큰 숫자를 기억해가며 진행하는 방법일 것이다. n개의 숫자가 있을경우 n - 1의 비교가 이루어진다. 1 3 2 4 1 5 6 9 6 5 10개의 숫자가 있을 경우 1번째 요소를 가장 큰 요소로 두고 10번까지 9번의 비교가 이루어진다. 소스코드) void SequentialSearch(int a[], int n){ int tmp = 0; for (int i = 1; i < n; i++) { if (a[tmp] < a[i]) { tmp = i; } } printf("\n%d\n", a[tmp]); }

알고리즘 - 병합 정렬(Mearge Sort)

병합정렬 - '분할 정복' 방법을 채택한 알고리즘 - O(N * logN)의 시간 복잡도를 가진다. - 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합친다. 기본 아이디어는 일단 정확히 반으로 나누고 나중에 정렬한다 계속 반으로 나누어서 한 개씩 남을 때 까지 나눈다. 예를 들어 a = { 8, 3, 4, 5, 1, 3, 2, 5} 이란 배열이 있을 경우 반을 나눌 경우 8 3 4 5 1 3 2 5 또 나눌 경우 8 3 4 5 1 3 2 5 또 반을 나눌 경우 8 3 4 5 1 3 2 5 한 개씩 남게된다. 다 나눴을 때 합치게 된다. 합치게 되는 과정은 보통 2의 배수만큼 합친다. 첫 번째 병합 첫 번째 합칠 때는 두 개씩 합치는데 합치면서 정렬을 하게 된다 8 3 4 5 ..

알고리즘 - 힙 정렬(Heap Sort)

우선 힙 트리를 알고 가야한다. 출처: 동빈나 힙 트리 힙 트리는 트리 자료구조에서 자식노드보다 부모노드가 큰 상태를 뜻한다. 최대힙과 최소힙의 다른점은 점점 내려갈수록 값이 커지는가, 작아지는가 차이지만 모두 균일성을 유지해야 한다. 완전 이진트리 완전 이진트리는 왼쪽부터 채워나간다. 완전 이진트리는 배열에 넣게되어도 유휴 공간이 발생하지 않는다. 아래와 같은 이진트리가 있을경우 A번 노드부터 L번 까지의 노드에 번호를 매긴다면 아래와 같다. 이를 보고 추리한다. n노드의 부모 -> n / 2 (나머지는 버림) n노드의 왼쪽 자식노드 -> n * 2 n노드의 오른쪽 자식노드 -> n * 2 + 1 heapify heapify는 하나의 노드에 대해 수행한다. 자식노드와 자신을 비교해 자식노드에 더 큰 수..

알고리즘 - 쉘 정렬(Shell's Sort)

쉘 정렬은 삽입 정렬의 개선판. 삽입 정렬을 이해하고 있어야 한다. 삽입정렬 https://clamp-coding.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%ACInsertionSort 알고리즘 - 삽입 정렬(InsertionSort) 삽입 정렬) 두 번째 원소로 시작해서 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자로를 삽입하여 정렬하는 알고리즘. 해당 배열을 오름차순으로 clamp-coding.tistory.com 쉘 정렬) 쉘 정렬은 갭의 크기가 줄어들면서 정렬되는 알고리즘이다. 예를 들어 n개의 값을 가지고 있는 배열이 있다면, 처음 g..

알고리즘 - 삽입 정렬(InsertionSort)

삽입 정렬) 두 번째 원소로 시작해서 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자로를 삽입하여 정렬하는 알고리즘. 해당 배열을 오름차순으로 정렬한다면. 두 번쨰 요소를 시작으로 key이전의 요소들과 비교를 한다. 7보단 5가 더 작으므로 7을 밀고 5를 삽입한다. 2번째 요소를 정렬했기 때문에 3번쨰 요소인 1을 이전 요소들과 비교 시작. 7보다 1이 작기때문에 7을 이동, 1을 삽입. 2회전의 결과이다. 이 이후로도 같은 작업을 이어간다. 2번째 요소부터 시작하지만 1번째 요소까지 계속 비교하며 N to 1 까지 비교해나간다. 삽입 정렬의 특징 - 배열 내에서 교환하는 방식으로, 공간복잡도는 O(1)이다. 추가적인 부분은 원소를 교환할때 사용하는 임시요소정..