출발하는 위치 k와 이동가능한 거리를 m이 주어질때, 가장 많은 동전을 획득하려고하면 몇개를 획득할 수 있는지 알려주는 함수를 만드세요.
예를 들어 리스트 A와 k, m이 아래와 같을때
1 2 3
A = [2, 3, 7, 5, 1, 3, 9] k=4 m=6
가장 많은 동전을 주울수있는 방법은 아래와 같고
1 2 3 4 5 6 7
4번째에서 출발 - 1개 획득 왼쪽으로 이동 - 5개 획득 (1번이동) 왼쪽으로 이동 - 7개 획득 (2번이동) 오른쪽으로 이동 - 0개 획득 (3번이동) 오른쪽으로 이동 - 0개 획득 (4번이동) 오른쪽으로 이동 - 3개 획득 (5번이동) 오른쪽으로 이동 - 9개 획득 (6번이동)
defsolution(A, k, m): acc_ls = [] sum = A[k] for i in range(k-1,-1,-1): sum += A[i] acc_ls.append(sum) acc_ls = sorted(acc_ls, reverse=True) acc_ls.append(A[k])
sum = 0 for j in range(k+1,len(A)): sum += A[j] acc_ls.append(sum) result = 0 min = k - m if min < 0: min = 0 max = k + m if max > len(A)-1: max = len(A)-1 result = A[min] if result < A[max]: result = A[max] for i in range(1, round(m/2)): up = i down = m - 2*i if up + down > m: continue try: if acc_ls[k+up] + acc_ls[k-down] > result: result = acc_ls[k+up] + acc_ls[k-down] if acc_ls[k-up] + acc_ls[k+down] > result: result = acc_ls[k-up] + acc_ls[k+down] except: continue return result
defaccumulate(A): result = [0] for a in A: result.append(result[-1]+a) return result
defrange_sum(A, x, y): return A[y+1] - A[x]
defsolution(A, k, m): acc_A = accumulate(A) result = A[k] # 왼쪽으로 출발 후에 오른쪽으로 방향 이동 for left in range(0, ceil(m/2)): # 왼쪽으로 0번 이동한 것 포함, 즉 오른쪽으로만 이동한 경우 포함 right = m - (left*2) left_idx = max(k-left, 0) # IndexError 방지 right_idx = min(len(A)-1, k+right) # IndexError 방지 result = max(result, range_sum(acc_A, left_idx, right_idx)) # 오른쪽으로 출발 후에 왼쪽으로 방향 이동 # 동일하게 작성 return result
채점하기
매주 금요일 알고리즘 테스트 결과를 채점하기 귀찮아졌습니다.
그래서 직접하지 않고, 수강생분들에게 공부가 된다는 사탕발림으로 서로의 시험결과를 채점하게 하려고합니다.
단, 양심적으로 진행하기 위해서 그 누구도 자신의 시험을 채점하지 않는다고 할때.
채점할 수 있는 경우의 수를 구하는 함수를 구하세요.
는
n=1일때 0개 n=2일때 1개 그리고 n>=3일때
(n-1) * ( (n-1)명이서 서로 채점하는 경우의 수 + (n-2)명이서 서로 채점하는 경우의 수)) 라는 특징을 따른다고 합니다.
def solution(n):함수를 생성하세요.
조건
1 <= n <= 1000
1 2 3 4
defsolution(n): if n <= 2: return n-1 return (n-1) * (solution(n-1) + solution(n-2))
memorization function 중요
1 2 3 4 5 6 7 8
defdeco(func): m = {} definner(n): ifnot m.get(n): result = func(n) m[n] = result return m[n] return inner
1 2 3 4 5
@deco defsolution(n): if n <= 2: return n-1 return (n-1) * (solution(n-1) + solution(n-2))
코드 실행시간 정확히 측정하는법
1 2 3 4 5 6 7
import time
start = time.perf_counter()
end = time.perf_counter()
end - start
Posts
다중선형회귀
다중선형회귀단순선형회귀는 단일 설명변수를 기반으로 반응변수를 예측하는 유용한 기법이다. 하지만 실제로는 보통 하나보다 많은 설명변수가 관련된다. 예를 들어, Advertising 자료에서 판매량과 TV 광고의 상관관계를 조사하였다. 광고자료에는 또한 라디오와 신문광고에
모델의 정확도 평가
귀무가설을 기각하고 대립가설을 채택했다면, 모델이 데이터에 적합한 정도를 수량화 하고자 할 것이다.선형회귀적합의 질(quality)은 보통 잔차표준오차(RSE)와 R2 통계량을 사용하여 평가한다. Advertising 자료의 TV 광고예산에 대한 판매량의 회귀에서
ubuntu virtualbox 용량 늘리기
ubuntu에서 virtualbox로 window를 쓰고 있다.window를 쓰는 와중에 하드디스크 용량이 부족하여 용량을 늘리고 싶어 virtualbox 설정을 이것저것 만져보았지만virtualbox 내의 설정 부분에서는 불가능하다는 것을 알았다. 1VBoxManag
계수 추정값의 정확도 평가
X와 Y의 실제(true) 선형관계는 어떤 알려지지 않은 함수 f에 대해 Y=f(x)+ϵ의 형태를 가지며, ϵ은 평균이 영인 랜덤오차항이다. 만약 f가 선형함수로 근사된다면 이 관계를 다음과 같이 나타낼 수 있다.
선형회귀
3. 선형회귀선형회귀에서 답을 찾아봐야하는 몇 가지 중요한 질문들 광고예산과 판매 사이에 상관관계가 있는가? 광고예산과 판매 사이에 얼마나 강한 상관관계가 있는가? 어느 매체가 판매에 기여하는가? 판매에 대한 각 매체의 효과를 얼마나 정확하게 추정할 수 있는가? 미래의