brunch

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

라이킷 21 댓글

You can make anything
by writing

C.S.Lewis

계정을 잊어버리셨나요?

by ZeRO Nov 26. 2024

3. 기본 연산과 기호

문제해결을 위한 알고리즘 입문

독자분들도 기억하시겠지만 초등학교에서 사칙연산(+, -, ×, ÷)을 배웠을 것이며, 그 외에도 다양한 연산과 기호가 있습니다. 유명한 예로는 나머지, 절대값, 거듭제곱, 루트 등을 들 수 있습니다. 또한, 컴퓨터는 전기적으로 움직이기 때문에 on/off의 정보(비트)를 정보의 최소 단위로 삼고, 2진법을 사용하여 계산을 합니다. 따라서 비트 단위로 논리 연산을 하는 AND, OR, XOR 등의 '비트 연산'이 중요해집니다. 이번 강좌에서는 이 부분을 설명합니다.

⑴ 나머지 (mod)

a를 b로 나눈 나머지를 a mod b라고 씁니다. 예를 들면,

8 mod 5 = 3(8 ÷ 5는 1에 나머지 3)입니다.

869 mod 120 = 29(869 ÷ 120은 7에 나머지 29)입니다.

C++, Python 프로그래밍 언어 등에서는코드로 표현하면 a % b라는 형식으로 계산할 수 있습니다.

⑵ 절대값 (abs)

a의 부호(+, -) 부분을 뺀 수를 a의 절대값이라고 하며, |a|라고 씁니다. 즉, a가 0 이상인 경우, |a| = a, a가 음수인 경우 |a| = -a가 됩니다. 예를 들어,

-|-20| = 20

-|-45| = 45

-|15| = 15

-|0| = 0

C++, Python 프로그래밍 언어 등에서는 코드로 표현하면 abs(a)를 사용하여 계산할 수 있습니다.

⑶ 거듭제곱 (pow)

a에 b를 곱한 값을 a의 b제곱이라고 하며

라고 합니다. 예를 들면,

입니다. 특히 a의 제곱은

이며, C++에서는 코드는 pow(a, b), Python에서는 a** b라는 형식으로 계산할 수 있습니다.

⑷ 제곱근 (sqrt)

0이상의 실수 a에 대해

가 되는 음이 아닌 실수 x를 루트a라고 하며,

라고 씁니다. 즉, 면적 a의 정사격형의 한변의 길이가 a입니다. 예를 들면,

입니다. 마지막 예시처럼 유리수가 아닌 경우가 있는데 C++에서는 코드는 sqrt(a), Python에서는 math.sqrt(a)를 사용하여 계산할 수 있습니다.

또한, 루트는 3제곱 이상으로 확장할 수 있으며, 0이상의 실수 a, 자연수 b에 대해,

가 되는 비부정 실수x를

로 표시합니다. 구체적인 예시는 아래와 같습니다.

C++코드 (mod, abs, pow, sqrt 예제)

Python 코드

⑸ 비트연산 전: 논리 연산이란?

비트 연산에 들어가기 전에 먼저 기초가 되는 논리 연산에 대해 설명합니다. 논리 연산은 0(FALSE) 또는 1(TRUE)을 취하는 값 사이에서 이루어지는 연산으로, 다음 세 가지가 유명합니다.

a AND b: a, b가 모두 1이면 1, 그렇지 않으면 0

a OR b : a, b 중 적어도 하나가 1이면 1, 그렇지 않으면 0

a XOR b: a, b 중 하나만 1이면 1, 그렇지 않으면 0　

아래 그림은 논리 연산의 이미지를 보여주는데, AND는 1이 되는 조건이 가장 까다롭습니다.

비트 연산은 주로 컴퓨터에서 이루어지는 연산 중 하나로 AND연산, OR연산, XOR연산의 3가지에 대해서는 아래와 같은 흐름으로 계산이 이루어집니다.

정수(보통 10진법)를 2진법으로 변환한다.

숫자(1의 자리, 2의 자리, 4의 자리, 8의 자리...)별로 논리연산을 수행한다.

논리 연산의 결과를 정수(보통 10진법)로 변환한다.

아래 구체적인 예시를 몇가지 소개합니다.

⑹ 비트 연산의 예시㉠ AND 연산

AND 연산은 2진법 표현의 각 숫자마다 논리 연산의 AND를 수행하는 것입니다. 예를 들어 11 AND 14의 값은 다음과 같이 계산됩니다.

11을 2진법으로 변환하면 '1011'이 된다.

14를 2진법으로 변환하면 '1110'이 된다.

1의 자리(아래에서 1번째 자리)에 대한 AND: 1 AND 0 = 0이다.

2의 자리(아래에서 2번째 자리)에 대한 AND: 1 AND 1 = 1이다.

4의 자리(아래에서 3번째 자리)에 대한 AND: 0 AND 1 = 0이다.

8의 자리(아래에서 4번째 자리)에 대한 AND: 1 AND 1 = 1이다.

계산 결과를 위쪽 자리부터 순서대로 정리하면 1010이 되고, 이를 10진법으로 변환하면 10이 된다.

따라서 11 AND 14 = 10이다.　

그 외의 구체적인 예시와 계산 이미지는 아래 그림과 같습니다. 비트 연산에서는 일반적인 덧셈과 같은 전진 처리가 발생하지 않는다는 점에 유의해야 합니다.

