brunch

연재 중 알고리즘과 수학 02화

라이킷 17 댓글

You can make anything
by writing

C.S.Lewis

계정을 잊어버리셨나요?

by ZeRO Nov 23. 2024

2. 숫자분류 및 문자식, 2진법

알고리즘과 수학

이제부터 진행되는 강좌의 문제나 해설을 읽을 때 중요한 수의 분류와 문자식에 대해, 후반부에서는 프로그램을 작성할 때 중요한 2진법에 대해 설명합니다. 다음 장부터 여러 번 사용하므로 잘 이해해 둡시다.

⑴ 정수, 유리수, 실수

우선 숫자의 종류로 다음 5가지를 기억해 둡시다.

유리수에는 정수가 포함되고 실수에는 정수와 유리수가 포함된다는 점에 유의해야 합니다. 예를 들어 36이라는 정수는 36/1의 형태로도 나타낼 수 있습니다. 또한 일반적으로 음수가 아닌 정수를 비부정수, 양의 정수를 자연수라고 부르기도 합니다. 프로그래밍 문맥에서도 자주 등장하므로 기억해 둡시다.　

실수가 아닌 수의 예로는 2i, -5i와 같은 허수를 들 수 있지만, 이 강좌에서는 다루지 않습니다. 여기까지 많은 용어가 이어졌으니, 아래 그림을 통해 이해를 해봅시다.

⑵ 문자식

사과가 5개 있고 귤이 몇 개 있을 때, 귤의 개수와 과일의 총 개수의 관계를 수식으로 표현해 봅시다. 예를 들어 귤이 2개일 때 5+ 2 = 7 개, 4개일 때 5 + 4 = 9 개가 됩니다. 하지만 이대로는 귤의 구체적인 개수를 알고 있을 때만 관계를 나타낼 수 있습니다.

그래서 귤의 개수를 x로 놓으면 총 개수는 5 + x 개로 나타낼 수 있습니다. 잘 모르겠다면 초등학교 산수에서 0 등의 기호를 사용하여 5 + 〇 개와 같이 표현했던 것을 떠올려봅시다. 이처럼 x, y, z, a, b 등의 문자로 표현한 수식을 문자식이라고 합니다. 문자식을 사용하면 사물의 관계를 한눈에 알 수 있을 뿐만 아니라, 문자에 구체적인 값을 대입(넣어보기)하면 다양한 경우의 수를 계산할 수 있다는 장점이 있습니다.

다른 문자식의 예로는 다음과 같은 것을 들 수 있습니다.

50 + x 100 - y a + b 100a 2a + 3b x + y + y + z xyz　

이러한 문자 수식을 작성할 때는 다음과 같은 '쓰기 규칙'이 있으니 기억해 둡시다.

규칙 1: 곱셈 기호 ×는 생략함. 예) 'a 곱하기 b'를 나타낼 때 [×]a × b [○]ab

규칙 2: 숫자와 문자의 곱셈은 숫자를 먼저 씀. 예) 'a 곱하기 2'를 나타낼 때 [×] a2 [○] 2a

규칙 3: 1과 문자의 곱셈은 문자만 씀. 예) 'a 곱하기 1'을 나타낼 때, ［×］1a ［○］a

규칙 4: -1과 문자의 곱셈은 문자에 마이너스를 붙임. 예) 'a 곱하기 -1'을 나타낼 때, ［×］-1a ［○］-a

⑶ 앞으로 강좌에서 사용하는 문제 문장 형식 ⓐ

문제를 푸는 알고리즘을 설계한다는 것은 단순히 하나의 케이스에 대한 답을 구하는 것이 아니라, 다양한 케이스에 대해 올바른 답을 구하기 위한 절차를 제시하는 것입니다. 따라서 대상 케이스의 범위를 명확하게 기술하기 위해 이 강좌에서는 다음과 같이 문자식을 사용하여 문제 문장을 작성하는 경우가 있습니다.

이 문제 문장은 “정수 N을 입력으로 받아 5 + N의 값을 출력하는 프로그램을 작성하시오”라는 의미입니다. 예를 들어,

N = 2가 입력되면 프로그램은 5 + 2 = 7을 출력해야 한다.

N = 4가 입력되면, 프로그램은 5 + 4 = 9를 출력해야 한다.

1 이상 100 이하라는 제약 조건을 만족하는 어떤 정수 N이 입력되더라도 올바른 출력을 해야 한다.

라는 것입니다. 이 문제를 푸는 프로그램의 예시로 아래 코드를 생각해 볼 수 있습니다. 익숙하지 않은 문제 문장의 형식일 수도 있지만, 이 강좌를 읽다 보면 자연스럽게 익숙해질 수 있을 것입니다.

⑷ 앞으로 강좌에서 사용하는 문제 문장 형식 ⓑ

