코드 깎는 개발자

[알고리즘] 계수 정렬 (Counting Sort) 특정한 범위 내에 속해있다면 O(NlogN)의 기존 정렬들보다 빠른 O(N)의 시간복잡도를 가질수 있는 알고리즘으로 단순하게 크기를 기준으로 세는 알고리즘이다. 크기를 기준으로 갯수를 세보자!!! 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하자! 5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5 위의 숫자들은 5이하의 숫자라는 범위안에 들어가 있다. 5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5 1 2 3 4 5 0 0 0 0 0 5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5 1 2 3 4 5 0 0 0 0 1 5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5 1 2 3 4 5 1 0 0 ..

[알고리즘] 힙 정렬 (Heap Sort) 힙정렬은 힙 트리 구조를 이용하는 정렬 방법이다. 따라서 힙(Heap)에 대해서 알아봐야하는데 또 힙을 알기 위해서는 선행적으로 이진 트리(Binary Tree)를 알고 있는 것이 좋다. 이진 트리란 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드에 담은 뒤에 노드를 두 개씩 이어 붙이는 구조를 말한다. 즉, 이진트리는 모든 노드의 자식이 2개 이하인 노드를 가지고 있는 구조이다. 그리고 데이터 루트 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근 차근 들어가는 구조의 이진트리를 완전 이진 트리 고한다. 힙(Heap)은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 힙에는 최대힙과 최소힙이 존재하..

[게임수학] 함수 함수 (Function) 두 집합에서 첫 번째 집합의 모든 원소가 빠짐없이 두 번째 집합의 어떤 원소에 대응하는 관계를 의미한다. 함수로 인정받는 조건 ▹ 첫 번째 집합의 모든 원소에 대한 대응 관계가 존재해야 한다. ▹ 첫 번째 집합의 원소는 두 번째 집합의 한 원소에만 대응되어야 한다. 정의역과 공역 정의역 : 함수에서 왼쪽에 위치한 첫 번째 집합이다. 공역 : 오른쪽에 위치한 두 번째 집합이다. 치역 : 공역의 모든 원소가 정의역에 대응할 필요는 없다. 그렇기 때문에 정의역에 대응되는 공역의 원소들을 치역이라고 한다. 정의역 공역 X → y = f(x) → Y 입력(input) 출력(output) 함수의 종류 전사함수 (Surjection) 공역의 모든 요소가 정의역에 대응되는 함..

[알고리즘] 병합 정렬 (Merge Sort) 병합정렬은 퀵정렬과 마찬가지로 분할 정복 방법의 알고리즘이며 퀵정렬과 마찬가지로 O(N * logN)의 시간 복잡도를 가진다. 먼저 반을 나누고 나중에 합쳐서 정렬을 하자!!!! 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하자! 7, 10, 5, 8, 1, 6, 3, 4, 2, 9 7 10 5 8 1 | 6 3 4 2 9 //반 나누기 7 10 5 | 8 1 | 6 3 4 | 2 9 //나눈 것을 또 나누기 5 7 10 | 1 8 | 3 4 6 | 2 9 //나눠진 것들 정렬 1 5 7 8 10 | 2 3 4 6 9 //합쳐서 정렬 1 2 3 4 5 6 7 8 9 10 소스코드 구현 (C++) #include //정렬될 배열을 미리 전역변수로 선언해두..

[게임수학] 수 수와 집합 분류 정의 기호 예 자연수 물건을 세거나 순서를 지정하기 위해 사용하는 수의 집합 ℕ 1,2,3 정수 자연수와 자연수의 음수 0을 포함하는 수의 집합 ℤ -1,0,1 유리수 분모가 0이 아닌 두 정수의 비율 혹은 분수로 나타낼 수 있는 수의 집합 ℚ ½, ⅞ 무리수 두 정수 비 혹은 분수로 나타낼 수 없는 수의 집합 𝕀 sqrt2, π 실수 유리수와 무리수를 포함하는 수의 집합 ℝ 위에 다 복소수 실수와 제곱하면 -1이 되는 허수 단위 i를 조합해 a + bi(a,b는 실수)형태로 표현하는 수의 집합 ℂ ​ 사원수 실수와 제곱하면 -1이 되는 세 허수 단위 i,j,k를 조합해 a+bi+cj_dk(a,b,c,d는 실수)형탸로 표현하는 수의 집합 ℍ 연산과 수의 구조 수 집합의 고..

