•알고리즘(Algorithm )/스터디

[알고리즘] 순차탐색 파이썬 시간복잡도

# 내용 첫 인덱스부터 끝까지 하나하나 검사해가면서 탐색함. 만약 탐색되면 즉시 반환 끝까지 탐색했는데도 값이 없으면 False반환 # 코드 import random def seq_search(list,target): for i in range(len(list)) : if list[i] == target : return True return False if __name__ == '__main__': list = random.sample(range(30),10) target = 10 print(f"{list} target {target}") answer = seq_search(list,target) print(answer) # 시간복잡도 최악의 경우 n번 순회해야 하기 때문에 O(n)

[알고리즘] 이진탐색 파이썬 및 시간복잡도

# 내용 정렬된 데이터 셋에서 탐색을 시도함 함수가 실행될때마다 탐색하는 범위가 반토막이 되기 때문에 순차탐색에 비해 월등히 속도가 빠름 # 코드 # 이진탐색은 데이터셋이 정렬되어 있어야함. import random def binary_serach(list,target): print(f"{list}, target : {target}",end="") # 찾는 조건 if len(list) == 1 : if list[0] == target : return True else : return False elif len(list) == 0 : # binary_serach함수를 호출할때 list[mid+1:]로 슬라이싱 하기 때문에 # len이 0이 되는 경우가 존재 return False # 탐색 조건 mid = ..

[알고리즘] 병합정렬(merge-sort) 파이썬

# 정리 merge(left,right)함수를 만들어 두 리스트를 순차적으로 비교하면서 정렬하는 것 까지는 쉽게 했는데, 이 함수들을 재귀적으로 계속 호출해서 정렬시키는 방법을 잘 모르겠어서 꽤 오랜 시간이 걸렸다. 아직은 재귀가 익숙하지 않은거 같다. # 코드 import random def merge(left, right): sorted = [] lptr, rptr = 0, 0 while lptr < len(left) and rptr < len(right): if left[lptr] < right[rptr]: sorted.append(left[lptr]) lptr += 1 else: sorted.append(right[rptr]) rptr += 1 if( lptr < len(left)) : for i..

[알고리즘] 재귀함수 파이썬, 회문검사

# 내용 재귀함수를 이용하여 회문검사, 파이썬 스트링 다루기 공부 파이썬에서는 재귀는 1000번까지만 호출 가능함 재귀 함수의 잦은 사용을 막기 위해 동적 계획법(Dynamic Programming)을 이용 할 수 있음. 동적 계획법은 앞서 사용했던 것들을 이용하여 그다음 문제를 풀때 사용하는 것. # 코드 import random def sum_list(data): sum = 0 for i in data: sum += i return sum def reculsive_sum(data): if len(data) == 1: return data[0] return data[0] + reculsive_sum(data[1:]) # 회문 검사 def palindrome(str): for index in range(..

[알고리즘] 선택 정렬 파이썬

# 코드 import random def selection_sort(data): size = len(data) for target in range(size): min_index = target for index in range(target + 1, size): if (data[min_index] > data[index]): min_index = index #swap temp = data[min_index] data[min_index] = data[target] data[target] = temp if __name__ == '__main__': input = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] sample_list = random.sample(range(10),10) # test..

[알고리즘] 삽입정렬 파이썬

# 참고 Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook/Twitte visualgo.net # 코드 def insertion_sort(input): data = inp..