고정 소수점

1의 보수

+0 -0 존재

상위 1비트는 무조건 부호

2의 보수

0 하나만 존재

상위 1비트는 무조건 부호

1100 → -4

부동 소수점

부호부 | 지수부 | 기수부

저장 용량 단위

KB 2^10byte

KB MB GB TB

PB EB ZB YB

자료형 변환

Widening : 정수형 → 실수형 , 정보손실 없다.

Narrowing : 실수형 → 정수형, 정보손실

Truncation : 자료 임의 부분 잘라낸다.

Underflow : 없는 자료 가져올 때 발생

자료구조

선형\비선형

선형 구조

스택

사용 예)

함수 호출, 인터럽트 수행, 깊이 우선 탐색

큐

사용 예)

프로세스 스케줄, 스풀, 입출력 버퍼

데크

배열

자료 삽입 시 : (n+1)/2

자료 삭제 시 : (n-1)/2

선형구조

연결 리스트(Linked List)

희소 행렬(0이 많은 행렬)을 표현하는 데 효율적

임의의 위치 삽입하는 비용 크다.

연결 리스트가 n 크기의 배열보다 메모리 사용량이 더 크다.

비선형 구조

트리, 그래프

트리

이진 트리 순회

Preorder

근 좌 우

Inorder

좌 근 우

Postorder

좌 우 근

노드의 차수 : 자식 노드의 개수

트리의 차수 : 노드의 차수가 가장 큰 값

신장트리의 간선의 개수 n -1

신장트리 : 모든 정점 연결하고 사이클이 없는 그래프

그래프

최대 간선 수

무방향 : n(n-1) /2

방향성 : n(n-1)

시간 복잡도

이진 탐색 트리 logn

배열 n

정렬된 이진 탐색 logn

순차탐색 n

해싱함수

제산법: 전체 자료수 나눈 나머지 값

폴딩법: XOR

선형 검색

자료가 적을 떄 유리

정렬 되어 있지 않아도 된다.

검색 속도가 매우 느리다.

블록 검색

순차 검색을 이용

보간 검색 보다 느리다.

블록 개수 : 루트 n

블록 끼리 정렬, 블록 내부 정렬 x

정렬