※ (링크) 바킹독 유튜브 영상을 통해
학습한 내용을 정리한 것입니다.
본인은 JAVA를 활용해 학습하였습니다.
비상업적 목적이며, 개인 복습을 위해 업로드한 글임을 다시 한 번 더 이야기드립니다.
[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I
안녕하세요, 바킹독입니다. 이번 단원에서는 기초 코드 작성 요령을 익혀보려고 합니다. 목차를 보셨으면 알겠지만 기초 코드 작성 요령이 두 강으로 나눠져있는데 앞으로 코드를 잘 짜기 위해
blog.encrypted.gg
출처: blog.encrypted.gg/922?category=773649
정수자료형
C언어에서 char 자료형은 1 byte = 8 bit 입니다. 즉, 1 byte의 값은 8개의 칸을 이용해 이진법으로 수가 표현된다는 이야기 입니다.
오른쪽부터 2의 0승 왼쪽의 두 번째 칸까지 2의 6승을 나타냅니다.
이때 독특하게 unsigned char에서는 첫 번째 칸에 -2의 7승을 표기합니다.
그 이유는 2's complement 개념을 찾아보면 되십니다! ( 추후 정리해서 추가할 예정 )
unsigned char 최솟값과 최댓값을 한 번 살펴보겠습니다. 00000000 일 때 0일 것이며, 11111111 일 때 255의 값을 가집니다.
즉, 최솟값은 0이며 최댓값은 255라는 뜻입니다.
char 또한 최솟값과 최댓값을 생각해보겠습니다. 최솟값은 10000000 일 때 -128일 것이며, 최댓값은 01111111 127일 것입니다.
[ 표 참고: docs.microsoft.com/en-us/cpp/cpp/data-type-ranges?redirectedfrom=MSDN&view=msvc-160 ]
정수자료형은 char 외에 short(2byte), int(4byte), long(8byte)가 존재합니다. 각각의 범위는 위 표와 같긴하나, 최댓값 계산법은 아래와 같습니다.
- short : 2byte = 16bit --> 215-1 ( = 32767 )
- int : 4byte = 32bit --> 231-1
- long : 8byte = 64bit --> 263-1
여담으로 옛날 메이플의 최대 보유 가능 메소는 int의 최댓값이었습니다.
보통 정수를 표현할 때 int나 long을 표현하는데, 80번째 피보나치 수를 구하는 문제와 같이 int자료형이 표현할 수 있는 범위를 넘어서는 수를 저장할 경우 long 자료형을 사용해야 합니다.
Integer Overflow
단순하게 생각해봅시다. 컴퓨터는 시키는대로 일을 합니다. 즉, 시키는대로 연산을 하지요. 만약 char형에서 덧셈연산을 한다고 생각해보겠습니다.
127 [ 0 1 1 1 1 1 1 1 ] + 1 [ 0 0 0 0 0 0 0 1 ] = -128 [ 1 0 0 0 0 0 0 0 ]
컴퓨터는 명령을 받은대로 이진수 계산을 합니다. 우리가 의도한 것과 달리 나와도, 컴퓨터의 계산은 틀린 것은 아니라는 것이죠. 이를 막는 방법은 굉장히 쉽습니다.
각 자료형에 맞는 값을 갖게 연산을 하면 됩니다.
실수자료형
실수의 원리를 먼저 보겠습니다. float ( 4byte ), double ( 8 byte )입니다. byte의 크기는 각각 int, long과 같은데 어떻게 실수로 표현할 수 있을까요?
이를 이해하기 위해 2진수를 실수로 확장하는 방법을 먼저 보겠습니다.
(1) 2진수의 실수 확장법
2의 음수 거듭제곱을 이용해 실수를 나타낼 수 있습니다. 10진수의 무한소수와 같이 2진수에서도 무한소수가 나타납니다.
(2) 2진수에서의 과학적 표기법
3562.234를 3.561234 X 103로 나타내는 것처럼 2진수에서도 11101.001(2) = 1.1101001(2) X 24로 나타낼 수 있습니다.
그렇다면 실수를 어떻게 표기할 수 있는지 접근해봅시다.
실수를 나타낼 때 칸은 sign, exponent, fraction 필드로 나누어집니다. 위 그림과 같이 말입니다.
- sign : 음수/양수 부호
- exponent : 지수 저장 필드
- fraction : 유효 숫자 저장 필드
- 6.75를 예시로 표현해보겠습니다.
- 마이너스 숫자로 sign 필드에 1을 표기합니다.
- exponent 필드는 2의 2승이 곱해져 지수는 2이나, 127을 더해 129를 exponent 필드에 이진법으로 나타냅니다. 127을 더하는 이유는 음수 지수승도 exponent 필드 안에 넣을 수 있기에 더해주는 것입니다.
- fraction 필드는 맨 앞에 숫자를 뺀 값이 적힙니다. 위 값은 맨 왼쪽부터 2-1 , 2-2인 자리입니다. 그렇기에 필드에 10110000 ... 00 이 적히게 되는 것입니다. 즉, 입력할 숫자를 제일 왼쪽부터 채우는 것입니다.
이는 IEEE-754 포멧입니다.
실수의 성질
- 실수의 저장과 연산 과정에서 반드시 오차가 발생할 수 밖에 없습니다.
유효숫자가 들어가는 fraction 필드가 유한하기에 2진수를 기준으로 무한소수 저장하려하는 경우 어쩔 수 없이 float는 앞 23bit, double은 앞 52bit만 잘라 저장할 수 밖에 없습니다.
fraction filed로 각 자료형이 어디까지 저장되는지 보면, float는 유효숫자 6자리, double은 유효숫자 15자리까지 저장할 수 있습니다. 이는 곧 float은 상대오차 10-6까지 안전하며, double은 10-15까지 안전하다는 이야기입니다.
이 표현을 정확하게 이해하자면 1 - 10-15 ~ 1 + 10-15값을 가지는 것이 보장된다는 뜻입니다. 오차는 막을 수 없으나 오차의 정도는 파악할 수 있습니다.
float와 double의 오차범위 차이가 크기에 실수가 필요하다면 double을 사용하는 것이 좋습니다.
또한 코딩테스트 문제에서 오차는 어느 범위까지 허용한다는 것이 나타나있는데, 이를 참고해 자료형을 선언하면 됩니다. - double에 long 범위의 정수를 함부로 담으면 안됩니다.
오차가 섞인 값이 저장될 수 있습니다. double의 유효숫자는 15자리이나 long은 최대 19자리이기 때문입니다. - 실수를 비교할 경우 등호를 사용하면 안 됩니다.
둘의 차이가 아주 작은 값인 10-12이하면 동일하다고 처리하는 것이 안전합니다. 아래 그림 중 다섯 번째 줄에 [ 1e-12 ]라고 표현된 것이 있습니다. 이 값이 10-12입니다.
'Programming > Algorithm' 카테고리의 다른 글
| [바킹독: 알고리즘] 배열 (0) | 2021.04.08 |
|---|---|
| [바킹독: 알고리즘] 기초 코드 작성 요령 2 (0) | 2021.04.07 |
| [바킹독: 알고리즘] 기초 코드 작성 요령 1 - (1) (0) | 2021.04.05 |
| [바킹독: 알고리즘] 오리엔테이션 (0) | 2021.04.05 |
| 알고리즘: 재귀함수(6) 예제 - 멱집합 ( powerset ) (0) | 2021.03.26 |
