바위타는 두루미

문제 어던 아이가 n개의 계단을 오른다. 한 번에 1계단 오르기도 하고 2계단이나 3계단을 오르기도 한다. 계단을 오르는 방법이 몇가지가 있는지 계산하는 프로그램을 구현하라. 접근법 n번째 계단을 딛기 바로 직전에 마지막에 딛는 계단은 3계단전, 2계단전, 1계단전에 있었을 것이다. 따라서, n개의 계단을 오르는 모든 경로를 생각해 본다면 1계단, 2계단 3계단 전까지의 경로를 단순히 더해주면 될 것이다. 무식하게 재귀로 구현할 수 있겠지만 반복적으로 호출되는 함수가 많아서 비효율적일 것이다. 따라서 메모이제이션을 통해 좀 더 효율적으로 해결 할 수 있다. def Solution(n): memo = [-1]* (n+1) return countWay(n, memo) def countWay(n, memo):..

퍼즐 혹은 수수께끼라고 불리는 문제들은 정책적으로 이런 종류의 문제를 면접에 출제하는 것을 금지하고 있지만, 이런 문제를 받게 될 가능성이 있다. 왜냐하면 수수께끼라는 것의 정의 자체가 모호하기 때문이다. 퍼즐 혹은 수수께기 문제의 좋은 점 중 하나는 꽤나 그럴싸하게 공정하다는 것이다. 대체로 문제로 말장난을 하지 않고 거의 대부분 논리적으로 추론이 가능하기 때문이다. 여기서는 이러한 문제들을 푸는데 기본적인 방법들과 반드시 알아야 하는 지식에 대해서 알아볼 것이다. -소수 소수판별 가장 단순한 방법 : 1 부터 n-1까지 돌면서 나누어지는 경우가 있는지 확인한다. 개선된 방법 : 1부터 n의 제곱근까지만 돌면서 나누어 지는 경우가 있는지 확인한다. import math def getPrime(n): i..

문제 흑백 모니터 화면은 하나의 바이트 배열에 저장되는데, 인접한 픽셀 여덟 개를 한 바이트에 묶어서 저장한다. 화면의 폭은 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 ,..