LiDARism

최대값 찾는 방법은 1. 정렬을 하거나 2. 하나하나 값을 비교해서 하면 되지만, 이번 알고리즘에는 제한이 있다. 알고리즘의 시간복잡도를 O(n)이 되도록 해야한다. 시간복잡도가 O(n)이 되기 위해선, 반복문이 이중으로 존재하면 안된다. 그러므로 다음과 같이 작성한다. price_tag = [10300,9600,9800,8200,7800,8300,9500,9800,10200,9500] def max_profit(prices): n = len(prices) maxprofit = 0 minprice = prices[0] for x in range(1,n): profit = prices[x] - minprice if profit > maxprofit: maxprofit = profit if prices[x]..

1. 큐와 스택 큐 : First In First Out. 먼저 들어간 데이터가 가장 먼저 나간다. 자료투입을 enqueue, 자료 출력을 dequeue라고 한다. 스택 : Last In First Out. 마지막에 들어간 자료가 가장 먼저 나간다. 자료투입을 push, 자료출력을 pop이라고 한다. 2. 큐와 스택을 이용한 간단한 알고리즘 파이썬에서는 리스트 메서드(append, pop)를 이용해 간단히 큐와 스택을 표현할 수 있다. 큐와 스택을 이용하여 회문(바로 읽어도 거꾸로 읽어도 같은 문장)을 찾는 알고리즘을 작성하고자 한다. 큐와 스택은 출력 순서가 서로 반대이다. 즉 큐에서나 스택에서는 읽는 데이터가 순서가 같다면 그 문장은 회문일 것이다. def Palindrome(lst): #큐와 스택 ..

탐색 범위를 절반으로 줄이는 것을 반복해서 탐색하는 방법이다. 이진탐색은 데이터가 정렬이 되어있음을 전제하고 사용하는 탐색 알고리즘이다. 계산 복잡도는 O(logn)이다. def Binary_search(lst, s_value): start = 0 end = len(lst) -1 #리스트 탐색범위 변수이다. while start lst[mid]: start = mid + 1 else: end = mid - 1 return -1 #찾지 못했을 때 반환하는 값이다. d = [1,4,9,16,25,36,49,64,81] n = 36 print(Binary_search(d, n)) d2 = [1,4,9,16,25,36,49,64,81,100,121,144] n2 = 144 print(Binary_search(d..

https://knowledgeforengineers.tistory.com/22 병합정렬 예제 #병합정렬 예제이다. #내가 먼저 만들어본 코드 오류가 있어서 잡아내야한다.... #문제가 있는 모듈 def mergesort(lst): l = int(len(lst)/2 - len(lst)%2) lst1 = lst[:l] lst2 = lst[l:] if l>1: mergesort(lst.. knowledgeforengineers.tistory.com 전에 병합정렬 예제를 올렸었다. 당시 내가 스스로 작성했던 소스코드가 이랬었다. def mergesort(lst): l = int(len(lst)/2 - len(lst)%2) lst1 = lst[:l] lst2 = lst[l:] if l>1: mergesort(l..

#병합정렬 예제이다. #내가 먼저 만들어본 코드 오류가 있어서 잡아내야한다.... #문제가 있는 모듈 def mergesort(lst): l = int(len(lst)/2 - len(lst)%2) lst1 = lst[:l] lst2 = lst[l:] if l>1: mergesort(lst1) mergesort(lst2) return mergesort_sub(lst1, lst2) # 병합하는 모듈 def mergesort_sub(lst1, lst2): new_lst = [] n1 = len(lst1) n2 = len(lst2) i = 0 j = 0 while n1>0 and n2>0: if lst1[i] > lst2[j]: new_lst.append(lst2[j]) j += 1 n2 -= 1 else: n..

#삽입정렬 예제이다. #먼저 연습 def insert_sort(lst): l = len(lst) i = 0 lst_sort = [] lst_sort.append(lst[i]) for i in range(0,l): m = len(lst_sort) for j in range(0, m): if lst[i] < lst_sort[j]: lst_sort.insert(j, lst[i]) break #맨 뒤까지 다 찾아봤으나 안보이는 경우 맨 뒤에 쳐박아야한다. if (j == (m-1)) and (lst[i] not in lst_sort) : lst_sort.append(lst[i]) return lst_sort d = [3,1,5,2,4] print(insert_sort(d)) # 책에서 제시하는 삽입정렬 예시이다..

# 파이썬 기반으로 작성한다. # 선택정렬, 삽입정렬, 병합정렬 세가지 중 선택정렬에 관한 예제이다. # 선택정렬은 O(n^2)인 알고리즘이다. # 쉽게 쓴 것 먼저 def finding_min_index(lst): n = len(lst) min_index = 0 for i in range(0, n): if lst[i]

# 파이썬 기반으로 작성한다. # 순차탐색은 시간복잡도가 O(n)인 알고리즘이다. def search_list(lst, findingvalue): n = len(a) for i in range(0,n): if findingvalue == lst[a]: return i //찾는 경우 해당 인덱스 값을 반환한다. return -1 //찾지 못하면 -1 반환 lst_v = [17,92,18,33,58,7,33,42] print(search_list(lst_v, 18)) print(search_list(lst_v, 33)) print(search_list(lst_v, 900))