뭘 배웠지?

기수정렬(Radix Sort) k이하의 자릿수를 가진 자연수인 경우 각 자릿수별로 정렬 숫자를 부분적으로 비교 기수의 기란? 기수에서 기는 기(Radix), 특정 진수를 나타낸다 10진수의 기: 0 ~ 9 2진수의 기: 0, 1 예시 가장 낮은 자릿수(1의 자리)를 비교 그 다음 낮은 수(10의 자리) 비교 그 다은 자릿수(100의 자리) 비교 하면서 작은수부터 적어주면 된다. 어디서 쓰면 좋을까? 많은 숫자로 되어있는 상용 데이터 베이스에서 유용 주민등록번호, 계좌번호, 전화번호, 인터넷 주소 등 파이썬으로 구현하면 이렇다(그저 따라해서 이해 못했지만) def radix_sort(A): RADIX = 10 maxLengh = False tmp, placement = -1, 1 while not maxL..

계수정렬(Counting Sort) 각 항목이 몇개씩 있는지 세는 작업을 하면서 선형시간에 정렬 한계 정수나 정수로 표현할 수 있는것만 정렬가능 방법 최대값까지 배열 생성 입력원소의 발생 횟수를 세어 저장 예시 입력 배열: [0] [5] [4] [4] [1] [3] [2] [5] [1] [4] [6] 입력 원소의 최대값까지 카운트(Count) 배열 생성 위의 예에서는 0~6까지 정수, 7개를 가진 카운트 배열이 생성된다. 1. 카운트 배열 7개 각 원소의 발생 횟수를 세어 저장 0 원소의 개수 한번, 1이 두번, 2가 한번 등 6까지 그럼 카운트 배열은 이렇다 [1] [2] [1] [1] [3] [2] [1] 2. 카운트 배열의 값을 누적하여 저장 다시 카운트 배열의 값을 누적해서 만들어준다 [1] [2..

트리 정렬(Tree Sort) 이진탐색트리를 이용해 정렬한다 이진트리? 트리의 모든 노드의 차수가 2이하 탐색 요건 모든 노드의 키는 서로 다른 유일한 키 왼쪽 서브트리에 있는 노드들의 키는 루트 노드의 키보다 작다 오른쪽 서브트리에 있는 노드들의 키는 루트 노드의 키보다 크다 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색트리

힙 정렬(Heap Sort) 항상 가장 큰 원소가 루트 노드가 되고 삭제 연산을 수행하면서 항상 루트 노드의 원소를 삭제하며 반환 힙(Heap) 이란? 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기위해, 완전 이진트리(Complete Binary Tree)를 기본으로 한 자료구조 힙 종류 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙

퀵 정렬 기준 값을 중심으로 왼쪽과 오른쪽 부분집합으로 정렬 기준 값을 피봇(Pivot)이라고 함 첫번째 가운데 혹은 마지막에 위치한 원소 선택 분할 기준값(피봇) 중심으로 2개의 부분집합으로 분할 정복 기준값 기준 작은 원소 왼쪽, 큰 원소 오른쪽으로 부분집합의 크기가 1일 될때까지 반복 규칙 Left는 피봇보다 작으면 통과, 크면 정지 Right는 피봇보다 크면 통과, 작으면 정지 예시 첫 번째 원소 52를 피봇이라고 하자 52(피봇), 33, 87, 47, 99, 4, 65, 26, 77 33을 Left로 표시, 77은 Right로 표시 52와 33(Left) 비교해보니 33이 작다 그러니 Left를 87로 52와 77(Right) 비교해보니 77이 크다 그러니 Right을 26으로 이동 현재 상황..

데이터의 세계 3중 세계관 실세계 -> 개념의 세계 -> 컴퓨터의 세계 개체 -> 개체 타입 -> 레코드 사실 -> 추상적 표현 ->(데이터 모델링)논리적 구조 개체(Entity)의 개념 유용한 정보를 저장 관리하기 위한 것 사람, 장소, 물건, 사건 개념 저장 물질일 필요 없다 지속적인 관심을 가지고 있어야 하는 대상 동질성을 지닌 개체 또는 행위의 집합 정의의 조건 우리가 관리하고자 하는 것인가 집합의 개념인지 개체들 간의 동질성이 있는지 다른 개체와 확연히 구분되는 독립성을 가졌는가 개체가 행위를 한 집합인지 개체의 성질 업무에 필요하고 관리하고자 하는 정보 식별자에 의해 식별이 가능한가 영속적으로 존재하는 개체 업무 프로세스에서 그 개체를 반드시 이용 속성을 포함해야 된다 하나 이상의 다른 개체와..

무결성 제약조건 관계형 모델 구조: 릴레이션(2차원 테이블) 연산: 관계대수(relational Algebra) 제약조건: 무결성 제약조건(Integrity Constraint) 모든 관계형 데이터 모델에 적용되는 일반적이고 기본적인 제약 이 제약을 기초로 세부적이고 특수한 제약을 생성 가능 스키마에 정의된 무결성 제약조건을 위반하지 않아야된다 개체 무결성 참조 무결성 도메인 무결성 개체 무결성(Entity Integrity) 의미: 서로 다른 두 튜플은 같을 수 없다 정의: 기본키 값은 널(Null)을 가질 수 없다. 튜플을 개체(Entity)를 나타낸다 개체는 본질적으로 구분 가능 구별할 수 있는 식별자가 필요하다 기본키는 이들을 유일하게 구별할 수 있는 기능을 제공 기본키: 유일성, 최소성을 만족하..

릴레이션: 튜플의 집합 키(Key) 란? 몇 개의 속성만 이용하면 모든 튜플을 식별할 수 있다. 튜플을 유일하게 식별할 수 있는 속성 집합 키의 종류 후보키, 기본키, 대체키: 유일성, 최소성 만족하는 속성 집합 수퍼키: 유일성만 만족하는 속성 집합 후보키(Candidate Key) 튜플의 유일성을 유지시키는 최소 속성 집합 유일성: 서로 다른 두 튜플의 속성 집합 K의 값이 같지 않는다 최소성: K는 서로 다른 두 튜플을 식별하기위한 최소한 속성의 집합 수퍼키(Super Key) 일반적으로 후보키는 수퍼키의 부분 집합 기본키(Primary Key) 하나의 릴레이션에 후보키가 여러 개 있을 수 있다 여러 개의 후보키 중 DBA가 지정한 1개의 키 대체키(Alternative Key) 후보키에 기본키를 제..

셸 정렬 주어진 자료에 매개 변수 h 길이를 갖는 부분집합으로 나누고, 삽입정렬 수행 매개변수 h값을 줄이며 반복, 매개 변수 h 값이 1이 되면 정렬 완성 부분집합 만드는 방법 부분집합 기준 간격을 h에 저장 한단계씩 h 값을 감소시키고 셸 정렬 호줄 h1가 1이 될 때까지 반복 예시 44, 88, 62, 38, 19, 49, 27, 73가 있다 매개변수를 원소 개수의 반으로 하는 경우 전체 원소 8개니까 매개 변수 h는 4 시작! 4간격씩 떨어져 있는 녀석들을 모아서 부분집합을 만든다 그 말은 44에서 오른쪽으로 4번 떨어진 19를 하나의 부분집합, 88에서 4번 떨어진 49를 부분집합으로 ... 나머지도 똑같이 부분집합 만들때 중요한 포인트 부분집합 할 때 삽입 정렬을 한다 이렇게 만들어진다 19,..

병합정렬 여러개의 정렬된 자료를 병합해서 하나로 만든다 부분집합으로 분할하고, 각 부분집합에서 정렬을 완료하고 정렬된 부분집합을 결합 2-way 병합: 2개의 정렬된 자료를 1개로 병합 n-way 병합: n개의 정렬된 자료를 1개로 병합 2-way만 한번 알아보자 같은 크기의 부분집합 2개로 분할 부분집한 원소들 정렬 1개로 병합 예시 분할 단계 44, 88, 62, 38, 19, 49, 27, 73이 있다 이렇게 4개씩 2개로 나눠보자 44, 88, 62, 38 그리고 19, 49, 27, 73 왼쪽의 44, 88, 62, 38을 또 나눠보자 44, 88 그리고 62, 38 오른쪽 19, 49, 27, 73도 나눠보자 19, 49 그리고 27, 73 이제 각자 1개씩 나눈다 44 / 88 / 62 / ..