[python/algorithm] 핵심 정리(1)

약수

• 나누어 떨어지는 수

      # n의 약수를 출력하시오
      for i in range(1, n+1):
          if n%i == 0:
              print(i)

파이썬 슬라이싱

• 리스트, 튜플, 문자열이 있을 때 범위를 지정해서 객체들을 가져오는 표기법

• 기본 형태 [시작위치, 끝위치, 스텝]

• 끝위치는 가져오지 않음, 끝 위치 앞까지

        a = [1,2,3,4,5] 
        # 1부터 3까지 가져온다. 
        a[1:3] # 2,3
  
        # 역으로 출력한다.
        a[::-1] # 5,4,3,2,1
  
        # 1부터 끝까지 가져온다.
        a[1:] # 2,3,4,5

enumerate 함수

• 리스트의 원소에 순서값을 부여해주는 함수

        a = ["one", "two", "three"]
        for idx, val in enumerate(a):
            print(idx, val)

자릿수의 합 구하기

• 문자열로 처리하여 구할 수도 있음

        def digit_sum(x):
            sum=0
            while x>0:
                sum+=x%10
                x=x//10
            return sum

파이썬 제곱근

• 10의 제곱근을 구한다.

        # 직접 계산
        a = 100 ** (1/2)
        print(a)
  
        # math.sqrt()
        import math
        a = math.sqrt(100)
        print(a)

에라토스테네스 체

• 다수의 자연수에 대하여 소수 여부를 판별할 때 사용

• 제곱근을 사용하여 더 빠르게
  https://gururuglasses.tistory.com/80
  https://daebaq27.tistory.com/106
  https://freedeveloper.tistory.com/392

        # 개선된 소수 판별 함수
        import math
  
        # 2부터 1,000까지의 모든 수에 대하여 소수 판별
        n = 1000 
        array = [True for i in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화
  
        # 에라토스테네스의 체 알고리즘 
        for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
            if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
                # i를 제외한 i의 모든 배수를 지우기
                j = 2 
                while i * j <= n:
                    array[i * j] = False
                    j += 1
  
        # 모든 소수 출력
        for i in range(2, n + 1):
            if array[i]:
                print(i, end=' ')