고정소수점(fixed point): 왼쪽밖에 소수점이 고정된 것으로 표현.
-다만 이는 표현할 수 있는 자리수가 적음. 0.0000000101에서 맨 뒤 101과 소수점 앞은 빠지게 됨
부동(floating point): 소수점의 위치가 변함. 부호, 지수부, 가수부로 나뉨.
-0.001234=-0.1234*10(지수-2)
| 1(부호,음수이기에 1) | -2((지수부, 소수점 오른쪽으로 2칸) | 1234(가수부) |
-10진수는 2진수표현으로 정확히 나타내지 못함. 이때문에 java에서는 bigdecimal class를 이용해 10진수 소수 계산을 할 수 있음.
10진수 실수(존과 팩 형식)
10진수의 2진수 실수표현은 근복적으로 부정확한 표현법. 이를 위해 10진수 실수법으로 표현.
- 존 형식(zoned decimal): 10진수 한 자리 표현을 위해 한 바이트 사용. 한 바이트에서 존영역과 수치영역으로 나뉜다. 존영역은 상위 니블로, 1111로 표시되며, 수치영역은 10진수 한 자리 값에 대해 2진수로 표시된다. 표현하고자 하는 10진수의 자릿수만큼 존형식으로 연결해 사용한다. 마지막 자리 존 영역에는 부호를 표시하여 양수인지 음수인지 표시한다.
- 팩 ㅡ 형식(packed decimal): 10진수 한 자리 표현을 위해 존영역 없이 하나의 니블을 전부 씀. 최하위 니블에 부호를 표시함으로써 양수와 음수를 구별한다. 존 형식과 마찬가지로 양수는 1100, 음수는 1101로 표현한다.
자료구조
추상자료형
-추상화(abstraction): 필수적인 중요한 것만 골라 단순화시킨 것.(반대어로, 구체화)
-컴퓨터는 크고 복잡한 문제를 단순화(추상화)시켜서 더 쉽게 문제해결방안을 찾음.
-자료형(data type): 처리할 데이터의 집합과 데이터에 대한 연산자의 집합
즉, 추상자료형(abstract data type)은 데이터와 연산자의 특성을 추상화해서 정의한 자료형. 구현은 하지 않은 것.
알고리즘
문제에 대해 해결절차를 체계적으로 기술한 것.
- 자연어를 이용해 서술하면 서술자에 따라 일관성이나 명확성을 유지하기 어렵다. 즉, 누구가 쉽게 이해하고 쓸 수 없다.
- 프로그래밍언어를 이용하면, 그 언어를 모를 땐 이해가 어려움, 다른 언어로 옮기는 것도 일.
- 순서로(flow chart)는 알고리즘에 대한 흐름파악이 용이하지만 복잡하게 표현은 어려움.
- 가상코드(pseudo-code)는 프로그래밍 언어와 유사하게 알고리즘을 표현함.
성능분석
알고리즘 분석
- 하나의 문제에 대해 여러 알고리즘을 쓸 수 있기에 가장 효율적이고 최적인 알고리즘을 결정하기 위해 알고리즘 분석 필요.
- 정확성(가장 중요), 명확성, 수행량, 메모리 사용량, 최적성이 기준
알고리즘 성능 분석 방법
-공간복잡도(space complexity): 알고리즘을 프로그램으로 실행하여 완료하는 데 필요한 총 저장공간, 고정 공간+가변 공간, 프로그램 자체를 저장하는 공간(고정 공간), 데이터와 변수들이 저장되는 공간(가변 공간)
-시간 복잡도(time complexity): 알고리즘 프로그램을 실행하여 완료하는 데에 걸리는 시간, 명령문의 실행 빈도수를 계산하여 실행시간을 구함.
- 서로 다른 알고리즘의 실행시간을 비교할 때 입력 자료수가 적을 땐 비교에 의미가 없다. 입력자료수가 커질 때 실행시간이 증가하는 것을 보고 비교해야 한다.
상술한 시간 복잡도는 o-notation(빅-오 표기법)으로 표현한다. 빅오는 다음과 같은 순서를 가진다.
- 실행시간 함수를 구함. T(n)
- 함수 결과에 영향을 주는 차수가 높은 n에 대한 항을 선택.
- o 기호 괄호 안에 표시한다
o표기법은 점근적 표기법 중 하나이다. 점근적 표기법은 입력크기(n)가 증가함에 따라 어느 정도로 실행시간이 증가하는 가를 표현한다. 이밖에도 big omega 표기법, theta 표기법, 기타 표기법이 있다.
주로 o 표기법을 사용하지만 보다 정확한 표현을 위해 theta 표기법을 사용하기도 한다.
o(n)은 무조건적으로 o(log n)보다 차수가 높다.
