분류 전체보기161 삽입 정렬(insertion sort) 삽입 정렬(insertion sort) 1. 두 번째 인덱스부터 시작한다 2. 인덱스 앞의 데이터들과 비교한다 2-1. 앞의 데이터가 해당 인덱스의 데이터보다 작으면 둘의 위치를 바꾼다 3. 위 과정을 다음 나머지 값에서 반복한다 * 시간복잡도 : O(N^2) - 최선의 시간 복잡도: O(N) import random # set up def insertion_sort1(data): for x in range(len(data) - 1): for y in range(x + 1, 0, -1): if data[y] < data[y - 1]: data[y - 1], data[y] = data[y], data[y - 1] else: break return data def insertion_sort2(data): f.. 2020. 9. 28. 선택 정렬(selection sort) 1. 주어진 데이터 중에서 최솟값을 찾는다 2. 맨 앞의 데이터와 찾은 최솟값의 위치를 바꾼다 3. 위 과정을 다음 나머지 값에서 반복한다 * 시간복잡도 : O(n^2) import random # set up def selection_sort(data): for x in range(len(data)-1): lowest = x for y in range(lowest+1, len(data)): if data[lowest] > data[y]: lowest = y data[lowest], data[x] = data[x], data[lowest] return data # given data = random.sample(range(30), 5) # when print(selection_sort(data)) # t.. 2020. 9. 28. 20/09- 다리를 지나는 트럭 def solution(bridge_length, weight, truck_weights): answer = 0 bridge_on = [0] * bridge_length curr_weight = 0 while truck_weights: answer += 1 bridge_out = bridge_on.pop(0) curr_weight -= bridge_out if curr_weight + truck_weights[0] > weight: bridge_on.append(0) else: truck = truck_weights.pop(0) bridge_on.append(truck) curr_weight += truck while curr_weight>0: answer += 1 bridge_out = bridge_o.. 2020. 9. 28. 1부터 n까지 더하기 # 1부터 100까지 더하기 1 # O(n) sum = 0 for num in range(1,101): sum += num print(sum) # 5050 # 1부터 100까지 더하기 2 # O(1) n = 100 sum = n * (n+1) / 2 print(int(sum)) # 5050 2020. 9. 28. 이전 1 ··· 30 31 32 33 34 35 36 ··· 41 다음