앞에서 x, y, z, a, b 등을 사용한 문자식을 소개했지만, 다루는 문자의 수가 많은 경우 수열과 같이 번호를 매겨 A1, A2, A3로 구분하는 경우가 있습니다. 다음 문장을 생각해 봅시다.

안창호는 A1개, 김구는 A2개, 윤봉길은 A3개, 홍범도는 A4개의 사과를 가지고 있다. 총 A1 + A2 + A3 + A4 사과가 있다.　

이 문장의 의미는 다음 문장의 의미와 동일하다.

안창호는 a개, 김구는 b개, 윤봉길은 c개, 홍범도는 d개의 사과를 가지고 있다. 총 a + b + c + d 개의 사과가 있다.　

이것은 프로그래밍 문제에서도 마찬가지입니다. 많은 값이 입력되는 문제에서는 예를 들어 다음과 같은 형태로 문제 문장이 쓰여질 수 있습니다.

이 문제는 입력으로 받은 3개의 정수가 1 이상 100 이하인 모든 경우에 3개의 정수의 합인 A1 + A2 + A3를 출력하는 코드와 같은 프로그램을 작성하도록 요구하고 있습니다. 예를 들어, A1 = 10, A2 = 20, A3 = 50일 때 10 + 20 + 50 = 80을 출력해야 합니다. A1 = 101, A2 = 50, A3 = -20과 같이 제약조건에 어긋나는 입력은 주어지지 않습니다.

⑸ 앞으로 강좌에서 사용하는 문제 문장 형식 ⓒ

이 강좌의 문제 형식에 익숙해지기 위해 한 가지 예를 더 들어보겠습니다. 여기서 A1 , A2 , ... , ... , AN이라는 표기가 있는데, 중간을 생략한 것뿐입니다. 예를 들어 N = 5인 경우 'A1, A2, A3, A4, A5가 주어졌으니 A1 + A2+ A3 + A4 + A5를 출력해 주세요'라는 뜻입니다.

이 문제는 먼저 정수 N을 입력으로 받은 후, N개의 정수를 입력받아 그 합계를 출력하는 코드와 같은 프로그램을 작성하도록 요구하고 있습니다. 예를 들어 N = 5, (A1 , A2 , A3 , A3 , A4 , A5 ) = (3,1, 4, 1, 5)일 때 3 + 1 + 4 + 4 + 1 + 5 = 14를 출력해야 합니다.

제약 조건란의

1 ≤ Ai ≤ 100

이라는 표기가 궁금하신 분들도 있을 텐데, 여기서는 '모든 i에 대해 Ai 가 1 이상 100 이하', 즉 A1 , A2 , ... , ... , AN 모두 1 이상 100 이하'라는 의미입니다. AN 모두 1 이상 100 이하라는 의미입니다. 이번 강좌에서 다루는 프로그래밍 문제의 제약 조건 섹션에서는 비슷한 표기를 사용하는 경우가 있는데, 기본적으로 '이 문자에 관련된 모든 입력이 ≤ 등으로 표현되는 제약 조건을 만족한다'고 생각하면 됩니다.

또한 이후의 문제문에서는 문장을 간결하게 하기 위해 '정수 A1, A2, A3가 주어집니다'와 같이 명시하지 않는 경우도 있지만, 원칙적으로 모든 변수가 주어진다고 생각하시면 됩니다.

⑹ 2진법이란?

다음으로 2진법에 대해 설명하겠습니다. 여러분은 일상적으로 0부터 9까지 10가지 숫자로 숫자를 표현하는 10진법을 사용하지만, 컴퓨터 내부에서는 0과 1의 두 가지 숫자만으로 숫자를 표현하는 2진법을 사용하여 계산이 이루어집니다. 예를 들어,

'10001'에 1을 더하면 '10010'이 됨(아래 1자리에 대해 앞당겨짐)

'10101'에 1을 더하면 '10110'이 됨(아래 1자리만큼 앞당겨짐)

'10111'에 1을 더하면 '11000' (아래 3자리까지 앞당겨짐)

'11111'에 1을 더하면 '100000' (아래 5자리까지 앞당겨짐)

이 됩니다. 이는 10진법에서 다음과 같은 덧셈과 비슷하며, 2진법에서 오른쪽부터 1이 연속되는 부분을 모두 9로 바꾸면 쉽게 이해할 수 있을 것입니다.

'10009'에 1을 더하면 '10010'이 됨

'10109'에 1을 더하면 '10110'이 됨

'10999'에 1을 더하면 '11000'이 됨

'99999'에 1을 더하면 '100000'이 됨

이 규칙에 따라 0부터 119까지의 숫자를 세어보면 아래 표와 같습니다.

⑺ 2진법 ⇒ 10진법 변환

