바위타는 두루미

문제 흑백 모니터 화면은 하나의 바이트 배열에 저장되는데, 인접한 픽셀 여덟 개를 한 바이트에 묶어서 저장한다. 화면의 폭은 w이며 , w는 8로 나누어 떨어진다. (따라서 어떤 바이트도 두 행에 걸치지 않는다) 물론, 화면 높이는 배열 길이와 화면 폭을 통해 유도해 낼 수 있다. 이때 (x1,y)에서 (x2,y)까지 수평선을 그려주는 함수를 작성하라. 메서드 용법은 다음과 같다. drawLine( byte[] screen, int width, int x1, int x2, int y) 접근법 정말 간단히 생각하면 x1에서 x2까지 for문을 돌면서 일일히 비트를 바꾸어 주어도 되지만, 전혀 효율적이지 못하다. 따라서 x1과 x2가 멀리 떨어져 있을 경우 그 사이 모든비트가 1인 바이트들이 있다는 것을 안..

문제 명령어를 가능한 적게 사용하면서 주어진 정수의 짝 수 번째 비트의 값과 홀수 번째 비트의 값을 바꾸는 프로그램을 작성하라 (예: 0번째 비트와 1번째 비트를 바꾸고, 2번째 비트와 3번째 비트를 바꾸는 식) 해결법 이 문제를 풀때에도 다른 방향에서 생각해 볼 필요가 있다. 개별 비트 쌍 단위로 연산해 나가는 것은 어려울 수 있고 , 그다지 효율적이지 못한 것 같다. 따라서 홀수번째 비트를 먼저 살펴보고, 그다음 짝수번째 비트를 살펴보는 방식으로 진행해보자 . 홀수번째 비트만 1씩 쉬프트 하는 것이 가능할까? 모든 홀수 비트를 10101010( OxAA)로 마스킹 한다음에 , 오른쪽으로 1만큼 쉬프트해서 짝수번째 자리에 두면 된다. 짝수비트도 마찬가지로 처리하여 마지막에 두 비트를 합쳐주면 된다. d..

문제 정수 A와 정수 B를 2진수로 표현했을 때, A를 B로 바꾸기 위해 뒤집어야 하는 비트의 개수를 구하는 함수를 작성하라 입력 : 29(혹은 11101) , 15( 혹은 01111) 출력 : 2 접근법 두 수의 각각의 비트중에서 다른 비트를 찾아내는 문제이기 때문에 XOR연산을 이용하면 매우 간단하게 풀린다. def bitSwapRequired(a, b): count = 0 c = a^b while c != 0 : count += c & 1 c >>=1 return count 하지만 최하위 비트를 비교해가면서 한칸씩 쉬프트 하는 방법 대신 더 나은 방식을 찾아보자 c & (c-1)을 하면 최하위 비트부터 차례대로 1을 없애 나갈 수 있다. def bitSwapRequired(a,b): count =0..

문제 다음 코드가 하는 일을 설명하여라 ( n & (n-1)) ==0 접근법 이 문제는 거꾸로 접근해가면서 해결할 수 있다. 1. 우선 , A & B==0이 무엇을 의미하는가? - A와 B에서 1비트의 위치가 같은 곳은 없다는 것을 의미한다. 2. n-1은 어떻게 생겼을까? 1011000 - 1 = 1010111 이 된다. 이말은 즉, 가장 오른쪽의 연속된 0들은 모두 1로 변하고 첫번째 1비트가 0으로 바뀐형태를 취한다. 즉 n = abced1000 이면 n-1은 abcde0111 이고 n & (n-1) ==0 가 되려면 abcde는 모두 0이 되어야 하므로 n은 2의 거듭제곱 꼴이여야 저 코드가 참일 것이다. 따라서 n이 2의 거듭제곱꼴인지 확인하는 코드이다.

