기초 알고리즘 [수학]

01. 1부터 n 까지 합계 구하기 

 

1.for문 이용하기

#for문 
n = int(input())
result = 0

for i in range(1,n+1) : 
 	result += i 

print(result)

2. while문 이용하기

#while문 
n = int(input())
result = 0 

cnt = 1
my_sum = 0 
while cnt <= num :
	my_sum += cnt 
    cnt += 1 

print(my_sum)

3. 내장함수 이용하기 (sum) 

n = int(input())

my_sum = sum(range(1,n+1))
print(my_sum)

4. 수열의 합 구하는 공식으로 구하기 

n = int(input()) 

result = (1+n)*n / 2 
print(result)

 

---

02. 최대값, 최소값 구하기 

1.함수 이용하기 (max, min) 

arr = map(int,input().split()) 

print(max(arr))
print(min(arr))

2. 반복문 이용하기 

arr = list(map(int,input().split())) # 3 1 5 2 4 

max_num = 0 
for i in arr : 
	if max_num  < i :
    	max_num = i 

print(max_num)

만일 숫자가 음수로만 들어온다면, 초깃값 0보다 큰 숫자가 리스트에 없기 때문에 최대값이 0이 출력될 것이다. 

⇒ 숫자 범위 고려하기 (입력된 리스트 값 중 하나를 초기값으로 정하는 것이 좋은 방법) 3

arr = list(map(int,input().split())) # 3 1 5 2 4 

max_num = arr[0]
for i in arr[1:] : 
	if max_num  < i :
    	max_num = i 

print(max_num)

---

03. 소수구하기

소수란 ? 1과 자신 외에는 나누어 지지 않는 양의 정수를 뜻한다.

num = int(input()) 

def is_prime(n) : 
	for i in range(2,n) : 
    	if n % i == 0 :
        	return False
    return True

if is_prime(n) :
	print("소수입니다") 
else :
	print("소수가 아닙니다")

2부터 n 직전까지 숫자로 n 값을 나누어 0이 한번이라도 나온다면 더 이상 수행하지 않고 소수가 아니라느 False로 return한다.  0이 나왔다는 의미는 나누어 졌다는 뜻이고, 소수가 아니라는 뜻이기 때문이다.

n = int(input())
result = 0
for i in range(2,n-1) :
	if is_prime(i) :
    	result += 1 
 print(result)

but, 숫자가 100만이 넘어가게 되면 프로그램 속도가 느려진다. 

 

약수의 성질 

위의 방법보다 효율적인 알고리즘을 구현하기 위해 약수가 갖는 성질을 생각해보자. 모든 약수는 가운데 약수를 기준으로 곱셈연산에 대해 대칭을 이루는 성질이 있다. 예를 들면 16의 약수는 1,2,4,8,16인데, 이 때 2*8  = 8*2 =16 이므로 약수들이 서로 곱셈에 대해 대칭이다. 따라서 특정한 자연수의 모든 약수를 찾고 싶을 때 가운데 약수(제곱근)까지만 확인하면 된다. 

( 16이 2로 나누어 떨어진다는 것은 8로도 나누어 떨어진다는 뜻이므로 ,16의 모든 약수를 보다 빠른 속도로 구할 수 있다.)

def is_prime(n) :
	for i in range(2, int(n**0.5) + 1) :
    	if n % i == 0 :
        	return False
     return True 
     
     
num = 1000000
result = 0 
for i in range(2,num) :
	if is_prime(i) :
    	result +=1 

print(result)

---

04. 에라토스테네스의 체 

어떤 수가 소수인지 알고 싶을 때는 앞에서 배운 방법을 이용, 주어진 범위 내에서 대량의 소수를 빠르게 찾을 때는 에라토스테네스의 체를 이용 ( 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법) 

 

1. 1은 소수가 아니므로 제외 

2. 2부터 시작하여 2는 소수가 되고, 2의 배수는 모두 소수가 아니게 된다,

3. 3은 소수이고, 3의 배수는 모두 소수가 아니게 된다.

4. 4는 이미 2의 배수이기 때문에 소수가 아니다

5. 5는 소수이고 5의 배수는 모두 소수가 아니다 

