기술 블로그

# 1. 알고리즘의 분석 * 알고리즘의 자원(resource) 사용량을 분석 * 자원이란 실행시간, 메모리, 저장장치, 통신 등 * 여기서 실행시간의 분석에 대해서 다룸 ## 시간복잡도 * 실행시간은 실행환경에 따라 달라짐 * 하드웨어, 운영체제, 언어, 컴파일러 등 * 실행시간을 측정하는 대신 연산의 실행 횟수를 카운트 * 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 * 데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐 * 최악의 경우 시간복잡도(worst-case analysis) * 평균 시간복잡도(average-case analysis) ## 점근적(Asymptotic) 분석 ### 점근적 표기법을 사용 * 데이터의 개수 n → ∞ 일때 수행시간이 증가하는 growth rat..

순회 : 이진 트리의 모든 노드를 방문하는 일  Inorderpreorderpostorderlevel order Inorder 순회1. 먼저 T_L을 inorder로 순회하고2. r을 순회하고3. T_R을 inorder로 순회 INORDER-TREE-WALK(x)if x != NIL then INORDER-TREE-WALK(left[x]) print key[x] INORDER-TREE-WALK(right[x])x를 루트로 하는 트리를 inorder 순회 = 시간복잡도 O(n) PREORDER-TREE-WALK(x) if x != NIL then print key[x] PRE-ORDER-TREE-WALK(left[x]) PRE-ORDER-TREE-WALK(r..

INSERTmax heap 에 새로운 것을 추가한다고 보면 heap이라는 것은 complete binary tree여야 합니다. 그리고 max-heap-property는 부모는 자식보다 크다라는 조건을 만족해야 합니다.  heap은 complete binary tree를 가져야 하므로 노드를 하나 추가해야하는데빨간 곳 말고는 없습니다. Insert하려는 값이 15라면 저 빨간 곳에 15를 저장할 수밖에 없습니다. 이렇게 하면 트리의 모양은 complete-binary-tree가 되지만 max-heap-property가 깨집니다. (부모가 자식보다 커야되는 것) 노드들간에 데이터를 exchange하고 새로 추가된 노드와 다른 노드에서는 문제가 없어보이며 크기를 비교하면 두 노드를 exchange하면 됩니다..

릴레이션 조작을 위한 연산 표현 방법 절차 언어 - 관계대수비절차 언어 - 튜플 관계 해석, 도메인 관계 해석 관계 대수릴레이션 = Set of tuples릴레이션에 대한 연산의 결과는 릴레이션  연산자의 종류일반 집합 연산자 합집합교집합차집합카디션 프로덕트순수 관계 연산자셀렉트프로젝트조인디비전   조인의 구분세타 조인 : 비교연산자(=,>,동일 조일 : 비교연산자가 = 인 조인자연 조인 : 양쪽 릴레이션에서 중복된 속성에 대해 동일 조인을 수행하고, 조인 결과에서 중복된 속성을 한번만 나타낸 조인, 일반적으로 조인이라고 하면 자연 조인을 의미함  자연조인의 예 1. 두 릴레이션의 공통속성인 학번에 대해 동일조인을 하고 2. 공통속성 '학번'은 한번만 출력 SQL테이블의 생성create table { 컬..

릴레이션릴레이션 스키마 + 인스턴스 릴레이션 스키마속성들의 집합으로 릴레이션의 논리적 구조를 나타냄릴레이션 스킴 또는 릴레이션 내포라고 함시간에 따라 변하지 않음릴레이션 인스턴스일정 시점에서의 튜플들의 집합시간에 따라 변함튜플속성에 해당하는 데이터의 모임 Relation == 테이블Tuple == 행, 레코드속성 == Field, 열 속성단일 속성 : 단일 값복합 속성 : 단순 도메인의 결합으로 이루어진 속성, 일반적으로 하나의 속성값으로 취급속성의 값은 분해할 수 없는 원자의 값입니다. 도메인속성이 취할 수있는 원자 값들의 집합 릴레이션의 특성 튜플의 상이성릴레이션에 포함된 투플은 모두 상이하다.모든 속성의 값이 동일한 투플이 존재해서는 안됨튜플의 무순서성릴레이션 내의 튜플들 간에는 순서가 없음속성의 ..

스키마DB내의 데이터의 구조, 관계, 제약조건에 대한 Specification관점에 따라 스키마는 달라보일 수 있음 (응용 프로그램의 관점, 조직 전체의 관점, 물리적 저장 장치 수준의 관점) 3단계 스키마 구조외부 스키마 : 개개의 사용자 또는 응용프로그램 수준의 스키마 / 서브스키마라고도 함개념 스키마 : 조직 전체 수준의 스키마, 외부 스키마들 통합된 것내부 스키마 : 개념 스키마의 저장 구조를 정의시스템 카탈로그스키마 정보, 사상 정보 등을 저장한 시스템 데이터베이스 데이터베이스 시스템이 사용하는 데이터를 유지하는 시스템용 데이터베이스메타 데이터를 유지데이터 사전이라고도 함일반 사용자도 접근 가능데이터 디렉토리시스템 카탈로그를 접근하기 위한 정보사용자 접근 불가능시스템만 접근 가능데이터 언어데이터..

파일을 이용한 데이터 처리데이터의 중복응용 프로그램이 기대하는 물리적 구조파일을 이용한 데이터 처리 문제점데이터 종속성 : 파일 내부 구조에 응용프로그램이 영향을 받음데이터 중복성 : 동일한 내용의 데이터 중복하여 관리, 데이터 일관성 상실, 보안성 취약, 경제성 취약, 데이터 무결성 취약 DBMS의 필수 기능데이터 정의 기능 : 사용할 데이터의 구조 정의할 수 있어야 함데이터 조작 기능 : 데이터 검색, 삽입, 삭제, 갱신데이터 제어 기능 : 무결성 유지 가능, 권한과 보안 기능, 동시사용 병행 제어 가능DBMS의 장점데이터 중복 최소화데이터 공유사용데이터 무결성 유지데이터 보안 보장조직 내 데이터의 표준화데이터 요구의 조정DBMS의 단점운영비 증대특정 응용 프로그램의 복잡화복잡한 백업과 회복시스템 취..

데이터관찰 측정된 사실 또는 값숫자, 문자, 문자열, 텍스트, 이미지 정보상황에 따라 적절한 결정을 할 수 있게 하는 지식 정보시스템조직체의 활동에 필요한 데이터 수집, 조직, 저장데이터 처리 통해 의사 결정 유용한 정보 생성 수단일괄처리동일한 트랜잭션을 모아 일정 시간에 한번에 처리  정보시스템 구조중앙 집중 시스템 : 데이터와 자원을 한곳에 집중하여 처리분산 시스템 : 다수의 컴퓨터를 네트워크로 연결하여 하나의 시스템처럼 데이터를 처리, 대부분 데이터 처리 시스템이 사용하는 방식데이터베이스한 조직의 여러 응용 프로그램들이 공유하여 사용하는 통합되고 저장된 운영 데이터의 집합정보시스템을 구성하는 핵심적인 요소DBMS데이터베이스를 사용할 수 있게 하는 소프트웨어데이터베이스 조건통합된 데이터 : 최소의 중..

여러 개의 키 저장INSERT, SEARCH, DELETE여러 개의 키를 저장하고 검색, 삽입, 삭제 작업을 효율적으로 수행하기 위해 다양한 자료구조가 사용됩니다. 아래는 배열과 연결 리스트를 사용할 경우, 정렬 여부에 따른 시간 복잡도를 정리한 표입니다:자료구조정렬여부SearchInsertDelete배열 (Array)정렬됨O(log n)O(n)O(n)배열 (Array)정렬되지 않음O(n)O(1), O(n)O(1)연결 리스트 (Linked List)정렬됨O(n)O(n)O(1)연결 리스트 (Linked List)정렬되지 않음O(n)O(1)O(1)🔍 배열이나 연결 리스트를 사용하는 경우, 정렬 여부와 상관없이 INSERT, SEARCH, DELETE 중 적어도 하나는 O(n)의 시간 복잡도를 가집니다. 이..

트리 루트(Root): 트리 구조에서 가장 위에 있는 노드입니다.부모-자식 관계: 한 노드 아래에 연결된 노드를 ‘자식 노드’라고 하며, 연결 위쪽의 노드를 ‘부모 노드’라고 합니다.형제 노드: 동일한 부모를 가진 노드들을 형제(sibling)라고 합니다.리프(Leaf) 노드: 자식 노드가 없는 노드입니다. 트리의 말단에 위치합니다.조상-자손 관계: 부모-자식 관계를 확장한 개념으로, 조상은 부모의 부모까지 포함하며, 자손은 자식의 자식까지 모두 포함합니다. 이진트리이진트리는 모든 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 각각의 자식 노드는 왼쪽 자식(left child) 또는 오른쪽 자식(right child)으로 구분됩니다. 자식이 하나뿐인 경우에도 해당 자식이 왼쪽인지 오른쪽인지를 명확..