문제 양의 정수가 하나 주어졌다. 이 숫자를 2진수로 표기했을때 1비트의 개수가 같은 숫자중에서 주어진 수보다 크지만 가장 작은 수와, 작지만 가장 큰 수를 구하여라 . 해결법 이 문제는 두가지 방식으로 풀 수 있다. 원리는 같지만 비트조작으로 하는지, 수학적으로 해결하는지의 차이이다. 우선 비트조작으로 해결하는 것을 살펴보자 - 비트조작으로 다음수 구하기 주어진 수보다 크지만 가장 작은수는 1의 갯수가 같은 다음 수를 의미할 것이다. 그러기 위해서는 0수열로 끝나는 수열이 아닌것 ( 다음에 1수열이 나오는 수열) 중에서 맨 오른쪽 0비트를 1로 뒤집고 , 뒤집은 수 보다 오른쪽에 있는 0과 1을 재정렬해서 0은 전부 왼쪽에 1은 전부 오른쪽에 오도록 하면 가장 작은 수가 될 것이다. 1101100111..

문제 어떤 정수가 주어졌을때 여러분은 이 정수의 비트 하나에 0에서 1로 바꿀 수 있다. 이때 1이 연속으로 나올 수 있는 가장 긴 길이를 구하는 코드를 작성하라. 해결법 1. 연속된 0수열과 1수열의 길이를 표현하는 배열로 바꿔서 생각해보기 11011101111을 오른쪽에서 왼쪽으로 읽으면 [0(0),4(1),1(0),3(1),1(0),2(1)]로 구성될 것이고 이 배열을 읽으면서 0수열이 1인 경우 인접한 1수열을 합치는 경우를 따져 보면 된다. INT_SIZE = 32 def getSequences(n): seq =[] searchingfor = 0 counter = 0 for i in range(INT_SIZE): if n & 1 != searchingfor : seq.append(counter)..

문제 0.72와 같이 0과 1 사이의 실수가 double 타입으로 주어졌을때 ,그 값을 2진수 형태로 출력하는 코드를 작성하라. 길이가 32이하인 문자열로 2진수로 정확히 표현할 수 없다면 ERROR를 출력하라 해결법 정수가 아닌 수를 이진수로 표현한다면 0.101(2)처럼 될 것이다. 소숫점 아래부분을 출력하기 위해서는 2를 곱해서 2n이 1보다 크거나 같은지를 확인하는 방법이 있다. 2*n이 1보다 크다는것은 소숫점 바로 다음수가 1이라는 뜻이고 사실 2를 곱한다는 것은 왼쪽으로 쉬프트 하는 것을 의미한다. def printBinary(num): if (num >=1 || num 0 if len(ans)>=32: return "ERROR" r = num *2 if r >=1 : ans +="1" nu..

문제 두 개의 32비트 수 N과 M이 주어지고, 비트 위치 i와 j가 주어졌을 때, M을 N에 삽입하는 메서들을 구현하라. M은 N의 j번째 비트에서 시작하여 i번째 비트에서 끝난다. j번째 비트에서 i번째 비트까지에는 M을 담기에 충분한 공간이 있다고 가정한다. 다시말해 M = 10011라면, j와 i사이에 적어도 다섯 비트가 있다고 가정해도 된다는 것이다. j = 3이고 i = 2인 경우처럼 M을 삽입할 수 없는 상황은 발생하지 않는다. 접근법 3가지 단계를 거쳐서 문제를 해결할 수 있을 것이다. 1. N의 i에서 j까지의 비트를 0으로 만든다. 2. M을 쉬프트해서 j부터 i번 비트자리에 오도록 만든다. 3. M 과 N을 합한다. def updateBits(int n , int m , int j ,..

- 몇가지 비트 트릭 1. 0110+ 0110 은 0110을 왼쪽으로 한번 쉬프트 한 것과 같다. - 0110 *2 와 같기 때문에 2. 0100 * 0011은 0011을 왼쪽으로 두번 쉬프트 한 것과 같다. - 0100은 4이기 때문에 0011*4와 동일 3. 1101 ^ (~1101) 은 모든 비트가 1이 된다. - XOR연산은 두 비트가 다를때 1을 가지는데 NOT연산으로 모든 비트를 반전 시켰으므로 각 비트들은 서로 다르다. 4. 1011 & (~0

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다. 입출력 예 money return [1, 2, 3, 1] 4 def getMax(money): isget = False first = 0 second = 0 cur_num = 0 for m in money:..