그렇다면 2진법을 10진법으로 변환하려면 어떻게 해야 할까요? 0부터 하나씩 숫자를 더하면 시간이 오래 걸리지만, 사실 단위(위치)의 성질을 이용하면 효율적으로 변환할 수 있습니다.　

10진법의 구조부터 설명하자면, 10진법에서는 아래부터 1의 자리, 10의 자리, 백의 자리, 천의 자리 등 순서대로 자릿수에 자릿수가 붙고, '자릿수와 그 자릿수의 곱셈'의 합이 원래의 정수가 됩니다. 아래 그림은 314와 2037의 경우의 예입니다.

2진법도 비슷한 원리로 작동하는데, 1을 두 배로 하면 1→2→4→4→8→...이 되므로 1의 자리, 2의 자리, 4의 자리, 8의 자리, 이렇게 숫자에 자리를 붙이는 것을 생각해 봅시다. 이때 '자리와 그 자릿수의 곱셈'의 합이 2진법을 10진법으로 변환한 값이 됩니다. 예를 들어 1011을 10진법으로 변환한 값은 11, 11100을 10진법으로 변환한 값은 28입니다.

⑻ 3진법 등에 대해

앞에서 10진법과 2진법을 다루었지만, 그 외의 경우(3진법, 4진법)도 마찬가지입니다. 먼저 3진법은 0, 1, 2의 조합으로 숫자를 표현하는 방식이며, '3'이 되면 앞뒤로 올라가는 현상이 발생합니다. 따라서 1에 3을 계속 곱하면 1→3→9→27→81→...이 되므로 1의 자리, 3의 자리, 9의 자리, 27의 자리 등 규칙에 따라 자릿수에 자리를 붙이는 것을 생각해 봅시다.

이때 '자리와 그 자리의 수를 곱한 값'의 합이 3진법을 10진법으로 변환한 값이 됩니다. 예를 들어 3진법 1212를 10진법으로 변환한 값은 50입니다. 또한 3진법에서 'abc'주2.1.4로 표기되는 숫자를 10진법으로 변환한 값은 9a + 3b + c입니다.

다음으로 4진법은 0, 1, 2, 3의 조합으로 숫자를 표현하는 방법이며, '4'가 되면 앞뒤로 올라가는 현상이 발생합니다. 따라서 1에 4를 계속 곱하면 1→4→16→16→64→256→...이 되므로 1의 자리, 4의 자리, 16의 자리, 64의 자리 등의 규칙으로 자릿수에 자리를 매기는 것을 생각해봅시다. 이때 '자리와 그 자릿수의 곱셈'의 합이 4진법을 10진법으로 변환한 값이 됩니다. 예를 들어 4진법 2231을 10진법으로 변환한 값은 173이며, 5진법, 6진법 등도 마찬가지로 정의되어 비슷한 방식으로 10진법으로 변환할 수 있습니다.

⑼ 10진법에서 2진법등의 변환

아래 그림과 같이 '숫자가 0이 될 때까지 2로 나눈 나머지를 써서 아래에서 읽어 내려가는 방식'으로 10진법을 2진법으로 변환할 수 있습니다.

10진법을 2진법 이외의 방식으로 변환할 때도 비슷한 방법을 사용할 수 있습니다. 예를 들어 3진법의 경우, 숫자가 0이 될 때까지 3으로 나눈 나머지를 써 내려가면서 아래에서 읽으면 됩니다. 아래 그림 오른쪽의 예처럼 10진법을 같은 10진법으로 변환하는 경우에도 잘 작동합니다.

조금 어렵지만, 이 방법이 잘 작동하는 이유는 2진법의 미계산 부분에 주목하면 쉽게 이해할 수 있습니다. 위 그림의 왼쪽 예제에 대해 순서대로 설명하면 다음과 같습니다.

먼저 11 ÷ 2는 5보다 1이 더 많은 것으로 계산되며, 11을 2진법으로 표기한 값 '1011'의 위쪽 3자리가 5를 2진법으로 표기한 값 '101'과 일치한다.

다음으로 5 ÷ 2는 2 ÷ 2는 2보다 1을 더한 값으로 계산되며, 11을 2진법으로 표기한 값 '1011'의 위 두 자리가 2를 2진법으로 표기한 값 '10'과 일치한다.

다음으로 2 ÷ 2는 2 ÷ 2는 1이 0으로 계산되며, 11을 2진법으로 표기한 값 '1011'의 위쪽 1자리가 1을 2진법으로 표기한 값 '1'과 일치한다.

마지막으로 10진수 N을 입력받아 2진수로 변환한 값을 출력하는 프로그램의 예로 아래 코드를 들 수 있습니다. 여기서 N % 2, N / 2 등 '2'의 값을 모두 '3'으로 바꾸고 적절히 경우 나누기를 하면 3진수 정수로 변환할 수 있으며, 4진법 등 다른 경우도 마찬가지입니다.