2진수(Binary), 16진수(Hexadecimal), 10진수(Decimal), 압축, 선형탐색, 이진탐색

바이너리 Binary 2진수

컴퓨터의 모든 정보(그림이나 문자 등)는 2진수 형태로 입력, 출력, 저장된다

0과 1로만 정보를 처리하고 저장하는 2진수를 사용

숫자를2진수로 나타내는 방법

숫자 21을 2진수로 나타내보자

1. 32, 16, 8, 3, 2, 1의 숫자 카드가 있다고 가정
2. 숫자 21을 만들기 위해서는 16, 4, 1 카드가 필요하다
3. 32, 16, 8, 4, 2, 1의 카드 사용여부를 1과 0으로 나타낸다면 010101로 표시할 수 있다

같은 방법으로 15는  8+4+2+1 이기 때문에 1111으로 표시할 수 있다

27은 11011

 

숫자 카드 5장으로 만들 수 있는 최대 수는 무엇일까?

2^(5장의 카드) - 1 = 255

0부터 시작하기 때문에 -1을 해주는 것

 

16진수 Hexadecimal

숫자 500을 2진수로 표현한다면 111110100 으로 표현해야 하는데 너무 복잡해진다

조금 단순하게 표현하기 위해서 16진수로 표현할 수 있다 

0과 1 대신에 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F로 나타내는 것

500은 1F4로 표시할 수 있다

111110100을 16진수로 바꾸는 방법은 간단하게 오른쪽부터 4개씩 끊어서 표시하면 쉬운데

1, 1111, 0100 으로 나누고 1은 1로, 1111은 F로, 0100은 4로 표시하는 것

 

참고로 10진수는 decimal, 위에서 사용했던 카드는 곧 컴퓨터의 bit에 해당하는 것이다

bit는 binary digit의 줄임말

 

알파벳은 몇장의 카드로 나타낼 수 있을까?

알파벳 26자는 2^5 보다 작기 때문에 5장의 카드로 나타낼 수 있다

키보드를 사용한다면? 한글도 있고, 특수기호 문자들도 있다

만약 256보다 작은 수의 문자들이라면 2^8, 8비트를 이용해서 나타낼 수 있을 것이다

 

요즘의 컴퓨터 운영체제는 64비트를 사용해서 정보를 처리한다

64비트를 하나의 묶음으로 처리한다는 뜻

 

압축

컴퓨터가 문자를 표시하고 이해로 할 때는 어떤 형태로 이해할까? 

컴퓨터의 화면은 는 작은 단위의 사각형, 픽셀로 이루어져 있는데

a라는 글자를 표현하기 위해서는 6*6의 픽셀들을 사용해서 아래와 같이 표시할 수 있다

이때 흰 픽셀을 1, 검은 픽셀을 2로 나타낸다면 

 

100001

000001

011111

100001

100011

100010

로 나타낼 수 있다

 

컴퓨터는 이를 좀더 효율적으로 사용하기 위해 압축하는 기술을 쓰는데,

색깔이 연속적으로 나타나는 숫자만 대신 써준다고 생각해보자

100001은 1이 1번, 0이 4번, 1이 1번이니 100001을 1,4,1로 나타낼 수 있다

 

그래서 a의 표시는 결국

1,4,1

5,1

1,5

0,4,1

0,3,2

0,3,1,1

으로 압축해서 나타낼 수 있다

 

팩스도 이런 원리를 통해서 사용되는 것인데

팩스는 흑백페이지를 대략 1000 * 2000 픽셀로 스캔한 후 다른 팩스 기기에서 인쇄하는 작은 컴퓨터로 볼 수 있다

1000 by 2000 픽셀을 그대로 주고 받기에는 비용이 많이 들기 때문에 압축해서 간단한 정보를 주고 받는 것이다

이렇게 팩스는 원본의 약 1/7정도로 압축할 수 있다고 한다

 

사진이나 그림의 경우에는 1/10 에서 많게는 1/100으로 압축이 가능하다

JPEG, GIF, ZIP, PNG 등의 확장자를 가진 파일들은 모두 이런 압축기술을 활용해서 저장된 것들이다

 

컬러는 어떻게 저장이 될까?

컬러는 색의 기본 요소인 적,녹, 청을 혼용해서 사용한다

노란색, 검정색, 흰색 등은 이 적, 녹, 청 다시 말해 RGB를 적절히 혼용해서 쓰는 것

노란색은 R과 G를 섞어서 (1, 1, 0)

흰색은 모두를 섞어서 (1, 1, 1)

검은색은 모든 것을 섞지 않아서 만들 수 있다 (0, 0, 0)

 

다시 돌아가서 컴퓨터는 직접 글자를 표현하지 않고, 글자와 매핑되는 코드를 사용해서 표시한다

이때 매칭되는 표를 코드표라고 한다

이런 코드 표는 세계적으로 약속된 것이고

우리가 범용적으로 사용하는 코드표에는 아스키 코드가 있다

우리가 실제로 사용하는 문자들이 아스키 코드에 코드표로 맵핑이 되어있다

 

정보의 탐색

컴퓨터는 어떻게 정보를 탐색할까?

1. 무작위 검색

2. 앞에서부터 확인, 선형탐색 (0번 확인, 1번 확인, 2번확인)

선형탐색은 우리가 찾아봐야 하는 정보가 정돈되어있지 않고 아무런 특징을 발견할 수 없을때 사용

단점은 우리가 찾아야 되는 정보가 많거나 찾고자 하는 자료가 맨 뒤쪽에 존재한다면 시간이 오래걸림

선형탐색은 언제 사용될까?

office 프로그램에서 찾기 버튼

3. 조건을 사용해서 찾아보기, 2진 탐색, binary 탐색

데이터가 미리 정렬되어 있다면 특정 기준이 되는 값을 중심으로 탐색해나가는 것

장점은 자료의 양이 많을 수록 더 빠른 결과를 보임

단점은 자료가 정렬되어있어야함

판단을 해서 검색의 범위를 줄여 나가는 방법

 

어떤 경우에 선형탐색?

어떤 경우에 이진탐색?

 

데이터의 양이 많지 않고 정리할 수 있는 패턴이 발견되지 않는다면 선형 탐색 - 평균적으로 (1 + n)/2 번 탐색

데이터의 양이 광범위하고 정리할 수 있는 패턴이 되어있다면 이진 탐색 - log n 만큼의 횟수만으로 탐색할 수 있음