Develop Develop

조건1. 노드는 레드 혹은 블랙이다2. 루트노드는 블랙이다.3. 모든 리프 노드는 블랙이다.4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (레드 노드가 연달아 나올 수 없고, 블랙 노드만이 레드 노드의 부모가 될 수 있다.)5. 어떤 노드로부터 시작되어 리프노드에 도달하는 모든 경로에는 리프노드를 제외하면 모두 같은 개수의 블랙 노드가 있다/ 레드-블랙 트리는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다(worst-case guarantees). 이는 실시간 처리와 같은 실행시간이 중요한 경우에 유용하게 쓰일 뿐만 아니라, 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모가 있다. 예를 들면, 각종 기하학 계산에 쓰이는 많은 자료 구조들이 레드-..

이진검색을 보자..(이거 logn)미리 정렬된 자료를 대상으로 검색 범위를 반으로 감소시키는 과정을 반복하여 검색 키를 찾는다.여기서 이진은 검색을 반씩 줄이기 때문이다..이분검색이라는건...시작위치 + 마지막 위치 / 2 로 소수점은 버리고 정수만을 취한다. 재귀에 의한 구현int binarySearchRecursive(int value[], int start, int end, int key){int ret = 0;int middle = 0; if (start

알고리즘의 대부분은 시간복잡도가 공간복잡도보다 더 중요하다.sum(n){ i

정렬 알고리즘이 가져야할 최소한의 복잡도는 O(nlogn)만약 C++ new에서 동적배열의 크기를 -1로 하면 당연히 안만들어지지만...만약에 0으로하면 항복이 하나도 없는 배열을 가리키는유효한 포인터가 생성되어 나두면 메모리릭이 발생한다.배열 메모리 계층들 중 가장 낮은 곳에 위치한 것은 레지스터다. 컴퓨터 전체에서 가장 빠른 메모리이다. x86 기준 8개밖에 없다.그런데 다행히도 대부분의 프로세서들은 레지스터와 거의 비슷하게 빠르되 용량이 좀 더 큰 메모리 영역이 있다. 그것이 바로 캐시다.(보통 L1 캐시라고 한다)먼저 레지스터에서 자료를 찾고 없으면 L1캐시에서 찾고 또 없으면 다른 메모리 수준에서 찾는다..근데 이러면 시간이 오래 걸린다.그런데 메모리의 특징이 하나 더 있다. 메모리는 한 수준에..

힙 정렬은 힙 자료구조를 이용하여 자료를 정렬한다.우선은 힙 자료구조를 본다면 완전 이진트리이면서 동시에 최대 트리 호은 최소 트리를 말하는 것으로,최대 힙은 루트노드의 키가 트리 전체 중 항상 최대값을 지니고 최소 힙은 루트 노드가 전체 중 항상 최솟값을 가지는 특성이 있다. 힙은 우선 순위 대기열에 사용하기에 매우 효율적이다. 또한 힙이라는 자료구조 자체에서도 정렬 기능이 있다..왼쪽 자식은 루트보다 작고 오른쪽은 크다(틀렸다. 하나의 노드는 그 노드의 모든 자손(왼, 오른쪽)보다 큰 키 값을 가진다. 루트에는 항상 가장 큰 키 값을 갖는 노드가 위치한다)(최소힙은 최대를 최소로만 바꿔서 읽으면 됨..)(그럼 위의 조건은 어떤 자료구조인가? 바로 이진 검색 트리의 조건이다.) 힙의 삽입 삭제 알고리즘..

기수정렬기수는 숫자의 자릿수를 말한다. 예를 들어 10진수 숫자 42는 1의 자릿수가 2이고 10의 자릿수는 4인 정수이다. 기수 정렬은 키 값의 자릿수에 따라 자료를 분배하는 방식을 통해 정렬하는 알고리즘이다.즉, 앞서의 정렬 알고리즘들이 각 자료의 키 값을 비교하여 이동을 수행하는 방식인 것과 비교하여기수 정렬은 이러한 비교연산이 필요없으며 버킷이라 불리는 자료보관 큐에 자료를 분배하고 다시 이를 꺼내는 연산을 통해 정렬이 이루어진다. 예를들어 키 값이 10진수의 2자리 숫자라고 한다면, 먼저 1의 자리에 대해서 분배하고 각 버킷 벼롤 자료들을 꺼낸 다음 다시 10의 자리에 대해서분배하고 버킷에서 자료들을 꺼내면 정렬이 완료된다. 입력데이터는 42, 60, 75, 81, 10, 23, 12, 18 이..

병합정렬은 1. 같은 개수의 원소를 가지는 부분집합으로 기존 자료를 분할하고2. 분할된 각 부분 집합을 병합하면서 정렬 작업을 완성하는 분할정복 기법에 의한 정렬방식이다.즉, 여러개의 정렬된 부분집합을 결합하여 정렬된 집합을 만드는 알고리즘 이다.2개의 정렬된 자료집합을 병합하면 2 - way 병합 / n개의 정렬된 자료 집합을 결합 n - way 병합 데이터는 80, 50, 70, 10, 60, 20, 40, 30의 8개의 정수 배열이다. 오름차순 병합 정렬은 먼저 기존 자료를 동일한 개수의 원소를 가지는 부분 집합으로 분할해야한다.여기서는 2 - way 병합을 사용해야하니까 초기 전체 자료를 2개의 부분 집합으로 나눈다.또한 나뉜 2개의 부분 집합에 대해서도 각각 2개의 부분 집합으로 나눈다. 이러한..

삽입 정렬은 기존에 정렬된 부분 집합에 정렬할 자료의 위치를 찾아 삽입하는 정렬방식이다.데이터 그룹은 다음과 같다80, 50, 70, 10, 60, 20, 40, 30의 8개의 정수로 구성되어있다.삽입 정렬에 의해 오름차순으로 정렬이 된다면... 두번째 자료부터 전체 자료개수만큼 루프를 돌면서 삽입위치를 찾는데..먼저 첫번째 80의 위치에두번째 자료인 50의 삽입할 위치를 찾는것....일단 80보다는 작으니까..80앞에 50이 위치하게 된다.그러면 50, 80, 70, 10, 60, 20, 40, 30 이렇게 되고..다름 70을 50, 80의 그룹에 삽입될 위치를 찾고..50, 70, 80이 된다..반복하게 되는것...50, 70, 80, 10, 60, 20, 40, 30 상태에서...다음인 10을 50..