0x01강

Last updated - 2025년 06월 19일 Edit Source

• 바킹독
• 코딩테스트

1강에서는 시간복잡도, 공간복잡도, 정수 자료형, 실수 자료형과 관련된 내용을 학습한다. 기초 문제는 제공되지 않고 전반적인 흐름을 잡고 넘어가는 수업으로 생각보다 중요하니 집중하도록 하자.

• [바킹독의 실전 알고리즘] 0x01강 - 기초 코드 작성 요령 1

컴퓨터는 1초에 대략 3억 ~ 5억 번의 연산을 수행

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int func1(int arr[], int n) {
	int cnt = 0;

	for (int i = 0; i < n; i++) {
		if (arr[i] % 5 == 0) {
			cnt++;
		}
	}

	return cnt;
}

• 총 몇 번의 연산?
  • 변수 cnt에 0 대입하는 과정 → 1번
  • 반복문 내부 i에 0 대입하는 과정 → 1번
  • n번 반복
    • i가 n보다 작은지 비교 → 1번
    • 비교 이후 증가 → 1번
    • arr 나머지 5 → 1번
    • 또 그게 0과 같은지 비교 → 1번
  • cnt 반환 → 1번
• 1 + 1 + n * (2 + 2 + 1) + 1 = 5n + 3
  • n이 100만 → 500만 → 1초 안에 가능
  • n이 10억 → 50억 → 1초 안에 불가능

Q. 대회장에 N명의 사람들이 일렬로 서있음. 이름이 “가나다"인 사람을 찾는데 걸리는 시간 (이름을 물어보고 듣는데까지 1초가 걸림)

• A. 최선 (1초), 최악 (N초), 평균 (N/2초)

Q. 대회장에 N명의 사람들이 일렬로 서있음. 근데 사람들이 이름순으로 서있음. 이름이 “가나다"인 사람을 찾는데 걸리는 시간 (이름을 물어보고 듣는데까지 1초가 걸림)

• A. 업다운 게임처럼 중간 사람에게 계속 물어보면 됨. 최선 (1초), 최악 (log N초), 평균 (log N초)
• 코딩테스트에서 로그는 밑이 2인 로그만 나옴
  • $log_2 2 = 1$, $log_2 4 = 2$, $log_2 8 = 3$, $log_2 16 = 4$, $log_2 32 = 5$

입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계

• 512MB = 1.2억개의 int
• int 1개가 4byte이니까

Integer Overflow

• sign field (float : 1, double : 1)
  • 음수인지 양수인지
• exponent field (float : 8, double : 11)
  • 지수
• fraction field (float : 23, double : 52)
  • 유효숫자

• -6.75
  • sign field
    • 부호 음수니까 1
  • exponent field
    • 지수는 2인데 여기에 127을 더한 129를 exponent에 기록
    • 129 → 10000001
    • 127을 더하는 이유는, 이렇게 더해야 음수의 지수승도 exponent에 넣을 수 있어서
  • fraction field
    • 1.1011에서 1을 제외한 1011을 기록
    • 맨 왼쪽부터 $2^{-1}, 2^{-2} \dots$
    • 10110000000 … 이렇게 왼쪽부터 채우면서 적혀짐
  • 이렇게 실수로 저장하는 방식을 IEEE-754 format이라고 함

1. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다.

• 0.1 + 0.1 + 0.1 != 0.3
  • 유효숫자가 들어가는 fraction field가 유한하기 때문에 2진수 기준으로 무한소수를 저장할 때는 float의 경우 앞 23 bit, double은 앞 52 bit 까지만 잘라서 저장할 수 있음
  • 0.1은 무한소수니까 오차가 발생한 상태로 저장되었고, 그걸 3번 더하니까 위와 같은 결과가 발생
• fraction field를 가지고 float은 유효숫자 6자리, double은 유효숫자 15자리까지 정확히 표현 가능
  • float → 상대오차 $10^{-6}$ 까지 안전
  • double → 상대오차 $10^{-15}$ 까지 안전
    • 값이 1이라고 하면, $1 - 10^{-15}$ ~ $1 + 10^{-15}$ 이 사이의 값을 가진다는게 보장됨
  • 오차가 생기는 것 자체를 막을 수 없지만, 오차가 어느정도인지는 알 수 있게됨
• 실수 자료형은 필연적으로 오차가 있으니까, 필요하다면 문제에서 절대/상대 오차를 허용한다는 단서를 줌
  • 

2. double에 long long 범위의 점수를 함부로 담으면 안된다.

• double은 유효숫자 15자리, long long은 최대 19자리
• $10^{18} + 1$과 $10^{18}$ 구분 불가능
• int의 경우 double에 담아도 오차 생기지 않음

3. 실수를 비교할 때는 등호를 사용하면 안된다.

• 1번 예시에서 이미 봤음
• 두 실수가 같은지 알고 싶으면, 둘의 차이가 아주 작은 값, 대략 $10^{-12}$ 이하면 동일하다고 처리해야 안전
  • $1e - 12$가 $10^{-12}$ 이다.
  • $10^{9}$은 $1e9$ 라고 써도 된다.