정렬
1. 자료구조 알고리즘 4주차 강의
1-1 정렬
:데이터를 순서대로 나열하는 방법
1-2 버블 정렬
:한 자리 옆에 있는 값을 비교 교환(가장 큰값이 맨 뒤로 가짐)
1-3 선택 정렬
:가장 작은 값을 찾는다. 맨 앞으로 보낸다. 다음 인덱스부터 반복
1-4 삽입 정렬
:하나씩 올바른 위치에 "삽입" 하는 방식
문제풀이
2. 문제풀이
2-1 1010. 다리 놓기
순서 없는 뽑기!
nCk = M! / ( N! X (M -N)!)
=> factorial(M)//factorial(N)//factorial(M-N)2-2 1003. 피보나치 함수
전역변수로 풀기가 가능하나 시간초과!
n = 입력 값
Z(n) = 총 0의 개수
O(n) = 총 1의 개수
Z(n) = Z(n-1) + Z(n+2)
O(n) = O(n-1) + O(n+2) 가 성립.
따라서 Z(0), Z(1), Z(2) 를 구하면 나머지 값도 알 수 있다.
따라서 O(0), O(1), O(2) 를 구하면 나머지 값도 알 수 있다.2-3 12865. 평범한 배낭
냅색 알고리즘을 이용
1.담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등):
Fractional Knapsack Problem
2.담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다):
0-1Knapsack Problem
여기서는 0-1 배낭문제(0-1Knapsack Problem)를 이용
1) x축엔 가방 1~K 까지의 무게, y축은 물건 N개 개수 만큼의 배열을 만들어준다.
2) 행을 차례대로 돌며 다음과 같은 알고리즘을 수행해준다.
3-0) 현재 물건이 현재 돌고있는 무게보다 작다면
[이전 물건][같은 무게] knapsack[i-1][j]를 입력해준다.
3-1) 현재 물건을 넣어준다. 물건을 넣은 뒤의 남은 무게를 채울 수 있는 최댓값
knapsack[i-1][j-weight]을 위의 행에서 가져와 더해준다.
3-2) 현재 물건을 넣어주는 것보다.
다른 물건들로 채우는 값 knapsack[i-1][j]을 가져온다.
4) 3-1과 3-2 중 더 큰 값을 knapsack[i][j]에 저장(가장 가치 높은 구성)
===> knapsack[N][K] = K무게일 때의 최대 가치값
# N, K = 4 , 7
# W = [0, 6, 4, 3, 5]
# V = [0, 13, 8, 6, 12]
knapsack = [[0 for j in range(K+1)] for i in range(N+1)]
for i in range(1,N+1):
for j in range(1,K+1):
if j >= W[i]:
knapsack[i][j] = max(knapsack[i - 1][j - W[i]] + V[i], knapsack[i - 1][j])
else:
knapsack[i][j] = knapsack[i-1][j]
#==결과==
#무게j 0 1 2 3 4 5 6 7 /물품i
# [[0, 0, 0, 0, 0, 0, 0, 0], W= 0, V = 0
# [0, 0, 0, 0, 0, 0, 13, 13], W= 6, V = 13
# [0, 0, 0, 0, 8, 8, 13, 13], W= 4, V = 8
# [0, 0, 0, 6, 8, 8, 13, 14], W= 3, V = 6
# [0, 0, 0, 6, 8, 12, 13, 14]] W= 5, V = 15