⑺ 비트 연산 예시 ㉡: OR 연산　

OR 연산은 2진법 표현의 각 숫자마다 논리 연산의 OR을 수행하는 것입니다. 예를 들어 11 OR 14 = 15입니다. 계산 이미지는 아래 그림과 같습니다.

⑻ 비트 연산 예시 ㉢: XOR 연산

XOR 연산은 2진법 표현의 각 숫자마다 논리 연산의 XOR 연산을 수행하는 것입니다. 예를 들어 11 XOR 14 = 5입니다. 계산 이미지는 아래 그림과 같습니다.

⑼ 비트연산 구현

C++, Python와 같은 프로그래밍 언어에서는 비트 연산을 하기 위해 굳이 10진법을 2진법으로 변환할 필요가 없습니다. 사칙연산과 마찬가지로 다음 표와 같이 하나의 기호를 사용하여 구현할 수 있습니다.

아래 코드는 정수 a, b를 입력하면 1행에 a AND b, 2행에 a OR b, 3행에 a XOR b를 출력하는 프로그램입니다. 예를 들어 a = 11, b = 14가 입력되면 1행부터 순서대로 '10, 15, 5'가 출력됩니다.

C++ 코드

Python 코드

⑽ 3개 이상의 AND, OR, XOR

두 정수에 대한 AND, OR, XOR을 소개했지만, 세 개 이상의 정수에 대한 AND, OR, XOR도 계산할 수 있습니다. 구체적인 절차는 다음 페이지와 같습니다.

① 3개의 정수에 대한 연산의 경우　

3개의 정수 a, b, c에 대한 AND, OR, XOR은 '먼저 두 값에 대해 비트 연산을 하고, 그 결과와 나머지 한 값에 대해 비트 연산을 한다'는 흐름으로 계산됩니다. 수식으로 표현하면 다음과 같습니다.

a AND b AND c = (a AND b) AND c = a AND (b AND c)

a OR b OR c = (a OR b) OR c = a OR (b OR c)

a XOR b XOR c = (a XOR b) XOR c = a XOR (b XOR c)　

여기서 어떤 순서로 계산해도 계산 결과는 변하지 않습니다. 예를 들어, a = 11, b = 27, c = 40인 경우 아래 그림과 같이 모든 결과가 동일합니다.

② 4개 이상의 정수에 대한 연산의 경우　

4개 이상의 정수에 대한 연산은 어떤 순서로 계산하든 계산 결과는 변하지 않습니다. 따라서 N개의 정수 A1, A2, A3, ..., ..., AN에 대한 비트 연산은 다음과 같이 할 수 있습니다.

AND 연산: (((A1 AND A2 ) AND A3 ) AND A3 ) AND A4 ) AND ... AN

OR 연산: (((A1 OR A2 ) OR A3 ) OR A3 ) OR A4 ) OR ... AN

XOR 연산: (((A1 XOR A2 ) XOR A3 ) XOR A4 ) XOR ... AN　

물론 다른 순서로 계산해도 동일한 결과를 얻을 수 있습니다. 예를 들어 12 XOR 23 XOR 34 XOR 45의 값은 5가지 방법으로 계산할 수 있지만, 계산 결과는 모두 20입니다.

③ 3개 이상의 AND, OR, XOR에 대한 성질　

3개 이상의 정수에 대한 AND, OR, XOR 연산을 할 때, 각 숫자에 대해 다음과 같은 흥미로운 성질이 성립합니다.

AND 연산: 모든 숫자에 대해 해당 자릿수가 1이면 계산 결과는 1, 그렇지 않으면 0이다.

OR 연산: 어느 한 숫자에 대해 그 자릿수가 1이면 계산 결과는 1, 그렇지 않으면 0이 된다.

XOR 연산: 숫자의 자릿수가 1인 숫자가 홀수인 경우 1, 그렇지 않은 경우 0을 반환한다.　

예를 들어, 12 XOR 23 XOR 34 XOR 45의 경우, 4위, 16위만 홀수인 1이 됩니다. 또한, 계산 결과인 20도 4의 경우, 16의 경우 1이 됩니다.

⑾ 비트연산 예시 ㉣: 왼쪽 시프트와 오른쪽 시프트

왼쪽 시프트 연산, 오른쪽 시프트 연산은 정수 a, b에 대한 연산으로, a를 2진법으로 표현했을 때 비트를 b 개씩 왼쪽/오른쪽으로 이동시키는 연산입니다.　

시프트 연산의 사양은 프로그래밍 언어에 따라 다르지만, 예를 들어 C++의 경우 다음 표와 같이 하나의 데이터(int형 등)의 자릿수가 2진법으로 8~64자리로 정해져 있습니다. 따라서 시프트 연산을 수행하면 '넘친 비트'가 발생하며, 이 비트는 지워진다는 점에 유의해야 합니다. 아래 그림은 8자리 2진수 00101110에 대한 시프트 연산의 예를 보여줍니다.

C++에서는 왼쪽 시프트는 (a << b), 오른쪽 시프트는 (a >> b) 형태로 구현할 수 있습니다. 예를 들어 (46 << 1) = 92, (46 >> 2) = 11입니다. 또한 (1 << N)은 2N을 나타내며, 조합의 전체 탐색이나 반복제곱법등에서 사용합니다.