이번 강의는 어려워도 꼭 필요한 기초 내용인 시간 복잡도와 자료형 내용이다.
목차
0x00 시간, 공간 복잡도
0x01 정수 자료형
0x02 실수 자료형
0x00 시간, 공간 복잡도
[중요]시간복잡도
입력의 크기와 문제 해결에 걸리는 시간의 상관관계다.
예를 들어, 반복문을 n번 실행하는 경우, n에 비례한다고 퉁쳐서 표현한다.
다른 예시를 보자.
사람들은 '정렬'되어 있음을 유의하자.
만약 50명 사람이 정렬된 이름순으로 서있다면, 가운데 사람의 이름을 물어봐서 25명을 남기고,
또 반을 쪼개서 12명, 6명, 3명.. 이런 식이면 '가나다'인 사람을 찾을 수 있다.
만약 16명이 있다면,
반으로 나눠서 8명, 반으로 나눠서 4명, 또 반으로 나눠서 2명, 반으로 나눠서 마지막 1명을 찾을 수 있다.
16명이 있을 때, 4번의 연산으로 타겟을 찾을 수 있다. 이 것을 lg N에 비례한다고 한다.
빅오표기법
주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법이다.
O(1) : 상수시간
O(lgN): 로그시간
O(N): 선형시간
O(lg N)부터 O(N²) : 다항시간
O(2^N): 지수시간
O(N!) : 팩토리얼
공간 복잡도
512MB 일때, 대강 1.2억개의 int를 사용할수 있음을 기억하자. (int 1개가 4byte 임을 이용해 계산할 수 있다. )
0x01 정수 자료형
char 자료형은 1byte == 8bit 이다. 즉, 8개의 bit로 숫자를 표현한다.
0000 0001 은 10진수로 1이다.
0000 0010 은 10진수로 2를 표현한다.
그런데, 맨 왼쪽은 -2의 7승이다. 맨 왼쪽 비트는 '부호비트'의 역할을 한다.
왜그럴까?
음수를 표현하기 위함이다.
참고: 2의 보수(2's complement)
보수의 의미? 보충해주는 수를 의미한다.
1에 대한 2의 보수는 1이다. 1에 1을 보충해줘야 2가 된다.
1에 대한 10의 보수는 9이다. 1에 9를 보충해주면 10이 된다는 의미다.
비트는 0과 1밖에 없는 2진수임을 유의하자. 1에 대한 2의 보수는 1이다.
어떤 정수를 표현하는 N개 비트가 있다.
이 비트를 전부 반전시키고, 1을 더하면 1의 보수가 나온다.
예시는 아래와 같다. 1이 -1이 된다.
| 2진수 8 비트 | 10진수 | |
| 10진수 1을 2진수로 표현한다 | 0000 0001 | 1 |
| 부호화 절대치 (부호비트만 반전) | 1000 0001 | |
| 나머지를 반전시킨다 (0을 1로, 1을 0으로) | 1111 1110 | -2 |
| 1을 더한다 | 1111 1111 | -1 |
어떤 수를 부호를 바꾸고자 한다면, 비트를 반전시킨 뒤 1을 더하면 된다.
sign비트로 음수 표현하기
부호를 표현하는 비트가 있냐 없냐에 따라서 표현할 수 있는 수의 범위가 2배 차이 난다.
unsiged의 의미는 부호비트(sign)의 여부를 의미한다.
Integer Overflow 문제
정수의 표현 범위를 넘어서 sign비트가 바뀌면 overflow가 발생한다.
맨 왼편이 -2의 7승, 즉 -128값을 가지기 때문이다. 따라서 각 자료형의 범위에 맞게 연산해야 함을 유의하자.
큰 수를 다룰 때 8byte 정수 자료형 long long을 쓰자.
만약 unsigned long long 을 넘어선다면 string으로 처리해야 하는데, Python을 쓰는게 C++ string을 쓰는 것 보다 편하다.
0x02 실수 자료형
실수 자료형은 float(4byte)와 double(8byte)가 있다.
float는 1bit 32개다.
double은 1bit 64개다.
컴퓨터는 2진수를 기반으로 실수를 표현하기 때문에, 오차가 있음을 기억하자!
1을 3으로 나눠보자.
10진수로 0.33333.... 무한소수로 길어진다.
2진수로 표현하면 ? 0.010101.. 로 역시 무한소수가 나온다.
2진수의 과학적 표기법 IEEE 754 format
실수를 표현하기 위해 32칸 혹은 64칸을 sign field, exponent field, fraction field 로 나눈다.
sign field : 양수/음수 구분
exponent field: 지수
fraction field : 유효숫자
-6.75를 예로 들어보자.
sign field : 음수니까 1로 표시
exponent field: 여기서는 2승이니까 2
fraction field : 맨 앞의 1은 뺀, 1011이 적힌다. (맨 왼쪽부터 2의 -1승, 2의 -2승 ... 자리임)
[중요] 실수 자료형의 특징!
1. 실수 자료형은 필연적으로 오차가 있다.
float는 유효숫자 6자리, double은 유효숫자 15자리 뿐이다.
여기서 유효숫자 15자리라는 의미는
참 값이 1이라고 할 때, 1 - 10의 -15승에서 1 + 10의 +15승 사이의 값을 가진다는게 보장된다는 의미다.
2. double에 long long 범위의 정수를 함부로 담지 말자.
double은 유효숫자가 15자리인데, long long은 최대 19자리 이다.
따라서 10의 18승과 10의 18승을 구분할 수 없고, 오차 섞인 값이 저장될 수 있다.
3. 실수를 비교할 때는 등호를 사용하면 안 된다.
실수 연산 시 오차가 발생할 수 밖에 없기 때문이다.
아까 배운 것 처럼, 유효숫자가 float는 6자리, double은 15자리 뿐으로 표현에 제한이 있기 때문이다.
두 실수가 같은지 알고 싶을 때 !
두 실수의 차가 대략 10의 -12승 이하면 동일하다고 처리하는 것이 안전하다.
1e-12 는 10의 -12승을 의미하는 표기다.
다음 강의에서는 표준 입출력과 코드 작성 팁에 대해 배운다.
2의 보수 자료 출처: 2진수의 수와 음수 표현법
공부 자료 출처: 바킹독 실전 알고리즘 0x01강
'알고리즘 > 실전 알고리즘' 카테고리의 다른 글
| 0x05강 - 스택 (0) | 2021.11.23 |
|---|---|
| 0x04강 - 연결리스트 (0) | 2021.11.22 |
| 0x03강 - 배열 (0) | 2021.11.21 |
| 0x02강 - 기초 코드 작성 요령2 (0) | 2021.11.20 |
| 0x00강 - 오리엔테이션(환경세팅) (0) | 2021.11.19 |
