[CT] 수열&자료구조 - AND,OR,XOR

 

오늘은 수열 알고리즘 XOR에 대한 문제를 다뤄보았다.

 

문제는 간략히 다음과 같다

 

어떤 수열에서 [a,b]구간의 각 수에 c라는 값으로 비트간 XOR을 적용하여 새로운 수열을 구하라.

2진수로 비교하라

 

수열 [1,0,0,2,5], a = 3, b=4,c=3

 

 

뭐지?

 

인공지능 파이썬 알고리즘 공부하면서 XOR이론에 대해서는 배웠으나,

수리영역에서 적용하는 것은 처음이었다.

 

그래서 각각에 대해 정리해보았다.

 

1. AND ( 논리곱 )

모든 입력값이 1일 때만 ->  1출력!

 

10010 AND 11010  =   10010

 

2. OR ( 논리합 )

하나 이상의 입력값 1일 때 -> 1 출력

 

11001  OR  01101 = 11101

 

3. XOR

두 값이 다르면 1, 같으면 0 출력

 

10110 XOR 10101 = 00011

 

 

 

만약 이진수 자릿수가 다르면..?

1001  XOR  0 = 1001

 

이렇게 자릿수가 겹치지 않는 부분 100을 그대로 써주고

나머지 겹치는 자릿수인 첫째자릿수(1)만 연산반영하여 써준다. 

 

 

 

문제 해결 )

문제 : 수열 [1,0,0,2,5], a = 3, b=4,c=3

 

1. [a, b] = [ 3, 4] 이니, 0과 2부분만 XOR연산하면 된다.

2. 이진수로 바꾸고 c = 3과 연산한다.

 

0,3,4를 각각 이진수로 표현하면 -> 0, 10, 11

따라서,

 

0 XOR 11 = 11  -> 3

10 XOR 11 = 01  -> 1

 

따라서 답은 0대신 3대입, 2대신 1대입하여

[ 1,0,3,1,5 ] 가 된다.