[Python] 알고리즘 - 3

 

개인 공부 목적 - 참고만 하시는걸 추천드립니다.

오일러 수(e)

아래의 수식을 계산해서 오일러 수(e)를 출력하시오. (수식) e = 1 + 1/1! + 1/2! + 1/3! + …

(출력예) e=2.718..

(Hint)

• fact(n:int)->int 함수를 만들어 사용

def fact(n:int) -> int: # 팩토리얼 구하는 함수
  res = 1
  for i in range(n, 0, -1):
    res *= i
  return res

def oil(n:int) -> float: # 오일러 수 구하는 함수
  res = 1
  for i in range(1, n+1):
    res += 1/fact(i)
  return res

print(oil(100))

완전수 출력

10000이하의 완전수를 모두 출력하시오. 완전수 = 약수의 합이 자신과 똑같은 수 예) 6 = 1 + 2+ 3

• Hint) SumDiv(n:int)->int 함수를 만들어 사용

def sumDiv(n:int) -> int: # 해당 숫자를 제외한 약수의 합 구하는 함수
  sum = 0
  for i in range(1,n):
    if n%i == 0:
      sum += i
  return sum

def perfectNum(): # 약수의 합 == 10000이하의 숫자 판별식 함수
  for i in range(1, 10001):
    if i == sumDiv(i):
      print(i, end = " ")

perfectNum()

3n+1 Problem

• 어떤 정수 n에서 시작해, n이 짝수면 2로 나누고, 홀수면 3을 곱한 다음 1을 더한다. 이렇게 해서 새로 만들어진 숫자를 n으로 놓고, n=1 이 될때까지 같은 작업을 계속 반복한다. 예를 들어, n=22이면 다음과 같은 수열이 만들어진다.
• 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
• n이라는 값이 입력되었을때 1이 나올때까지 만들어진 수의 개수(1을 포함)를 n의 사이클 길이라고 한다. 위에 있는 수열을 예로 들면 22의 사이클 길이는 16이다.
• 900과 1000사이의 수중에서 가장 긴 사이클 길이는?

def func(n:int, count:int = 0) -> int:
  count+=1
  if n == 1:
    return count
  else:
    if n % 2 == 0:
      return func(n//2, count)
    else:
      return func(n*3+1, count)

def compare() -> int:
  lst = []
  for i in range(900, 1000):
    lst.append(func(i))
  return max(lst)

print(compare())

[구글 입사 문제] 숫자 개수

• 1부터 10,000까지 8이라는 숫자가 총 몇번 나오는가?
• 8이 포함되어 있는 숫자의 갯수를 카운팅 하는 것이 아니라 8이라는 숫자를 모두 카운팅 해야 한다. (※ 예를들어 8808은 3, 8888은 4로 카운팅 해야 함)

def num_cnt():
  count = 0
  for i in range(1, 10000):
    for j in str(i):
      if j == '8':
        count += 1

  return count

print(num_cnt())

[넥슨 입사문제] 셀프 넘버

• 어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자.
• 예를 들어 d(91) = 9 + 1 + 91 = 101 이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다.
• 어떤 숫자들은 하나 이상의 제네레이터를 가지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 셀프 넘버(self-number)라 이름 붙였다. 예를 들어 1,3,5,7,9,20,31 은 셀프 넘버 들이다.
• 1 이상이고 5000 보다 작은 모든 셀프 넘버들의 합을 구하라.

def self_num():
  num = 0
  self_lst = []
  num_lst = []
  for i in range(1, 5000):
    self_lst.append(i)
    for j in str(i):
      num += int(j)
    num += i
    num_lst.append(num)
    num = 0
  for k in range(len(num_lst)):
    if num_lst[k] in self_lst:
      self_lst.remove(num_lst[k])

  return self_lst

print(self_num())

10진수를 2진수로 변환하기

• 위 그림을 참조하여 라이브러리를 사용하지 말고 10진수를 2진수로 변환하는 프로그램을 작성하시오. 조건) tobin(n:int)->str 함수 작성
• 실행예) 입력(10진수) : 23310 2진수 : 111010011000

def tobin(n:int) -> str:
  if n == 0 or n == 1:
    return str(n)
  else:
    return tobin(n//2) + str(n%2)

print(tobin(23310))

<문제> 곱하기 혹은 더하기: 문제 설명

• 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 ‘×’ 혹은 ‘+’ 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 ×를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.
• 예를 들어 02984라는 문자열로 만들 수 있는 가장 큰 수는 ((((0 + 2) × 9) × 8) × 4) = 576입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

def greedy(n:str) -> int:
  res = int(n[0])
  for i in n[1:]:
    if int(i) < 1 or res < 1:
      res += int(i)
    else:
      res *= int(i)
  return res


greedy("02984")