2-1. 데이터 입,출력 구현

자료 구조

자료 구조의 분류

선형 구조 : 배열, 선형 리스트, 스택, 큐, 데크

비선형 구조 : 트리, 그래프

 

연결 리스트

노드 삽입,삭제가 용이

연결을 위한 포인터 필요

포인터 탐색 시간이 길어 접근속도가 느림

중간 연결이 끊어지면 다음 노드 못 찾음

 

스택

LIFO

왔던 길 탐색에서 사용

 

스택 응용 분야

함수 호출 순서 제어

인터럽트 처리

수식 표기

컴파일러를 이용한 언어번역

 

큐

F, R이 존재하고 F에는 pop, R에는 push

FIFO

 

데크

삽입, 삭제가 양방향에서 가능

 

트리

Node, Edge로 구성

디그리 : 각 노드에서 뻗어나온 가지 수

단말 노드(Terminal) : 자식노드

 

트리 운행법

preorder : root -> left -> right

inorder : left -> root -> right

postorder : left -> right -> root

 

정렬

삽입 정렬

평균, 최악 시간 복잡도 -> N의 제곱

하나씩 삽입하면서 자신의 위치를 찾는 정렬

 

선택 정렬

전체 배열에서 최소값 찾아 넣고 그 다음으로 작은 수 계속해서 선택

 

버블 정렬

두 개의 인접한 수 비교를 계속하여 변경이 없을 때까지 비교를 하는 것

 

퀵 정렬

divide and conquer

피봇을 사용, 최악의 경우 n*(n-1)/2 비교

 

힙 정렬

전이진 트리를 이용한 정렬

평균,최악 모두 nlogn복잡도

 

검색

이분탐색

중간지점을 갱신하며 자신의 위치를 탐색해나감

정렬된 배열에서 사용 가능

 

해싱 함수

제산법(divide), 제곱법(mid-square), 폴딩법(folding), 숫자 분석법(digit analysis)

 

체이닝

충돌이 생기면 연결 리스트에 저장하는 방법

 

데이터베이스 개요

정의 기능, 조작 기능, 제어 기능

 

스키마 3계층

외부 스키마, 개념 스키마, 내부 스키마

 

절차형 SQL

테스트 : 오류 검출

디버깅 : 오류 발생한 소스 코드 추적