[알고리즘] 퀵 정렬 (Quick Sort) 특정한 값(Pivot)을 기준으로 큰 숫자와 작은 숫자를 나누자!!! 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하자! 1, 10, 5, 8, 7, 6, 3, 4, 2, 9 1 10 5 8 7 6 3 4 2 9 // 맨 앞을 기준으로 왼쪽에서부터 큰값을 찾고 오른쪽에서부터 작은 값을 찾는다. // 큰값 10, 작은값 없음 다음으로 피벗을 넘김 1 10 5 8 7 6 3 4 2 9 //기준 값 10, 큰값 없음 작은값 5 1 5 10 8 7 6 3 4 2 9 ⁞ 1 5 8 7 6 3 4 2 9 10 //10보다 큰 값이 없기 때문에 계속 작은 값과 위치가 바뀌어서 맨뒤로감 1 5 8 7 6 3 4 2 9 10 //기준 값 5, 큰값 8 작은값 2 1 5 ..

[C++] 해시 (Hash) 해시 (Hash) 해시는 해시함수의 결과물이며, 저장소에서 값과 매칭되어 저장되며 해시테이블의 구성 요소이다. ▹ 이진 트리가 아닌 해시 테이블로 구성되어있다. ▹ 올바른 키와 올바른 해시 테이블 크기가 만족된다면 요소를 검색하는 속도는 O(N)에서 O(1)로 단축할 수 있다. 해시 테이블 (Hash Table) 해시 테이블은 연관 컨테이너 구조를 이용하여 키(key)에 값(Value)을 저장하는 자료 구조이다. 키, 해시 함수(Hash Function), 해시, 값, 저장소(Bucket)로 이루어져 있으며 키는 해시함수를 통해 해시로 변경되며 해시는 값과 매칭되어 저장소에 저장이 된다. 해시 함수 (Hash Function) 키(key)를 해시(Hash)로 바꿔주는 역할을 ..

[알고리즘] 삽입 정렬 (Insertion Sort) 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하자! 1, 10, 5, 8, 7, 6, 3, 4, 2, 9 정렬 시 각 숫자를 필요할 때만 적절한 위치로 바꾸자!!! 1 10 5 8 7 6 3 4 2 9 _ 1 _ 10 5 8 7 6 3 4 2 9 1 _ 10 _ 5 8 7 6 3 4 2 9 1 5 _ 10 _ 8 7 6 3 4 2 9 1 5 8 10 7 6 3 4 2 9 ⁞ 1 2 3 4 5 6 7 8 9 소스코드 구현 (C++) int main() { int temp; int arr[10] = { 1, 10, 5, 8, 7, 6, 3, 4, 2, 9 }; //삽입 정렬 for (int i = 0; i < 9; i++) { int j = i; w..

[알고리즘] 버블 정렬 (Bubble Sort) 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하자! 1, 10, 5, 8, 7, 6, 3, 4, 2, 9 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내자!!! //1 1 10 5 8 7 6 3 4 2 9 1 5 10 8 7 6 3 4 2 9 1 5 8 10 7 6 3 4 2 9 1 5 8 7 10 6 3 4 2 9 ⁞ 1 5 8 7 6 3 4 2 9 10 //2 1 5 8 7 6 3 4 2 9 10 1 5 7 8 6 3 4 2 9 10 1 5 7 6 8 3 4 2 9 10 ⁞ 1 5 7 6 3 4 2 8 9 10 ⁞ 1 2 3 4 5 6 7 8 9 10 소스코드 구현 (C++) int main() { int temp; int arr[10] = {..

[알고리즘] 선택 정렬 (Selection Sort) 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하자! 1, 10, 5, 8, 7, 6, 3, 4, 2, 9 가장 작은것을 앞으로 보내자!!! 1 10 5 8 7 6 3 4 2 9 1 2 5 8 7 6 3 4 10 9 1 2 3 8 7 6 5 4 10 9 1 2 3 4 7 6 5 8 10 9 ⁞ 1 2 3 4 5 6 7 8 10 9 1 2 3 4 5 6 7 8 9 10 소스코드 구현 (C++) #include using namespace std; int main() { int min, index, temp; int arr[10] = { 1, 10, 5, 8, 7, 6, 3, 4, 2, 9 }; //선택정렬 for (int i = 0; i < 10; ..