소개 인접한 두 수를 비교하면서 대소 비교에 적합한 수를 뒤로 보내는 알고리즘이다. 평균적으로 시간 복잡도는 $O(n^2)$를 나타낸다. 설명현재 인덱스의 바로 다음번 인덱스와의 크기를 비교해서 조건에 맞다면 위치를 옮겨준다. 여기서 조건은 대소 비교의 조건이다.비교하면서 한 번 순회를 끝내면 순회 시 제일 마지막 인덱스는 자연스럽게 제일 크거나 작은 값이다. 다음번 순회에서는 최종 인덱스 까지 순회할 필요 없다. 즉 순회마다 -1만큼 순회할 크기가 줄어 드는 것이다. 시간 복잡도 계산 전체 원소의 수가 $n$ 개라면 $(n-1) + (n-2) + ... + 2 + 1 = (n - 1) * n / 2 = (n^2-n)/2$의 값을 연산을 하게 될 것이다. 그래서 평균적인 시간 복잡도는 $O(n^2)$ 이..
소개특정 인덱스 값의 값을 남은 값들을 순회 하면서 가장 크거나 작은 값으로 바꾸는 정렬 알고리즘으로, 메모리가 제한적인 경우 사용하면 성능 상 이점이 있는 알고리즘이다.설명1. 주어진 데이터의 첫번째 인덱스의 값을 첫번째를 제외한 나머지 데이터 중에서 가장 크거나 작은 값으로 변경한다2. 순회를 끝내면 인덱스 값을 증가 시켜서 나머지 데이터 중에서 가장 크거나 작은 값으로 변경한다. 3. 위의 동작을 순회가 끝날때 까지 반복한다.시간복잡도선택정렬 또한 순회를 할 때마다 -1씩 순회 할 데이터 양이 줄어 든다. 그러면 다음과 같은 수식을 얻을 수 있게 된다. $(n-1) + (n-2) + ... + 2 + 1 = (n - 1) * n / 2 = (n^2-n)/2$ 그래서 선택정렬의 시간 복잡도는 $O(n..
소개최적해를 구하는 데에 사용되는 근사적인 방법, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해나가는 방식이다. 여기서 중요한 것은 선택들을 계속 수집해서 최종적인 해답을 얻었을 경우 이 해답이 최적의 답이라는 보장은 없다. 탐욕 알고리즘은 동적알고리즘이 지나치게 많은 일을 한다는 것에 착안되어 만들어진 알고리즘이다.적용이 잘되는 경우1. Greedy Choice Property (탐욕 선택 조건)앞의 선택이 이후 선택에 영향을 주지 않는 경우를 적용이 잘된다. 즉, 각 사건들이 서로 독립적일 때 잘 맞는다. 2. Optimal Substructure (최적 부분 구조 조건)문제에 대한 최적해가 부분 문제에 대해서도 최적인 경우대표적인 해결 문제1. 배낭 문제2. 동..
해쉬 알고리즘이란?? 키 값을 입력 받아서 해쉬 테이블의 주소가 되는 값을 반환해주는 함수 해쉬 테이블이란?? Key & Value로 이루어진 테이블 형태의 자료 구조로서 Key값이 Hash 함수를 거쳐 나온 Hash 값을 테이블 상의 저장 주소로 사용한다. 해쉬 값은 최대한 중복이 발생 되지 않는게 좋겠지만 현실적으로 불가능 하며 이것을 해결 하기 위한 방법들이 몇 가지 있다. 해쉬 테이블 충돌 해결 방법 위 그림처럼 키 값은 다르지만 Hash함수를 거치고 난 뒤의 해쉬 값이 동일하여 충돌이 발생하는 경우에는 데이터를 안전하게 저장하고 관리하기 위해서 충돌에 대한 해결을 해주어햐 하며 2가지가 존재한다. Separate Chaining 방식 이 방법은 Linked List를 사용하는 방법이다. 인덱스에..