Python으로 기초 수학 공식 구현하기 (직접 구현, 파이썬 라이브러리)

1. 최대공약수

1) 직접 구현 : 유클리드 호제법

def gdc(a,b):
	while b:
    	a, b = b, a%b
    return(a)

 

2) 라이브러리 활용

import math

gcd_val = math.gcd(a,b)

 

2. 최소공배수

1) 직접 구현 : 최대공약수 이용

def lcm(a,b):
	return (a*b) // gcd(a,b)

 

2) 라이브러리 활용

import math

lcm_val = math.lcm(a,b)

 

 

3. 조합

arr  배열에서 원소 개수가 r개인 조합 뽑기

1) 직접 구현

• r= 2일 경우, 이중 for문으로 인덱스를 조정하면서 구할 수 있다.

def combination(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            print(arr[i], arr[j])

 

• r>2 일 경우 : 가능한 모든 경우를 트리처럼 탐색 (DFS, 백트래킹)

def combintion(arr,r):
    result = []
    
    #i번째 값에 대해
    #start: 다음에 탐색 시작할 인덱스
    #path: 지금까지 선택한 값들
    #r개를 뽑으면 결과 저장하고 종료
    #start 값 옮겨서 여기서 부터 다시 선택 시작

    def backtrack(start, path):
        if len(path) == r:
            result.append(path[:]) #값 복사
            return #path.pop()으로 넘어감(재귀함수 종료)
        
        for i in range(start, len(arr)): #i의 경우에 대해
            path.append(arr[i])
            backtrack(i+1, path) #start값 옮김
            path.pop() #백트래킹
    
    backtrack(0,[])

 

<콜스택 설명>

예시: arr = [1,2,3], r = 2

backtrack(0, [])
 ├── [1]
 │    ├── [1,2] → return
 │    └── [1,3] → return
 │
 ├── [2]
 │    └── [2,3] → return
 │
 └── [3] (끝)

 

 

2) 라이브러리 활용

combinations(arr, r)

from itertools import combinations

arr = [1,2,3,4]
for i in combinations(arr, 2):
	print(i)
    
'''
출력결과
(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)
'''

 

 

4. 진법 변환

*결과값은 모두 string

1) n진수 -> 10진수

파이썬 기본 함수 int()를 활용한다.

int(string, base)

int('101',2) #20
int('505',6) #185
int('ACF',16) #2767

 

 

2) 10진수 -> 2,8,16 진수

각각 내장함수를 쓸 수 있다.

bin(11) #0b1011
oct(11) #0o13
hex(11) #0xb

 

 

 

3) 10진수 -> n진수

이 외의 진법으로 변환하려면 직접 코드로 구현해야한다.

10진법으로 주어진 수 A를 n진법으로 나타낼 때, 계산 과정을 생각해보면

몫이 0이 될 때까지 A를 n으로 나누고, 그 과정에서 도출된 나머지를 거꾸로 읽으면 n진수가 된다.

출처: https://dduniverse.tistory.com/entry/python-10%EC%A7%84%EB%B2%95%EC%9D%84-n%EC%A7%84%EB%B2%95%EC%9C%BC%EB%A1%9C-%EB%82%98%ED%83%80%EB%82%B4%EA%B8%B0

 

def solution(A, n):
	answer = ''
    if A == 0: #예외처리: 이 코드를 넣지 않으면 A가 0일 때 ''이 출력됨
        return '0'
    
    while A:
        answer += str(A%n)
        A = A // n
    
    return(answer[::-1])

 

내장함수 divmod 사용 

(몫,나머지) 로 튜플형태로 반환하여, 몫과 나머지를 각각 계산하는 것보다  효율적이다.

def solution(A, n):
    if A == 0:
        return '0'
    
    answer = ''

    while A > 0:
        A, mod = divmod(A, n)
        answer += str(mod)

    return answer[::-1]

 

10진수 이상으로 변환할 경우, 10이상 값이 문자이므로

digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" 미리 정의해두고 구현한다.

 

4) n진수 -> n진수

10진수를 거쳐 변환한다.

#ex. 2진수 -> 16진수
hex(int('1010',2))