분류 전체보기

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

# 내용 첫 인덱스부터 끝까지 하나하나 검사해가면서 탐색함. 만약 탐색되면 즉시 반환 끝까지 탐색했는데도 값이 없으면 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..

[백준-9461] 파도반 수열 - 동적계획법 이용하기

#문제 #풀이 점화관계에 주목하며 주어진 10개의 숫자에서 1,1,1,2,2,3,4,5,7,9에서 점화관계를 찾아보려고 노력했음. i의 값은 i-2 + i-3의 값과 같은 규칙을 찾을 수 있었다. #코드 def answer(n) : if( n

[백준-11726] 2*n 타일링 - 동적계획법 이용하기

# 문제 #풀이 첫 시도는 늘어나는 n에대해서 1또는 2의 합으로만 구성되면 된다고 생각했음. 즉 n=5일 경우 1+1+1+1+1이 되고, 1과 2의 합으로 5를 만드는 모든 경우의 수를 구하면 된다고 생각했다. 확통시간에 배운 경우의 수를 활용하면 풀 수 있을것 같았지만 기억이 나지 않았다. n이 늘어나는 경우 결국 앞선것을 재활용하면 되기 때문에 점화 관계를 찾아서 문제를 풀었다. # 코드 def answer(n): if (n

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

# 내용 재귀함수를 이용하여 회문검사, 파이썬 스트링 다루기 공부 파이썬에서는 재귀는 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(..