[Algorithm] 동적계획법(Dynamic programming) - Brute Force, Kadane’s Algorithm
#동적계획법(Dynamic programming) - 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 (wikipedia) - Bottom-Up 적 방법 #동적계획법 예제 - nm선 자르기 #nm의 선을 1m나 2m 자르는 방법의 수 #1m 선의 경우 #[1,1,1] => 1가지 #dy[1]=1 #2m 선의 경우 #[1,1,1],[2] => 2가지 #dy[2]=2 #3m 선의 경우 #[1,1,1] => 1가지 #[1,1,1],[2] => 2가지 #1가지(1m선의 경우) + 2가지(2m선의 경우) = 3가지 #dy[3]=3 #4m 선의 경우 #2가지(2m선의 경우) + 3가지(3m선의 경우) = 5가지 #dy[4]=5 n = int(input()) dy=[0]*(n+1) #배열을 만듦 dy[1]=..
2020. 9. 6.
[Python 기초] 탐색 (search)
#선형탐색 (Linear Search) def linear_search(L,x): i=0 #index i를 0으로 준다 while i < len(L) and L[i] != x: #i가 L리스트의 길이보다 작고, L의 i번째 원소가 x와 같지 않을때 i += 1 #i를 1씩 증가시켜나간다. #원소가 발견되면 i값을 가지고 loop가 종료하게 될 것이기 때문에 #i가 L리스트의 길이보다 짧으면 리스트 안에서 원소를 발견했다는 의미 if i < len(L): return i #발견된 x를 리턴하고 else: return -1 #그렇지 않으면 -1을 리턴한다. S = [3,8,2,7,6,7,6,10,9] linear_search(S,6) #Out: 4 S = [3,8,2,7,6,7,6,10,9] linear_s..
2020. 9. 6.
[Python 기초] 정렬 (sort)
#알파벳, 숫자 크기 순으로 정렬 L=['abcd','xyz','spam'] sorted(L) #Out: ['abcd', 'spam', 'xyz'] L=[3,7,2,7,1,7] L.sort() L #Out: [1, 2, 3, 7, 7, 7] #lambda : 익명함수 (lambda x,y: x + y)(5, 6) #Out: 11 ▼ 익명 함수 lambda 활용법 더보기 더보기 #map() list(map(lambda x: x ** 2, range(5))) # 파이썬 2 및 파이썬 3 #Out: [0, 1, 4, 9, 16] #reduce() from functools import reduce reduce(lambda x, y: x + y, [0, 1, 2, 3, 4]) #Out: 10 reduce(lam..
2020. 9. 5.
