[SW Expert Academy] Computational Thinking 논리와 증명 / 수와 표현 문제풀이 (4)

Sw Expert Academy : Computational Thinking - 논리와 증명, 수와 표현 (링크)

문제 풀이

문제 1 : 2진수 표현에서 $\log{n}$ 비트로 표현할 수 있는 숫자 범위는?

• k개의 비트를 사용하면 0 ~ $2^k-1$까지 표현할 수 있다
• $log{n}$ 비트를 사용하면 0 ~ $2^{log{n}}-1$까지 표현할 수 있다

문제 2 : 스무고개가 이상적으로 진행된다고 할 때, 맞출 수 있는 답의 종류는 몇 가지인가?

• 문제의 답이 o, x 중 하나 이고 이상적으로는 총 20문제가 있으므로 답의 종류는 $2^{20}$가지이다

문제 3 : n이 충분히 큰 값일 때 다음 중 어느 값이 더 큰가? 각 쌍에 대해 비교하고 그 이유를 작성하시오

① $2n$ : $n^2$

• n이 충분히 크다면 상승률이 높은 $n^2$이 더 크다

② $2^{\frac{n}{2}}$ : $\sqrt{3^n}$

• 지수가 n/2로 양쪽이 똑같으므로 밑이 높은 $\sqrt{3^n}$가 더 크다

③ $2^{nlogn}$ : $n!$

• $2^{nlogn}$은 $2^{log{n^n}}$으로 표현할 수 있고 log의 밑이 2라면 $n^n$이다
• n을 n번 곱한것이 n!보다 크기 때문에 $2^{nlogn}$가 더 크다

④ $log2^{2n}$ : $n\sqrt{n}$

• 왼쪽은 2n으로 간소화 할 수 있고 양 변을 나눴을 때 좌변은 상수가 되고 우변은 $\sqrt{n}이 된다
• 따라서 $n\sqrt{n}$가 더 크다

문제 4 : $x=log{a}(yz)$일 때 x를 2가 밑인 로그들로 표현하시오. 단 로그함수의 인자는 모두 문자 하나여야 한다

• $log{a}(yz)=loga(y)+loga(z)$
• $= log2(y)/log2(a) + log2(z)/log2(a)$
• $= (log2(y)+log2(z))/log2(a)$

문제 5 : 다음 함수들의 역함수를 구하시오

① $f(x)=\log(x-3)-5$

• $y = \log(x-3)-5$
• $y+5 = \log(x-3)$
• $2^{y+5} = x-3$
• $2^{y+5}+3 = x$
• 따라서 $f^{-1}(x)=2^{x+5}+3$

② $f(x)=3\log(x+3)+1$

• $(y-1)/3=\log(x+3)$
• $2^{(y-1)/3}-3 = x$
• 따라서 $f^{-1}(x)=2^{(x-1)/3}-3$

③ $f(x)=2*3^x-1$

• $(y+1)/2 = 3^x$
• $log3((y+1)/2) = x$
• 따라서 $f^{-1}(x)=log3((x+1)/2)$