[자료구조 기초 - 정수(Integer)]백준 사파리월드(2420번) 풀이 (C++/Python)
가장 먼저 비트(bit)/바이트(byte) 개념을 간단하게 알아보고 가겠습니다.
컴퓨터 공학에서 비트(bit)는 0 혹은 1로 이루어진 데이터 단위입니다.
비트 0은 스위치가 열린 상태, 비트 1은 스위치가 닫힌 상태입니다.
스위치가 열리면 조명이 꺼지고, 스위치가 닫히면 조명이 켜집니다.
스위치 하나만으로 데이터의 최소 단위를 표현할 수 있습니다.
그 다음으로 바이트(byte)는 무엇일까요?
바이트(byte)는 8개의 비트로 이루어진 데이터 단위입니다.
즉, 8개의 비트로 이루어져 있으니 1 byte로 총 2^8 = 256가지의 데이터를 표현할 수 있습니다.
여기서 자료구조 중 정수형 자료는 다음과 같은 종류가 존재합니다.
(C++ 기준입니다.)
| char | 1 byte |
| short | 2 byte |
| int/long | 4 byte |
| long long | 8 byte |
그러면 byte로 어떻게 정수를 표현한다는 것일까요?
먼저 2진수에 대해 간단하게 알아보고 넘어가겠습니다.
10을 2진수로 변환할려면 어떻게 해야 할까요?
아래의 사진을 확인해주세요.
이렇게 10을 2진수로 변환하면 1010이 됩니다.
이것을 1 byte 형식으로 표현하면 0000 1010이 됩니다.
그러면 여기서 음수도 가능할까요?
네, 가능합니다!
-1을 2진수로 표현할 수 있어요.
먼저 1을 2진수로 표현합니다. 그러면 0000 0001이 되겠죠?
그 다음 0을 1로, 1을 0으로 바꾸세요. 그러면 1111 1110이 됩니다.
그 다음에 +1을 해주세요. 그러면 1111 1111이 됩니다. 이것이 바로 -1을 2진수로 표현한 것입니다.
같은 원리로 -4도 해볼까요? 4 -> 0000 0100이 되고, 그 다음 다 바꿔서 1111 1011이 되고, 여기에 +1을 해서 1111 1100이 됩니다.
이것이 바로 -4를 2진수로 바꾸면 1111 1100이 됩니다.
여기서 맨 앞에 있는 비트가 제일 중요합니다.
맨 앞에 있는 비트가 0이면 양수, 1이면 음수입니다.
자, 그러면 이제 1 byte로 어디까지 표현할 수 있을까요?
우선 양수 기준으로 보면 0111 1111까지 표현할 수 있으며 계산하면 127이 됩니다.(2^(8-1) - 1)
그리고 -128을 2진수로 바꿀까요? 그러면 1000 0000이 되고, 다 바꿔서 0111 1111이 되고 그 다음 +1을 해주세요.
그러면 -128은 1000 0000이 되며 -128보다 더 작은 음수는 표현할 수 없습니다.(-2^(8-1))
따라서 1 byte(8 bits)로 표현할 수 있는 정수 범위는 -128 이상 127 이하입니다.
같은 원리로 2 byte, 4 byte, 8 byte로 표현할 수 있는 정수 범위를 구해봅시다.
| char | 1 byte(8 bits) | -128 이상 127 |
| short | 2 byte(16 bits) | -32,768 이상 32,767 이하 |
| int/long | 4 byte(32 bits) | -2,147,483,648 이상 2,147,483,647 이하 |
| long long | 8 byte(64 bits) | -9,223,372,036,854,775,808 이상 9,223,372,036,854,775,807 이하 |
즉, 데이터 범위는 bits를 n으로 가정한다면 -2^(n-1) 이상 2^(n-1) - 1 이하입니다.
그리고 여기서 unsigned가 추가된다면 어떻게 될까요?
음수로 표현할 수 없는 대신 양수 범위가 더 증가하게 됩니다.
예시로 1 byte 기준으로 -3같은 음수는 표현할 수 없으나 144, 196같은 기존 범위를 넘어서는 양수를 표현할 수 있습니다.
이 때 1 byte 기준으로 0 이상 2^8 - 1 이하, 즉 0 이상 255 이하입니다.
즉, bits가 n이면 unsigned가 붙일 때 0 이상 2^n - 1 이하입니다.
컴퓨터 공학 기초 지식을 알려주고 시작하는 이유는 Python을 제외한 대부분 프로그래밍 언어에서는 정수 범위를 신경 써서 풀어야 하는 문제가 존재합니다.
그 문제들 중 가장 쉬운 문제인 사파리월드(2420번)가 존재합니다.
문제 : 사파리월드(2420번)(Bronze V)
문제 링크 : https://www.acmicpc.net/problem/2420
출처 : Baekjoon Online Judge
이 문제는 너무 간단합니다.
그냥 a - b의 절대값을 구하면 끝나는 문제입니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b;
cin >> a >> b;
cout << abs(a - b);
return 0;
}그러면 제출해볼까요?
"틀렸습니다"라고 뜹니다.
왜 그럴까요?
정수 범위를 초과했기 때문입니다.
이 문제의 입력 범위가 -2,000,000,000 이상 2,000,000,000 이하입니다.
만약 A가 2,000,000,000이고 B가 -2,000,000,000이면 답은 4,000,000,000이 되어야 하는데 int 범위가 넘어가서 다른 값이 나오게 됩니다.
input
2000000000 -2000000000
output
294967296
answer
4000000000그러므로 여기서는 long long으로 변경해야 합니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b;
cin >> a >> b;
cout << abs(a - b);
return 0;
}이렇게 해서 제출하겠습니다.
맞았습니다!!
참고로 Python에서는 범위를 신경쓰지 않아도 됩니다.
알아서 메모리 할당해주고 범위 계산해주기 때문입니다.
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
print(abs(N - M))