37. 트리(Tree) (⭐️⭐️⭐️⭐️)
1) 개요 및 용어정리
정점(노드)과 선분(가지)을 이용해 사이클을 이루지 않도록 구성한 그래프의 특수한 형태
- 하나의 기억공간: 노드, 노드-노드 연결선: 링크
- 최초레벨: Level1, ... 마지막레벨: Level n 일때 Depth = n
✓ 노드: 점과 가지 모두 합친것
✓ 근 노드 (Root Node): 트리의 맨 위에 있는 노드
✓ 디그리 (Degree, 차수): 노드에서 뻗어나온 가지의 수
✓ 단말 노드(Terminal Node) / 잎 노드 (Leaf Node): 디그리가 0인 노드
✓ 자식 노드(Son Node): 한 노드에 연결된 다음 레벨의 노드들
✓ 부모 노드(Parent Node): " 이전레벨의 노드
✓ 형제 노드(Brother Node): 동일 부모 갖는 노드들
✓ 트리의 디그리: 노드 디그리들 중 가장 높은 수
2) 트리 운행법 ⭐️⭐️⭐️
노드 찾아가는 방법을 운행법이라고 함
이진트리 운행법
- Preorder 운행: 루트->왼->오 (루트가 앞에 - pre)
- Inorder 운행: 왼->루트->오 (루트가 안에 - in)
- Postorder 운행: 왼->오->루트 (루트가 뒤에 - post)
3) 수식 표기법 ⭐️⭐️⭐️
-> 복잡해서 나중에 시간남을때 이해
대충 Infix: A+B 라는 수식에서, Prefix: +AB, Postfix: AB+
38. 정렬(Sort) (⭐️⭐️⭐️⭐️)
1) 삽입 정렬 (Insert Sort)
이미 순서화된 파일 에 새로운 레코드 순서에 맞게 삽입시켜 정렬
- n번째의 값을 n-1번째의 값들과 계속해서 비교하여 정렬
- 평균과 최악 모두 수행시간 복잡도는 O(n^2)
2) 쉘 정렬 (Shell Sort)
- 매개변수(h) 간격으로 있는 숫자들의 리스트를 따로 만들고 그 리스트별로 삽입정렬 실시 (보통 n=h^3)
- h 간격을 점점 좁혀가며 리스트별로 삽입정렬 실시
- 삽입정렬보다 수행시간이 빠름
- 평균 수행시간 복잡도는 O(n^1.5), 최악의 경우 O(n^2)로 선택정렬과 동일
3) 선택 정렬 (Selection Sort)
- n개의 레코드 중 최소값을 찾아 첫번째 위치에, 다시 찾아 두번째 위치에.
- 평균과 최악 모두 O(n^2)
4) 버블 정렬 (Bubble Sort)
- 인접한 두개의 레코드 계속 비교
- 평균과 최악 모두 O(n^2)
5) 퀵 정렬 (Quick Sort)
- 분할: 하나의 피벗(Pivot, 중심값)을 정하고
- 정복: 피벗보다 작은값/큰값 두 부분집합으로 나눔
- 더이상 나눠지지 않을 때까지 분할과 정복 반복
- 정렬방식중 가장 빠름
- 평균 O(nlog2n), 최악 O(n^2)
6) 힙 정렬 (Heap Sort)
- 전이진 트리 (Complete Binary Tree) 이용한 정렬방식
- 리스트를 전이진 트리로 만들고, 노드의 역순으로 자식노드와 부모노드 비교
- 평균과 최악 모두 O(nlog2n)
7) 2-way 합병 정렬
정렬된 두개의 파일을 하나의 파일로
- 두개의 키를 한쌍으로 하여 정렬
- 묶음을 또 한쌍으로 하여 정렬 ... 반복
- 평균과 최악 모두 O(nlog2n)
8) 기수 정렬 (Radix Sort) = Bucket Sort
자리수(digits)별로 정렬
- 일의 자리수 비교 -> 10의 자리수 비교 -> ...
- 복잡도는 평균과 최악 모두 O(dn)
39. 데이터베이스 개요 (⭐️⭐️⭐️)
1) 개요
- 논리 데이터 저장소: 데이터 및 데이터간 연관성, 제약조건 식별하여 논리적 구조로 조직화한 것
- 물리 데이터 저장소: 논리데이터저장소에 저장된 데이터와 구조들을 하드웨어 저장장치에 저장한 것
2) 데이터베이스
-> 공동, 통합, 저장, 운영
3) DBMS
데이터의 종속성과 중복성 문제 해결
세 가지 기능
- 정의: 데이터 형/구조 정의, 이용방식, 제약조건 명시
- 조작: 데이터의 검색, 갱신, 삽입, 삭제
- 제어: 무결성, 권한검사, 병행제어
👉🏻 데이터의 독립성
- 논리적 독립성: 응용프로그램과 데이터베이스 독립; 데이터 논리구조 변경돼도 응용프로그램 변동 X
- 물리적 독립성: 응용프로그램과 물리적 장치(보조기억장치 등) 독립; 시스템 성능향상 위해 새로운 디스크 도입해도 응용프로그램 영향 X
5) 스키마
데이터 구조 제약조건에 관한 전반적 명세 기술한 메타데이터의 집합
- 외부 스키마: 사용자나 프로그래머가 개인의 입장에서 DB 논리적 구조 정의
- 개념 스키마: 개체간 관계와 제약조건, DB 접근권한, 보안 및 무결성규칙에 관한 명세 정의
- 내부 스키마: 물리적 저장장치, 레코드 형식 정의, 내부레코드 물리적순서 등
41. 절차형 SQL
- 테스트: 오류를 찾음
- 디버깅: 오류를 수정
참고도서 📚
2022 시나공 정보처리기사 필기
정체되지 않는 성장