I. 문자의 빈도 기반 접두부호 생성, 허프만 코드의 개요 가. 허프만 코드의 개념 무손실 압축 위한 엔트로피 부호화로, 데이터 등장 빈도에 따라 다른 길이 부호 사용 알고리즘 개념도 설명 – 접두어 코드 사용 압축 – 접두어 코드 표현 왼쪽 서브 노드: 0 오른쪽 서브 노드: 1 – 루트→리프 경로가 접두어 – 허프만 코드는 무손실 압축, 심볼의 출현 빈도에 따른 가변 길드 코드와 접두사 코드 생성 II. 허프만 코드의
I. 용량 효율화, 압축 기술 이미지, 동영상, 프로그램 등의 저장장치 사용량 절감을 위한 손실/무손실 부호화 기법 II. 압축 기술의 분류 및 유형 가. 압축 기술의 분류 무손실 압축기술 – RLC, 허프만 코드 손실 압축기술 – PCM, DCT 혼합 압축기술 – JPEG, GIF, H.264 – 압축 기술은 무손실, 손실, 혼합 압축기법 존재 나. 압축 기술 세부 설명 구분 설명 사례 무손실 – 압축전 = 복원 데이터 – 정보손실 없음 / 압축률 낮음
I. 비순환 연결 트리, 최소 신장 트리 가. 최소 신장 트리의 개념 연결 그래프의 연결된 간선 일부를 사용하여 모든 정점을 포함하여 가중치의 합이 최소가 되는 트리 나. 최소 신장 트리의 특징 모든 정점 포함 – 그래프에 포함된 모든 정점을 포함 비순환 구성 – 구성된 트리는 순환이 존재하지 않음 최소 비용 – 모든 간선의 가중치 합을 최소화 II. 최소 신장 트리 개념도 – 모든 정점 포함, 비순환, 가중치
I. 모든 경우의 수 도출, 백트래킹 모든 경우의 수를 도출하기 위해 DFS와 Pruning 기법 기반 특정 조건 만족하는 모든 해 탐색 기법 II. 백트래킹 절차도 및 세부 절차 가. 백트래킹 절차도 DFS 기반 유망성 부재 시 Pruning 수행하여 시간 단축 나. 백트래킹 세부 절차 절차 핵심 개념 설명 깊이 우선 탐색 수행 – 상태 공간 트리 – 상태 공간 트리 기반 Pre Order 방식 DFS 수행 Promising 검토 – 유망성 검토 – 해 존재 가능
I. 순간 최적 해 도출, 그리디 알고리즘 개념 특징 특정 순간 최적해를 구하기 위해 최적성과 효율성 개선을 통해 최적의 해를 도출하는 알고리즘 – 최적성의 원리 – 최적 해 보장 불가 – 효율성 개선 II. 그리디 알고리즘 흐름도 및 수행절차 가. 그리디 알고리즘 흐름도 최종 해 도출까지 해 선택, 과정을 반복 & 적합성 확인 나. 그리디 알고리즘 수행절차 # 알고리즘 설명 ① 해 선택 – 부분 해 집합에
I. 최단 거리 계산, 다익스트라 알고리즘 가. 다익스트라 알고리즘의 개념 정점에서부터 다른 모든 정점들까지 증가하는 거리 순 최단 경로를 찾는 알고리즘 나. 다익스트라 알고리즘 절차 단계 절차 세부 설명 ① – 각 노드 거리 설정 – 시작 노드 외 각 노드의 거리에 무한대(∞) 적용 ② – 거리 측정 – 시작노드로부터 각 노드까지 계산 ③ – 최소거리선택 – 시작 노드부터 도착 노드까지 최소비용 간선의 노드 연결 II. 다익스트라 알고리즘
I. 독립변수와 종속변수 간 상관관계, 회귀분석 가. 회귀분석의 개념 관찰된 변수 집합에서 독립변수와 종속변수 간 상관관계를 함수식으로 표현 및 검증하는 분석기법 나. 회귀분석 모형의 가정 구분 구성요소 변수 선형성 – 독립변수와 종속변수 관계는 선형적 오차 정규성 – 오차의 기대값은 ‘0’이며, 정규분포 오차 독립성 – 오차들은 서로 독립적 II. 회귀분석 모델/구성요소 및 분석 유형 가. 회귀분석 모델/구성요소 모델 구성요소 설명 독립변수 입력값, 원인 변수 종속변수 독립변수 의한 효과 회귀계수 변화량, 기울기 최소자승법 각점 거리
I. 순차 비교 정렬 알고리즘, 버블 정렬 개념도 개념 인접한 2개의 값을 비교하여 크기가 순서대로 되어 있지 않으면 값을 서로 교환하여 끝까지 진행하는 알고리즘 II. 버블 정렬에서 flag의 의미 가. flag를 두지 않는 경우 정렬 절차 설명 flag를 두지 않는 경우 처음부터 끝까지 비교/교환 과정 수행 이미 정렬이 되어 있어도 모두 비교 과정 수행 나. flag를 두는 경우 정렬 절차 설명 flag를 두는 경우
균형 트리, B Tree (Balanced Tree) DBMS에서 가장 일반적인 인덱스로, Leaf Block에 정렬된 데이터와 해당 데이터를 가진 행의 위치를 가리키는 레코드 식별자로 구성된 인덱스 II. Tree 인덱스 검색 절차 위 B Tree 인덱스 구조에서 37을 찾는 경우 절차 설명 1단계 – 루트 블록에서 50보다 작으면 왼쪽 포인터로 이동 2단계 – 37은 왼쪽 브랜치 블록의 11과
I. 평균 탐색 속도 보장, 이진 탐색 트리의 개요 이진 탐색 트리의 개념 중복된 노드가 없고, 왼쪽 서브 트리에는 작은 값, 오른쪽 서브 트리에는 큰 값으로 구성되는 이진 트리 이진 탐색 트리의 특징 O(log N)의 평균 탐색 속도 보장 삽입/삭제 시 트리 재구성 필요 II. 이진 탐색 트리의 데이터 삽입 과정 이진 탐색 트리 데이터