[Python] 알고리즘 - 3

2024. 1. 17. 11:24· 프로그래밍/알고리즘
목차
  1. 개인 공부 목적 - 참고만 하시는걸 추천드립니다.
  2. 오일러 수(e)
  3. 완전수 출력
  4. 3n+1 Problem
  5. [구글 입사 문제] 숫자 개수
  6. [넥슨 입사문제] 셀프 넘버
  7. 10진수를 2진수로 변환하기
  8. <문제> 곱하기 혹은 더하기: 문제 설명
반응형

 

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

오일러 수(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))

Untitled.png

완전수 출력

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()

Untitled.png

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())

Untitled.png

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

  • 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())

Untitled.png

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

  • 어떤 자연수 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())

Untitled.pngUntitled.png

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

Untitled.png

  • 위 그림을 참조하여 라이브러리를 사용하지 말고 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))

Untitled.png

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

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

Untitled.png

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")

Untitled.png

반응형
  1. 개인 공부 목적 - 참고만 하시는걸 추천드립니다.
  2. 오일러 수(e)
  3. 완전수 출력
  4. 3n+1 Problem
  5. [구글 입사 문제] 숫자 개수
  6. [넥슨 입사문제] 셀프 넘버
  7. 10진수를 2진수로 변환하기
  8. <문제> 곱하기 혹은 더하기: 문제 설명
'프로그래밍/알고리즘' 카테고리의 다른 글
  • [Python] 알고리즘 - 4
  • [Python] 알고리즘 - 2
  • [Python] 알고리즘 - 1
Future0_
Future0_
rm -rf /
Future0_
Luna Developer Blog
Future0_
전체
오늘
어제
  • 분류 전체보기 (112)
    • 프로그래밍 (4)
      • 알고리즘 (4)
    • 보안 (14)
      • Dreamhack (4)
      • Hackthebox (1)
      • Webhacking (9)
    • 프로젝트 (4)
    • 공부 (80)
      • Database (2)
      • Python (11)
      • System (4)
      • Java (13)
      • JSP (13)
      • Spring (11)
      • Kotlin (16)
      • 자료구조 (10)
      • 기계학습 (0)
    • Docker (4)
    • Github (2)
    • Tip (1)
    • 잡담 (2)

블로그 메뉴

  • 홈
  • 태그

공지사항

인기 글

태그

  • Java
  • 디버깅키해시
  • Computer science
  • docker
  • Android Studio
  • 자바빈즈
  • 프로그래밍
  • native app
  • React
  • 상속
  • api 통신
  • dreamhack
  • shared preference
  • android studio 삭제
  • ViewModel
  • 알고리즘
  • Database
  • cs
  • SpringBoot
  • 컴퓨터
  • 자료구조
  • Python
  • 코틀린기본문법
  • 키 해시
  • spring
  • 1.9.22
  • jsp
  • Kotlin
  • webhacking
  • 보안

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
Future0_
[Python] 알고리즘 - 3
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.