[Python] 알고리즘 - 2

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

Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

⇒

---

3과 5의 배수

만약 우리가 3 또는 5의 배수인 10 이하의 모든 자연수를 나열한다면, 우리는 3, 5, 6, 9를 얻게 됩니다. 이 배수들의 합은 23입니다.

1000 아래의 3이나 5의 모든 배수의 합을 구하세요.

def func():
  sum = 0
  for i in range(1000):
    if i % 3 == 0 or i % 5 == 0:
      sum += i
  return sum

print(func())

---

*반복문 활용 : ,  /, % 연산자 대체

두 정수 a, b(≠0)를 입력 받아 *, /, %연산자를 사용하지 말고, 두 정수의 곱, 몫, 나머지를 출력하시오 (실행예) 두 정수 입력 : 10 3 10 * 3 = 30 10 / 3 = 3 10 % 3 = 1

(Hint) 두정수의 곱 : 더하기 연산 반복(10*3⇒ 10+10+10) 두정수 몫, 나머지 : 빼기 연산 반복(10/3⇒10-3-3-3=1)

def mu(a:int, b:int) -> int:
  mul = 0 # 곱하기
  div_tmp = a # 나누기
  div_res = 0 # 나누기 답
  rem = 0 # 나머지
  for i in range(1,b+1):
    if (i == 1):
      mul = a
    else :
      mul = mul + a
    if (div_tmp-b) > 0:
      div_tmp = div_tmp - b
      div_res += 1

  print(a, "*" , b , "=" ,mul)
  print(a, "/" , b , "=" ,div_res)
  print(a, "%" , b , "=" ,div_tmp)


a, b = (map(int, input("두 정수 입력 : ").split()))
mu(a, b)

---

원주율 출력

라이프니치 공식을 활용하여 원주율 출력

def func():
  pi = 4
  switch = True

  for i in range(3, 10001, 2):
    if switch: # True면 -
      pi = pi - ( 4 * (1 / i))
      switch = False
    else: # False면 +
      pi = pi + ( 4 * (1 / i))
      switch = True

  return pi

print(func())

---

오일러 공식을 활용하여 원주율 출력

import math

def func():
  sum = 0
  for i in range(1, 10000):
    sum += (1/i**2)

  pi = math.sqrt(6 * sum) # 루트 6
  return pi

print(func())

---

몬테카를로법 : 원주율 출력

임의의 실수 x, y (0<=x, y<=1)를 N번 발생시켜, ¼원 내에 포함된 점의 횟수 E를 계산하여 원주율을 출력

(Hint) 난수발생 함수 활용

import random

def func():
  cnt = 0
  pi = 0
  for i in range(1000000):
    x = -(random.random())
    y = random.random()

    if (x*x + y*y) <= 1: # 1안에 들어가는 지 확인 E 값 증감
      cnt += 1
    pi = (4 * cnt) / 1000000
  return pi

print(func())

---

이중 루프를 이용하여 별표 출력

이중루프를 사용해 아래와 같은 별표를 출력 하시오

n = 10
for i in range(2, n+1, 2):
    print(' ' * ((n-i)//2) + '*' * i)
for i in range(n, 0, -2):
    print(' ' * ((n-i)//2) + '*' * i)

---

1이 될 때까지 : 문제

• 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.

1.N에서 1을 뺍니다.

2.N을 K로 나눕니다.

• 예를 들어 N이 17, K가 4라고 가정합시다. 이때 1번의 과정을 한 번 수행하면 N은 16이 됩니다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 됩니다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됩니다. 이는 N을 1로 만드는 최소 횟수입니다.
• N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하세요.

힌트 (그리디 알고리즘)

• 주어진 N에 대하여 최대한 많이 나누기를 수행하면 됩니다.
• N의 값을 줄일 때 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있습니다.
• 예를 들어 N = 25, K = 3일 때는 다음과 같습니다.

N, K = map(int, input("두 정수 입력 :").split())

cnt = 0

while(N != 1):
  if(N % K == 0):
    N = N / K
  else:
    N = N - 1
  cnt += 1

print(cnt)