[중급] 가볍게 이것저것
알고리즘 문제풀이_1
PassionPython
2019. 10. 15. 23:03
알고리즘 문제풀이
1. selection_sort
2. 함수 f(n)는 1 부터 n 사이에서 1이 나오는 횟수를 구해준다. f(13) = 6, f(1) = 1 이다.
f(n) = n 을 만족하는 첫 번째 양수가 1 이라고 할 때, 2 번째 양수는 얼마인가?
3. 개구리가 처음엔 한 칸 뛰고 그 이후부터는 앞선 점프의 2 배 거리를 뛴다.
점프시 도착지점을 넘어서리라 예상되면 다시 한 칸으로 뛰는 거리를 줄여 다시 2배씩
점프 거리를 늘려나간다. 원점(0) 부터 시작한 경우 25 위치에 도달하기 위해서는
9번의 점프가 필요한 셈이다.(1+2+4+8 + 1+2+4 + 1+2) x 위치까지 가기 위한 함수 hop(x) 만들기.
4. c, d 사이의 구간 안에서 일차함수 f(x) = ax+b 의 해를 구하는 함수 sol(a, b, c, d) 를 만들기.
#_HW_1_sorting_program
'''
x와 y는 둘 다 d_in 리스트의 인덱스를 의미한다.
리스트에서 하나씩 뽑는 이터레이터로 2중 for 문
구성하고 바깥 for 문에서는 x, 안쪽 for 문은 y.
그러면 y 가 d_in 리스트를 한 바퀴 돌고 비로소
x 가 다음 이터레이션을 수행한다.
그렇게 해서 d_in 의 y번째와 x 번째를 비교해
Y번째가 더 큰 경우 x 번째와 y번째를 교환한다.
x 인덱스와 y 인덱스의 대소비교에 의해
오름/내림차순 기능을 구현해 주었다.
'''
def sel_sort(d_in, ascending=False):
for x in range(len(d_in)):
for y in range(len(d_in)):
if ascending == False:
if x >= y:
continue
else:
if x <= y:
continue
if d_in[x] < d_in[y]:
d_in[x], d_in[y] = d_in[y], d_in[x]
return d_in
sel_sort([1, 5, 78, 7, 2, 5, 8], ascending=True)#_HW_2_google_question
'''
while True시 epoch에 1씩 추가해준다.
epoch를 str() 하여 for로 뽑아 in 판독한다.
들어있으면 one에 +1. epoch == one 이면 one_ones 에 one 을 추가해준다.
one 변수는 1이 출현한 횟수이다. plotter는 matplotlib 으로 plotting 하기
위한 리스트이고 한 epoch 이 끝날 때마다 숫자가 하나 들어간다.
해당 epoch시 1이 있으면 그만큼 더해져 들어가고 없었다면 지난 번 epoch의 값이다.
one_ones는 epoch==one인 경우 묶음이고 [-1] 로 선택.
'''
import matplotlib.pyplot as plt
%matplotlib inline
def f(n):
one_ones, plotter, one, epoch = [], [], 0, 0
for epoch in range(1, 10**7):
for letter in str(epoch):
if '1' == letter:
one = one + 1
plotter.append(one)
if epoch == one:
one_ones.append(one)
if len(one_ones) == n:
return one_ones[-1], epoch, plotter
result, epoch, plotter = f(2)
print(result)
plt.figure(figsize=(12, 6))
plt.plot(plotter) ; plt.plot([i for i in range(1, epoch)])
plt.show()199981
#_Frog's_Hop
'''
도착지점에 도달시 반복 종료이므로 while True에 break로 반복을 관리한다.
개구리는 다음 번 뛰어야 할 거리는 기존 뛰었던 거리의 2 배이다.
다음 번 뛰었을 때 도착지점을 넘기면 1칸부터 다시 시작이므로
다음 번 뛸 거리 next_hop에 현재 거리를 더해서 도착지점 넘기는지 if문 판별.
도착지점 = 뛴거리 이면 종료.
'''
def hop(x):
hop, meter, i = 0, 0, 0
while True:
next_hop = 2 ** i
if meter + next_hop > x:
i = 0
hop, meter = hop + 1, meter + 2 ** i
print(hop, meter)
i = i + 1
if meter == x:
break
return hop
hop(25)1 1
2 3
3 7
4 15
5 16
6 18
7 22
8 23
9 25
9#_f(x) = ax + b, [c ~ d] range, sol(a, b, c, d)
'''
해가 구간 안에 존재하지 않을 경우를 일괄 배제하기 위해
f(x) = ax + b 함수의 x 에 c, d를 넣은 값의 곱이 양수인지 판별.
구간의 시작과 끝의 부호가 서로 다르면 중간값 정리에 의해 연속/미분 가능한
함수에서 부호가 다른 두 지점 사이에 반드시 함수를 0으로 만드는 해가 존재한다.
f(x) = ax + b, f’(x) = a 이므로 이 함수의 x에 대한 기울기는 a 이다.
만약 f(x)의 값이 + 이면 x를 –a 방향으로 이동, f(x)의 값이 - 이면 x를 +a 방향으로 이동.
LR은 이동시킬 비율이다. 1만 번 이터레이션 마다 LR 을 절반으로 줄인다.
'''
def sol(a, b, c, d):
if (a*c + b) * (a*d + b) > 0: return 'solution not in range %s ~ %s' % (c, d)
plotter, epoch, LR, x = [], 0, 1, (c + d) / 2
while True:
epoch = epoch + 1
loss_SE, grad = a * x + b, LR * a
plotter.append(loss_SE)
if loss_SE < 0 : grad = -grad
x = x - grad
text = 'epoch_{0:8.0f}, x_{1:12.6f}, Loss_SE_{2:20.6f}'.format(
epoch, x, loss_SE)
if epoch % 10000 == 0 or epoch == 1 : LR = LR * 0.5; print(text)
if (loss_SE ** 2) < 10**(-20) :
print('\n final_entry \n' + text) ; break
return x
sol(1000, -1000, -3, 6)epoch_ 1, x_ -998.500000, Loss_SE_ 500.000000
epoch_ 10000, x_ -498.500000, Loss_SE_ 500.000000
epoch_ 20000, x_ 1.500000, Loss_SE_ -249500.000000
epoch_ 30000, x_ 1.500000, Loss_SE_ -124500.000000
epoch_ 40000, x_ 1.500000, Loss_SE_ -62000.000000
epoch_ 50000, x_ 1.500000, Loss_SE_ -30750.000000
epoch_ 60000, x_ 1.500000, Loss_SE_ -15125.000000
epoch_ 70000, x_ 1.500000, Loss_SE_ -7312.500000
epoch_ 80000, x_ 1.500000, Loss_SE_ -3406.250000
epoch_ 90000, x_ 1.500000, Loss_SE_ -1453.125000
epoch_ 100000, x_ 1.500000, Loss_SE_ -476.562500
epoch_ 110000, x_ 0.523438, Loss_SE_ 11.718750
epoch_ 120000, x_ 1.011719, Loss_SE_ -232.421875
epoch_ 130000, x_ 1.011719, Loss_SE_ -110.351562
epoch_ 140000, x_ 1.011719, Loss_SE_ -49.316406
epoch_ 150000, x_ 1.011719, Loss_SE_ -18.798828
epoch_ 160000, x_ 1.011719, Loss_SE_ -3.540039
epoch_ 170000, x_ 0.996460, Loss_SE_ 4.089355
epoch_ 180000, x_ 0.996460, Loss_SE_ 0.274658
epoch_ 190000, x_ 1.000275, Loss_SE_ -1.632690
epoch_ 200000, x_ 1.000275, Loss_SE_ -0.679016
epoch_ 210000, x_ 1.000275, Loss_SE_ -0.202179
epoch_ 220000, x_ 0.999798, Loss_SE_ 0.036240
epoch_ 230000, x_ 1.000036, Loss_SE_ -0.082970
epoch_ 240000, x_ 1.000036, Loss_SE_ -0.023365
epoch_ 250000, x_ 0.999977, Loss_SE_ 0.006437
epoch_ 260000, x_ 1.000006, Loss_SE_ -0.008464
epoch_ 270000, x_ 1.000006, Loss_SE_ -0.001013
epoch_ 280000, x_ 0.999999, Loss_SE_ 0.002712
epoch_ 290000, x_ 0.999999, Loss_SE_ 0.000849
epoch_ 300000, x_ 1.000001, Loss_SE_ -0.000082
epoch_ 310000, x_ 1.000000, Loss_SE_ 0.000384
epoch_ 320000, x_ 1.000000, Loss_SE_ 0.000151
epoch_ 330000, x_ 1.000000, Loss_SE_ 0.000034
epoch_ 340000, x_ 1.000000, Loss_SE_ -0.000024
epoch_ 350000, x_ 1.000000, Loss_SE_ 0.000005
epoch_ 360000, x_ 1.000000, Loss_SE_ -0.000009
epoch_ 370000, x_ 1.000000, Loss_SE_ -0.000002
epoch_ 380000, x_ 1.000000, Loss_SE_ 0.000002
epoch_ 390000, x_ 1.000000, Loss_SE_ -0.000000
epoch_ 400000, x_ 1.000000, Loss_SE_ 0.000001
epoch_ 410000, x_ 1.000000, Loss_SE_ 0.000000
epoch_ 420000, x_ 1.000000, Loss_SE_ 0.000000
epoch_ 430000, x_ 1.000000, Loss_SE_ 0.000000
epoch_ 440000, x_ 1.000000, Loss_SE_ -0.000000
epoch_ 450000, x_ 1.000000, Loss_SE_ -0.000000
epoch_ 460000, x_ 1.000000, Loss_SE_ -0.000000
epoch_ 470000, x_ 1.000000, Loss_SE_ 0.000000
epoch_ 480000, x_ 1.000000, Loss_SE_ 0.000000
epoch_ 490000, x_ 1.000000, Loss_SE_ -0.000000
epoch_ 500000, x_ 1.000000, Loss_SE_ 0.000000
epoch_ 510000, x_ 1.000000, Loss_SE_ -0.000000
final_entry
epoch_ 510002, x_ 1.000000, Loss_SE_ 0.000000
0.999999999999833