** 대표적인 탐색 알고리즘 - 순차 탐색, 해시, 이진 탐색 트리, 이진 탐색, ... ** 이진 탐색(Binary Search) 탐색할 자료를 둘로 나누어 해당 데이터가 있을 만한 곳을 탐색하는 방법 순차 탐색과 비교 ** 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘 (Divide and Conquer) Divide: 문제를 하나 또는 둘 이상으로 나눈다. Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다. 이진 탐색 Divide: 리스트를 두 개의 서브 리스트로 나눈다. Comquer 검색할 숫자 (search) > 중간값 이면, 뒷부분의 서브 리스트에서 검색할 숫자를 찾는다. 검색할 숫자 (search) < 중간값 이면, 앞부분의 서브 리스..

** 순차 탐색(Sequential Search) 데이터가 담겨 있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 탐색: 여러 데이터 중에서 원하는 데이터를 찾아내는 것 ** 프로그래밍 연습 임의 리스트가 다음과 같이 rand_data_list로 있을 때, 원하는 데이터의 위치를 리턴하는 순차탐색 알고리즘 작성해보기 (원하는 데이터가 없을 경우, -1 리턴) # 데이터 준비: data_list 10개 만들기 from random import * rand_data_list = list() for num in range(10): rand_data_list.append(randint(1, 100)) # 10개의 데이터가 무작위로 생성 - 코드 작성 부분 def sequencial(data_l..

** 병합 정렬(Merge sort) 재귀 용법과 분할 정복 알고리즘을 활용한 정렬 알고리즘 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 분할 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병 VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) 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 t..

** 퀵 정렬(Quick sort) 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수가 필요 각 왼쪽, 오른쪽은 재귀 호출을 통해 위 작업을 반복함 함수는 [왼쪽] + 기준점 + [오른쪽]을 리턴함 ** 구현 def qsort(data): if len(data) data[index]: left.append(data[index]) else: right.append(data[index]) return qsort(left) + [pivot] + qsort(right) - 파이썬 list comprehension을 사용해서 더 깔끔하게 작성 def qsort(data): if len(data) item ] right = [ item for item in data[..

동적 계획법(Dynamic Programming, DP)작은 부분 문제들을 해결한 후, 해당 부분 문제들의 해를 활용하여 보다 큰 부분 문제를 해결하면서, 최종적으로 전체 문제를 해결하는 알고리즘「상향식 접근법」으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식Memoization 기법을 사용함Memoization(메모이제이션)이란?: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨예: 피보나치 수열분할 정복(Divide and Conquer)문제를 나눌 수 없을 때까지 나누어서, 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘「하..

** 재귀 용법(Recursive Call, 재귀 호출) 함수 안에서 동일한 함수를 호출하는 형태 ** 예제 팩토리얼을 구하는 알고리즘 분석: 규칙이 보임 n! = n * (n-1)! def factorial(num): if num > 1: return num * factorial(num - 1) else: return num ** 예제: 시간 복잡도와 공간 복잡도 factorial(n) 은 n - 1 번의 factorial() 함수를 호출해서, 곱셈을 함 일종의 n-1번 반복문을 호출한 것과 동일 factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨 시간 복잡도/공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n) ** 재귀 호출의 일반적인 형태 # 일반적인 형태1 def functi..