[알고리즘-공부] 5.동적계획법(2) - 연속행렬곱셈
코드로는 이해가 잘 안간다. 책을 봐도 읽기 싫게 생겼다.. 그냥 문제를 풀면서 한번 생각해 보자 우선 책을 읽고 문제를 접하는게 이해하기 쉬울것 같다. 이 알고리즘은 결합법칙이 핵심인것 같다. 첫번째 문제 A1 (10 x 2), A2 (2 x 20), A3 (20 x 5), A4 (5 x 15) 1. 일단 행렬 (1,1) ,(2,2), (3,3), (4,4)에 모두 0을 집어 넣자 2. 첫번째 사선인 (1,2), (2,3), (3,4)의 행렬값을 채워 나가자 A1A2 = (10 x 2) x (2 x 20) = (10 x 20), A1A2의 값 : 10 x 2 x 20 = 400 A2A3 = (2 x 20) x (20 x 5) = (2 x 5), A2A3의 값 : 2 x 20 x 5 = 200 A3A4 ..
[알고리즘-공부] 1. 알고리즘의 첫걸음(1) - 순차탐색, 이진탐색
1.1 최대 숫자 찾기 : 순차탐색 가장 큰 숫자가 적힌 카드를 찾는 한 가지 방법은 카드의 숫자를 하나씩 비교하면서 본 숫자들 중에서 가장 큰 숫자를 기억해가며 진행하는 방법이다. 마지막 카드의 숫자를 본 후에, 머릿속에 기억된 가장 큰 숫자가 적힌 카드를 바닥에서 집어든다. 순차탐색 : 카드를 한 장씩 차례대로 읽어가며 찾는 방법 ex) 17, 92, 18, 33, 58, 7, 33, 42 중 최댓값을 찾기 코드로 생각해보자 #최댓값 구하기 #입력 : 숫자가 n개 들어 있는 리스트 #출력 : 숫자 n개 중 최댓값 def find_max(arr): n = len(arr) #입력크기 n max_arr = arr[0] #리스트의 첫 번째 값을 최댓값으로 기억 for i in range(1,n): #1부터 ..
