[백준/기본기 다지기(1)] 약수 / 이진수 / 지능형 기차2

약수 구하기

• 두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하기
  • 약수를 set으로 저장함
  • 약수 개수 < k 이면 -> 0 출력, 아니면 정렬후 k-1번째 수 가져옴
  • 약수는 2~n의 제곱근까지만 for 루프를 돌며 나눠본다. 기본으로 1과 n(자기자신)으로 초기화시켜줌
  • set을 sorted에 넣어주면 → 리스트 [] 로 타입이 변화됨

  n, k = map(int, input().split())
  
  a = {1, n}
  
  if n > 1:
      for i in range(2, int(n**0.5) + 1):
          if n % i == 0:
              a |= {i, n // i}
  
  # 약수 개수 < k 이면 -> 0 출력, 아니면 정렬후 k-1번째 수 가져옴
  print(0 if len(a) < k else sorted(a)[k-1])
  

---

이진수 

• 양의 정수 n이 주어졌을 때, 이를 이진수로 나타냈을 때 1의 위치를 모두 찾는 프로그램을 작성하시오. 최하위 비트(least significant bit, lsb)의 위치는 0이다.
  • [재귀 이용해서 10진수 -> 2진수 변환 후 LSB부터 1의 위치 세기]
  • n==0일 경우 대비 x: n이 0이 아닌 이상, 논리적으로 num은 0이 될 수가 없다
  • 재귀 종료 : num == 1이 됐을 떄

  t = int(input())
  
  def getBinaryReverse(num):
  
      if num == 1:
          return '1'
  
      # 2로 나눈 나머지에 잇기 = LSB부터 세어야해서 : 순서 뒤집음!
      return str(num % 2) + getBinaryReverse(num // 2)
      #return getBinaryReverse(num // 2) + str(num % 2) -> 이게 맞는 2진수 순서
  
  case = []
  for _ in range(t):
      case.append(int(input()))
  
  for n in case:
      b = getBinaryReverse(n)
  
      for idx, value in enumerate(b):
          if value == '1':
              print(idx, end = ' ')
      print()
  

  • 또다른 풀이! = 2로 나눈 나머지가 1일 때만 print 바로바로 해버리는 방식
    • 코드길이는 많이 줄었지만, 시간은 4ms더 걸린다 뜸! 근데 공부하기 좋은 코드

  # [재귀 이용해서 10진수 -> 2진수 변환 후 LSB부터 1의 위치 세기]
  
  for _ in range(int(input())):
      n, idx = int(input()), 0
  
      # n이 0이면 탈출
      while n > 0:
          if n % 2 == 1:
              print(idx, end = " ")
  
          n //= 2
          idx += 1
      print()
  

---

지능형 기차 2 

• 10개의 역에 대해 기차에서 내린 사람 수와 탄 사람 수가 주어졌을 때, 기차에 사람이 가장 많을 때의 사람 수를 계산하는 프로그램을 작성하시오.
  • 최대 합보다 클 경우 교체하는 식으로 루프를 돌게 했는데 → 아래 두번쨰 풀이처럼 그냥 리스트에 다 때려넣고 max 함수 쓰는게 더 나음! 시간 차이는 없고, 코드길이는 줄었으니

  # [누적된 탄 사람] = [누적된 탄 사람] - 현재역의 내린 사람 수 + 현재역에 탄 사람 수
  total = 0 #누적
  max_total = 0
  
  for _ in range(range):
      a, b = map(int, input().split())
  
      now = total - a + b
      
      max_total = now if now > max_total else max_total
      total = now
  
  print(max_total)
  

• max함수 쓴거!

s = [0]

for i in range(10):
    a, b = map(int, input().split())

    s.append(s[i] - a + b)

print(max(s)