개요
7주차 스터디는 수학 관련 4문제였다.
(이번 주부터 못 풀더라도 꼭 문제를 파악하게 오는 것으로 바뀌어서 4문제가 되었다.)
A번
문제 요약
어떤 수 N이 주어졌을 때, -2진수로 나타내기
설명
케이스 워크로 풀었는데, 생각해보니 -2진수는 2진수와 같은 원리로 풀 수 있었다. 그 풀이는 영문 위키피디아로 대체
내가 생각한 풀이는 아래와 같다.
1~1(1개)은 1비트, 2~5(4개)는 3비트, 6~21(16개)는 5비트
마찬가지로, -1~-2(2개)는 2비트, -3~-10(8개)는 4비트, -11~-42(32개)는 6비트
이런 식으로 정리가 가능해서, N이 주어졌을 때 log N으로 몇 비트에 들어가는 지를 구할 수 있다.
이제 저걸 반복적으로 적용해서,
- -2진수의 큰 비트부터 한 비트씩 보면서 값을 넣을 수 있으면 넣는다. 남은 값이 양수이고 내 비트가 양수라면 넣고, 남은 값이 음수이고 내 비트가 음수라면 넣는 식이다. (알맞은 1을 넣기 위한 부분)
- 반례를 해결하기 위해, 남은 값이 총 몇 비트로 표현이 가능한지 확인해서 다음 비트로 이동한다. 예를 들어 9(11001)에서 11까지 채운 후 3비트가 남았는데, 지금까지 8을 채워서 남은 값이 1이므로 1은 1비트로 표현이 가능한 것을 위 방법대로 구한다. 그러면 0을 두 번 채우면서 비트를 이동시키면 된다. (알맞은 0을 넣기 위한 부분)
뭔가 직관에 의존해서 풀어서 설명하기가 힘들다. 그리고 정해가 따로 있는데 괜히 더 어렵게 푼 것 같다.
B번
문제 요약
ARR[i+1] = A * ARR[i] + B의 형태로 표현되는 수열을 줄 때, 다음 수열 값을 구하는 문제
설명
브루트포스로도 예외적인 경우를 다 잘 고려해준다면 풀 수 있겠지만, 그렇게 풀기 싫어서 생각을 더 해 봤다.
그랬더니 초등학생 때 본 것 같은 느낌으로, 수열 -> 수열의 차이들 -> 수열의 차이들의 배율 이런 식으로 계산할 수 있다.
그런데 좀 케이스 워크를 해 줘야 하는 부분이 있어서 약간 귀찮았다.
C번
문제 요약
1과 5로만 구성된 N자리 수 중 15의 배수의 개수를 구하는 문제
설명
15 = 3 * 5라서, 3의 배수이면서 5의 배수인 수를 세 주면 된다.
5의 배수는 0이나 5로 끝나기 때문에, 이 문제의 경우에는 5로 끝나는지만 파악하면 된다.
3의 배수는 각 자릿수를 모두 더했을 때 3의 배수인지를 확인해 주면 된다.
- 1의 개수를 1~N-1으로 반복을 한다. 5의 개수는 N-(1의 개수)다.
- 15의 배수인지를 위 방법대로 파악을 한다. 아니라면 넘어간다.
- 그 중 마지막자리에 가야 하는 5 하나를 제외하고, 1과 5를 섞어서 나올 수 있는 모든 경우의 수를 구한다. (모듈러 역원을 이용해서 팩토리얼 조합으로 계산)
D번
문제 요약
높이가 모두 다른 빌딩 N개가 있을 때, 왼쪽에서 L개 오른쪽에서 R개가 보이는 경우의 수 구하기
설명
그냥 확통으로 풀 수 있을 줄 알았는데 생각보다 복잡하기도 하고, 시간을 이번주에 많이 투자를 못 해서 못 풀었다.
후기
한 문제를 못 푼게 아쉬웠고, 그리고 문제를 내가 골랐는데 생각보다 재미없는 문제도 껴 있어서 아쉬웠다.