𝐓𝐨𝐝𝐚𝐲 𝐈 𝐋𝐞𝐚𝐫𝐧 2022.03.29.화

Today I Learn (20220329)

---

오늘 유클리드 호제법과 그리디, 에라토스테스네의 체에 대해 배웠다.

사실 처음에는 내가 아는 수학적 개념이라해도 구현을 해내는 것은 매우 어렵게 다가왔다. 알고리즘을 시작한 지 거의 한달이 되어가는데, 아직 수학-->코드로 구현 이 부분이 부족하다고 느껴진다. 앞으로 더 많은 연습이 필요한거 같다. 하지만 수학에서 배웠던것을 코드로 구현해 쉽게 값을 낼 수 있다는 점이 흥미롭게 다가왔다.

오늘 동적계획법에 대해 일부 배웠는데, 많은 연습과 복습이 필요해보인다. 아직 개념이 잘 잡히지 않는다. 다른 사람들에게 많이 질문하고 내가 부족한 점을 채워나가야겠다!

---

---

유클리드 호제법

---

의미: 최초의 알고리즘

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. (출처:wikipedia)

<구현>

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

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

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

def abc(a,b):
    if b==0:
        print(a)
        return
    abc(b,(a-b)%b)

abc(a,b)

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

answer = 1
while b:
    answer = a%b
    a=b
    b=answer
    
print(a)

응용 - 최소공배수 구하기

---

#숫자 2개 입력받고 입력받은 두 숫자의 최소 공배수 구하기(least common multiple)
#lcm=gcd*(a/gcd)*(b/gcd)

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

gcd=0
def abc(a,b):
    global gcd
    if b==0:
        gcd = a
        return
    abc(b,(a-b)%b)
abc(a,b)

lcm = gcd*(a/gcd)*(b/gcd)
print(int(lcm))

에라토스테네스의 체 (소수 구하기)

---

#에라토스테네스의 체 (소수 구하기)
#소수 - 1과 자기 자신만으로 나눌 수 있는 수
#입력 받은 후 입력받은 숫자가 소수인지 아닌지 출력!
#힌트 2부터 자기자신 -1 까지 나누었을 때 나머지가 0이면 안됨

#입력값을 받아 소수인지 판별하시오.
#내 코드
n = int(input())
for i in range(2,n):
    if n%i ==0:
        print('소수 안됨')
        break
else:
    print('소수 됨')

#입력 50 #출력 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

#에라토스테네스의 체 (소수 구하기)
#소수 - 1과 자기 자신만으로 나눌 수 있는 수

#입력 받은 후 입력받은 범위까지의 소수를 찾기
a = int(input())
answer=[]
check=[0]*(a+1) #지울 거를 체크하는 박스
for i in range(2,a+1): #2부터 50까지 확인
    if check[i] ==0:
        answer.append(i) #소수는 answer에 저장~
		#남은 수 중에 작은 수 부터 50까지 작은수의 배수에 해당하는 index의 값을 1로 체크
    for j in range(i+i,a+1,i): 
        check[j]=1
print(*answer)

그리디(greedy)

---

https://www.acmicpc.net/problem/11399

#복잡도 n^2
n = int(input())
people = list(map(int,input().split()))
people.sort()

total=0
for i in range(n):
    for j in range(i+1):
        total+=people[j]
print(total)

#복잡도 n
a = int(input())
arr = list(map(int,input().split()))
arr.sort()
sum=0
for i in range(a):
	sum+=(arr[i]*(a-1))
print(sum)

 

 

#예약의 개수 입력받고, 예약 시작시간, 마감시간 입력받아 최대 몇개의 예약을 받을 수 있는지

#입력

10 #예약 개수
18 21 #예약 시작 시간, 파티 마치는 시간 입력
11 14
15 17
18 22
13 16
10 16
12 23
22 24
16 20
15 19

#1.끝나는 시간 기준으로 sort
#2.다음 시작시간이 그 전 파티 끝나는 시간보다는 크거나 같다 (다음시작 >=그 전 끝 cnt)


schedules = []
N = int(input())
for _ in range(N):
    schedules.append(list(map(int, input().split())))

schedules.sort(key=lambda x: x[1]) #파티 종료시간을 기준으로 sort하기
time = 0
cnt = 0
for i in range(len(schedules)):
    if time <= schedules[i][0]: #시작 시간과 비교
        time = schedules[i][1] #끝 시간을 대입 해주기
        cnt += 1 #파티 수
print(cnt)

 

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

비슷하지만 풀이법이 좀 달랐던 백준문제... 2번이나 틀렸다.

이 문제의 경우에는 먼저 시작시간으로 정렬을 해주고 다시 종료시간으로 정렬해줘야 해결할 수 있었다.

n = int(input())

meeting=[list(map(int,input().split())) for _ in range(n)]
meeting.sort(key=lambda x:x[0])
meeting.sort(key=lambda x:x[1])

cnt=0
time=0
for j in range(n):
    if time<=meeting[j][0]:
        time = meeting[j][1]
        cnt+=1
print(cnt)