[Python] 알고리즘 - 4

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

[다음 입사문제] 최근접쌍

• 1차원의 점들이 주어졌을 때, 그 중 가장 거리가 짧은 것의 쌍을 출력하는 함수를 작성하시오
• 예를들어 S=[13, 20, 8, 4, 1, 17, 3] 이 주어졌다면, 결과값은 (3, 4)가 될 것이다.
• Hint) 정렬 후 인접쌍 거리 체크

def func(lst:list) -> list:
  tmp = {}
  lst.sort()
  for i in range(len(lst) - 1):
    tmp[lst[i], lst[i+1]] = lst[i+1] - lst[i]
  return list(min(tmp, key=tmp.get))

print(func([13,20,8,4,1,17,3]))

[아마존 면접문제] 정렬

• 다음과 같은 형태의 배열을
• [a1,a2,a3...,an,b1,b2...bn] 다음과 같은 형태로 바꾸시오
• [a1,b1,a2,b2.....an,bn]

def reverse_lst(lst:list) -> list:
  res = []
  for i in range(0, len(lst)//2):
    res.append(lst[i])
    res.append(lst[len(lst)-(len(lst)//2-i)])
  return res

print(reverse_lst(['a1', 'a2', 'a3', 'an', 'b1','b2','b3', 'bn']))

(구글 면접문제) Special Sort

• n개의 정수를 가진 배열이 있다. 이 배열은 양의정수와 음의 정수를 모두 가지고 있다. 이제 당신은 이 배열을 좀 특별한 방법으로 정렬해야 한다.
• 정렬이 되고 난 후, 음의 정수는 앞쪽에 양의정수는 뒷쪽에 있어야 한다. 또한 양의정수와 음의정수의 순서에는 변함이 없어야 한다.
• 예. -1 1 3 -2 2 ans: -1 -2 1 3 2.

def func(lst:list) -> list:
  res = []
  for i in range(len(lst)):
    if lst[i] < 0:
      res.append(lst[i])

  for j in range(len(lst)):
    if lst[j] > 0:
      res.append(lst[j])

  return res

print(func([-1, 1, 3, -2, 2]))

Lotto Simulation

• 1~5사이의 정수 3개를 중복없이 입력 받아, 자동 발생시킨 로또 번호와 비교 (실행예) 로또 번호 입력 : 1 2 3
• 자동 발생 번호 : 1 3 5

import random

def lotto() -> str:
  while True:
    a = random.randint(1, 5)
    b = random.randint(1, 5)
    c = random.randint(1, 5)
    if a != b and a != c and b != c:
      break
  return ' '.join(map(str, (a, b, c)))

user1, user2, user3 = map(int, input('로또 번호 입력 : ').split())

print("자동 발생 번호 :", lotto())

• (추가실습) 로또 결과를 출력하시오 (실행예) 결과 : 숫자 2개 일치

inval = True
import random

def lotto() -> str:
  while True:
    a = random.randint(1, 5)
    b = random.randint(1, 5)
    c = random.randint(1, 5)
    if a != b and a != c and b != c:
      break
  return a,b,c

def chk(user1:int, user2:int, user3:int) -> int:
  cnt = 0
  lst = list(lotto())
  user_lst = [user1, user2, user3]
  lst.sort(); user_lst.sort()
  for i in range(3):
    if lst[i] == user_lst[i]:
      cnt += 1
  return cnt

while (inval == True):
  user1, user2, user3 = map(int, input('로또 번호 입력 : ').split())
  if user1 > 5 or user2 > 5 or user3 > 5 or user1 < 1 or user2 < 1 or user3 < 1:
    print("1~5사이의 정수로 입력해주세요")
  else:
    inval = False
    break


if(inval == False):
  print("숫자",chk(user1, user2, user3),"개 일치")

빈도수 체크

• 크기 n인 배열을 [1~100) 난수로 초기화 Bin 크기 입력 각 Bin에 포함된 숫자의 개수 출력
• 실행 예) 배열의 크기 입력 : 100 Bin 크기 입력 : 3 각 Bin에 포함된 숫자의 개수 = [33, 37, 30]

import random

def rand(n:int) -> int:
  lst = [random.randint(1,100) for i in range(n)]
  return lst

def eq(n:int, bin:int) -> list:
  res = []
  rand_lst = rand(n)
  for i in rand_lst:
    if str(bin) in str(i):
      res.append(i)
  return res

n = int(input('배열의 크기 입력 : '))
bin = int(input("Bin 크기 입력 : "))
lst = eq(n, bin)
print("각 Bin에 포함된 숫자의 개수 =", lst)

에라토스테네스의 체(소수 출력)

• 2부터 시작해 자연수를 차례로 쓴 다음 합성수를 제거
• 배열 활용
  • 인덱스를 자연수라 가정, 1로 모두 초기화
    • 인덱스 0, 1의 원소는 활용 안함
  • 자연수 i(인덱스)가 합성수이면 0으로 지움
• 메소드 작성
  • delete(lst : list, i : int)
    • 리스트 lst에서 정수 i의 배수를 모두 지움

def composite(n:int) -> int:
  res = []
  for i in range(1, n+1):
    if n % i == 0:
      res.append(i)

  if len(res) >= 3:
    return 0
  else:
    return 1

def delete(dic, i:int):
  for j in range(len(dic)):
    if dic[j] % i == 0:
      del dic[j]
  return dic


dic = {}
for i in range(0, 20):
  dic[i] = composite(i)

print(delete(dic, 2))

파스칼삼각형

• 지수 n을 입력받아 이항계수를 출력하는 프로그램 작성 (실행예)
  • 지수를 입력 : 4
  • 이항계수 : 1 4 6 4 1

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

def func(n, k):
    return factorial(n) // (factorial(k) * factorial(n - k))

n = int(input('지수를 입력 : : '))
res = [func(n, k) for k in range(n+1)]
print("이항계수 : ",res)

<문제> 시각: 문제 설명

• 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 입니다.
  • 00시 00분 03초
  • 00시 13분 30초
• 세어야 하는 시각
• 반면에 다음은 3이 하나도 포함되어 있지 않으므로 입니다.
  • 00시 02분 55초
  • 01시 27분 45초
• 세면 안 되는 시각

→ 구현 : 시뮬레이션과 완전 탐색

# 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중 3이 하나라도 포함되는 모든
# 경우의 수를 구하는 프로그램
def time(n:int) -> int:
  res = 0
  for hour in range(0, n+1):
    for minute in range(0, 60):
      for second in range(0, 60):
        if '3' in str(hour) + str(minute) + str(second):
          res += 1

  return res

n = int(input("입력 : "))
print("3이 포함된 모든 경우의 수 : ",time(n))