01. 다음 큰 숫자
어떤 수 N(1≤N≤1,000,000) 이 주어졌을 때, N의 다음 큰 숫자는 다음과 같습니다.
- N의 다음 큰 숫자는 N을 2진수로 바꾸었을 때의 1의 개수와 같은 개수로 이루어진 수입니다.
- 1번째 조건을 만족하는 숫자들 중 N보다 큰 수 중에서 가장 작은 숫자를 찾아야 합니다.
예를 들어, 78을 2진수로 바꾸면
1001110
이며, 78의 다음 큰 숫자는 83으로 2진수는1010011
입니다. N이 주어질 때, N의 다음 큰 숫자를 찾는 nextBigNumber 함수를 완성하세요.
def nextBigNumber(n):
c = bin(n).count("1")
for nn in range(n+1, 1000000+1):
if c == bin(nn).count("1"):
return nn
return "out of range"
- 입력된 숫자 n을 2진수로 변환 후, 1의 갯수를 모두 카운트한다.
- 그리고 입력된 숫자 n의 다음 부분부터 숫자를 하나씩 증가시키면서 2진수로 변환한 다음 1의 갯수를 카운트한다!
02. 멀리 뛰기
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 출력하는 jumpCase 함수를 완성하세요. 예를 들어 4가 입력된다면, 5를 반환해 주면 됩니다.
def jumpCase(num):
if num == 1:
return 1
if num == 2:
return 2
return jumpCase(num-1)+jumpCase(num-2)
-
이 문제의 경우 효진이는 1칸 혹은 2칸만 점프를 할 수 있다.
-
이럴 경우 1칸을 가는 방법은 1가지, 2칸을 가는 방법은
2
칸을 한번에 가기,1+1
로 가는 방법 2가지이다. \(\begin{align} f(1) & = 1 \\ f(2) & = f(1) + 1 \\ f(3) & = f(2) + f(1) \\ f(4) & = f(3) + f(2) \\ &\ \ \ \ \ \ \ \ \ \vdots \\ f(n) & = \sum_{x=1}^{n-1}f(x) \end{align}\) -
여기서 우리가 확실히 알수 있는 것은 n = 1,2일때의 값이다.
-
만약에 n에 4가 들어오면
f(4) = f(3) + f(2)이고
f(3) = f(2) + f(1)이고
f(2) = f(1) + 1로 모든 합을 f(1)과 f(2)의 조합으로 구해낼수 있다. -
하지만 이럴 경우 분할되는 조각의 수 만큼 가장 밑바닥 즉 f(1)과 f(2)의 값들을 중복적으로 계산하게 된다1.
-
위의 코드는 간단한 메모이제이션으로 바꿀 수 있고, 그것을 또 다시 하나의 반복문의 형태로 변형시킬수 있다.
def jumpCase(n): a=1; b=2 for x in range(2, n+1): a , b = b, a+b return a
03. N개의 최소공배수
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. nlcm 함수를 통해 n개의 숫자가 입력되었을 때, 최소공배수를 반환해 주세요. 예를들어 [2,6,8,14] 가 입력된다면 168을 반환해 주면 됩니다.
def gcd(a,b):
exp = 0;r=0
while ((a|b)&1 == 0):
exp += 1
a >>= 1
b >>= 1
while(a!=0 and b!=0):
while((a&1)==0):
a>>=1
while((b&1)==0):
b>>=1
if (a>b):
a = a-b
else:
b = b-a
if (a!=0):
r=a
else:
r=b
return r<<exp
def nlcm(num):
# lcm = num[0]*num[1]//gcd(num[0], num[1])
for n in range(1, len(num)):
lcm = num[n-1]* num[n] // gcd(num[n-1], num[n])
return lcm
- 앞에서 했던 최소공배수 문제를 풀었다면 금방 풀 수 있는 문제이다.
- 두 숫자의 최소공배수를 구하고 구해진 최소공배수와 다음 숫자와의 최소공배수를 다시 구한다!
4. 야근 지수
야근 지수 회사원인 수민이는 많은 일이 쌓여 있습니다. 수민이는 야근을 최소화하기 위해 남은 일의 작업량을 숫자로 메기고, 일에 대한 야근 지수를 줄이기로 결정했습니다. 야근 지수는 남은 일의 작업량을 제곱하여 더한 값을 의미합니다. 수민이는 1시간 동안 남은 일 중 하나를 골라 작업량 1만큼 처리할 수 있습니다. 수민이의 퇴근까지 남은 N 시간과 각 일에 대한 작업량이 있을 때, noOvertime 함수를 제작하여 수민이의 야근 지수를 최소화 한 결과를 출력해 주세요. 예를 들어, N=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 일을 한 결과는 [2, 2, 2]가 되고 야근 지수는 22 + 22 + 22 = 12가 되어 12를 반환해 줍니다.
def noOvertime(n, works):
for n in range(n):
works[works.index(max(works))] -= 1
return sum([x**2 for x in works])
- 결과 코드자체는 간단하지만 문제에 대해서 수학적으로 접근하는 생각이 약간은 필요하다.
- 남은 시간의 제곱의 합을 구하는 문제이다. 이 제곱의 합이 최소가 되기 위해서는 어느 하나를 한꺼번에 줄이기보다는 전체적인 숫자의 크기를 줄이는 식의 접근이 필요하다.
- 그러므로 우선 입력된 work에서 최대값에서 1을 빼주는 것을 남은 시간수 만큼 반복해준다!
5.시저 암호
어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다.
A를 3만큼 밀면 D가 되고 z를 1만큼 밀면 a가 됩니다. 공백은 수정하지 않습니다.
보낼 문자열 s와 얼마나 밀지 알려주는 n을 입력받아 암호문을 만드는 ceasar 함수를 완성해 보세요.
- “a B z”,4를 입력받았다면 “e F d”를 리턴합니다.
def caesar(s, n):
result = ""
for ss in s:
if ss.isalpha():
if ss.islower():
ss = (((ord(ss) - ord("a")) + n) % 26) + ord("a")
elif ss.isupper():
ss = (((ord(ss) - ord("A")) + n) % 26) + ord("A")
ss = chr(ss)
result += ss
return result
- 이 문제의 경우도 무언가 알고리즘을 적용했다기보다는 단순히 문제에 설명되어 있는 작업을 순차적으로 진행하였다.
- 각 알파벳에서 입력된 숫자만큼 이동을 시키고, 알파벳의 범위(26개)를 넘어 갈 경우 다시 처음부터(a)에서 부터 시작하도록
%
를 이용해준다!
-
이는 재귀적으로 구한 함수의 구조적인 문제이다. ↩