6. 위 과정을 반복하면 소수인 수 만 남는다. 

 

 

 

 num = int(input())
 
 prime = [True] * (num +1) 
 
 prime[0] , prime[1] = False, False #2부터 시작하기 때문에 0과1은 소수가 아닙니다.

for i in range(2, num+1) : #2부터 백만까지 반복합니다.
 	if prime[i] : #prime[i]가 True이면 소수입니다.
    	for j in range(i * 2 , num+1 , i ) : # i*2배부터 i의 배수를 순회합니다
        	prime[j] = False #i의 배수는 모두 소수가 아닙니다. 
            
result = 0
for i in range(num+1) : 
	if prime[i] :
    	result += 1 

print(f'2부터 {num} 까지의 소수는 총 {result}개 있습니다.')

---

05. 유클리드 호제법 

유클리드 호제법은 기원전 3세기경의 수학자 유클리드가 만든 최대 공약수를 구하는 알고리즘 입니다. 

⇒ a와 b의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다. 

 

1. 최대 공약수 구하기 (유클리드 호제법 X) 

a,b = map(int,input().split()) 

for i in range(min(a,b) , 0 , -1) :
	if a % i ==0 and b % i == 0 :
    	print(i) 
        break

2. 최대공약수 구하기  (유클리드 호제법 O)

 

1. 두 수 중 큰수를 작은 수로 나눕니다,

2. 나머지가 0이면 작은 수가 최대 공약수가 됩니다,

3. 나머지가 0이 아니면 작은 수가 큰 수가 되고, 나머지를 작은 수로 대체하고 1단계로 돌아갑니다. 

 

예) 510과 210의 최대 공약수 

1. 510을 210으로 나눕니다. 나머지는 90입니다. 

2. 210을 90으로 나눕니다. 나머지는 30입니다.

3. 90을 30으로 나눕니다. 나머지는 0입니다. 

4. 나머지가 0이므로 최대공약수는 30입니다.

 

a,b = map(int,input().split())

if b>a :
	a,b = b,a

def gcd(a,b) : #b가 0이 아닐 때 까지 
	while b != 0:
    	a,b = b, a%b 
    return a

---

06. 기하

1. 세 막대

삼각형의 특성 : 가장 긴 변은 나머지 두 변의 합보다 클 수 없다. 

a+b > c  따라서 가장 긴 변의 길이를 a+b-1로 설정하면 가장 큰 둘레를 구할 수 있다. 

 

2. 터렛

풀이

출처 : https://mathjk.tistory.com/m/178

 

두 원이 한 점에서 만날 때 ⇒ 좌표의 수 1 

두 원이 두 점에서 만날 때 ⇒ 좌표의 수 2 

두 원이 만나지 않을 때  ⇒ 좌표의 수 0 

조규현 좌표 = 백승환 자표 ⇒ 좌표의 수 -1

 

import sys 
from math import sqrt
T = int(input())

for i in range(T) :
	x1,y1,r1,x2,y2,r2 = map(int,sys.stdin.readline().split())
    distance = sqrt((x1-y1)*2 + (x2-y2)**2)
    diff = ans(r1-r2)
    
    # 두 원이 일치할 경우 
    if distance == 0 and diff == 0 :
    	ans = -1 
    # 두 원이 내접하거나 외접할 경우
    elif distance == diff and distance == r1+r2 :
    	ans = 1 
    # 두 원이 두 점에서 만날 경우
    elif diff < distance <r1+r2 :
    	ans = 2 
    print(ans)

 

💡input() 대신에 sys.stdin.readline()을 사용하는 이유 

: 반복문을 여러 줄을 입력 받아야 하는 경우에는 input()으로 입력받는다면 시간 초과가 발생할 수 있다.

import sys 
a = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))

- sys.stdin.readlin()은 한줄 단위로 입력받기 때문에, 개행문자가 같이 입력받아진다.

- 만일 3을 입력했다면 3\n이 저장되기 때문에 개행문자를 제거해야 한다. 

- 변수타입이 str로 저장되기 때문에, 정수로 사용하기 위해서는 형 변환을 해준다. 

 

 

참고자료: https://wikidocs.net/book/10280