🌱 𝐣𝐣𝐢𝐧𝐠𝐥𝐞 𝐝𝐞𝐕𝐥𝐨𝐠

그래프 탐색 알고리즘 너비 우선 탐색 (BFS; Breadth First Search) 정점들과 같은 레벨에 있는 노드들(형제 노드)을 먼저 탐색하는 방식 A - B - C - D - G - H - I - E - F - J 깊이 우선 탐색 (DFS; Depth First Search) 정점의 자식들을 먼저 탐색하는 방식 A - B - D - E - F - C - G - H - I - J

순차 탐색 (Sequential Search) ? - 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미 - 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 data = list() for num in range(10): data.append(randint(1, 100)) #random 라이브러리 def sequencial(data, search_data): for index in range(len(data)): if data[index] == search_data: return index return -1 sequencial(data, 4)

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

병합 정렬(merge sort) ? 재귀 용법을 활용한 정렬 알고리즘 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눔 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병 def merge(left, right): merged = list() left_point, right_point = 0,0 #case1: left/right 둘다 데이터 있을 때 while len(left) > left_point and len(right) > right_point: it left[left_point] > right[right_point]: merged.append(right[right_point]) right_point += 1 else: merged...

퀵 정렬(quick sort) ? 정렬 알고리즘의 꽃 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수 각 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출해 위 작업 반복 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right)을 리턴 def qsort(data): if len(data) data[index]: left.append(data[index]) else: right.append(data[index]) #2.list comprehension 사용 left = [item for item in data[1:] if pivot > item] right = [item for item in data[1:] if pivot

동적 계획법 ( DP; Dynamic Programming) ? 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해 보다 큰 크기의 부분 문제를 해결 상향식 접근법 Memoization 기법 : 프로그램 실행 시, 이전에 계산한 값을 저장하여 다시 계산하지 않도록 함 -> 실행속도 향상 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용됨 -> 피보나치 수열 분할 정복 (Divide and Conquer ) ? 문제를 나눌 수 없을 때까지 나누어서, 각각 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 하향식 접근법 (일반적으로 재귀함수로 구현) 문제를 잘게 조갤 때, 부분 문제는 서로 중복되지 않음 공통점과 차이점 공통점 : 문제를 잘게 쪼개서, 가장 작은 단위로 분할 차이점 동..

재귀 용법(recursive call) ? - 함수 안에서 동일한 함수를 호출하는 형태 - 여러 알고리즘에서 사용 재귀호출의 일반적인 형태 내부적으로 스택(Stack)처럼 관리된다 #case1 def function(입력): if 입력 > 일정 값: # 입력이 일정 값 이상이면 return function(입력 - 1) # 입력 값보다 작은 값 else: return 일정 값, 입력 값, 또는 특정 값 # 재귀호출 종료 #case2 def function(입력): if 입력

정렬 (Sorting) ? - 어떤 데이터들이 주어졌을 때, 이를 정해진 순서대로 나열하는 것 - 정렬은 프로그램 작성 시, 빈번하게 필요 - 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수 버블 정렬(bubble sort) : 두 인접한 데이터를 비교해서, 앞에있는 데이터가 뒤에있는 데이터보다 크면 자리를 바꿈 def bubblesort(data): for index in range(len(data) - 1 ): swap = False for index2 in range(len(data) - index - 1): if data[index2] > data[index2 + 1]: data[index2], data[index2 + 1] = data[index2 + 1], data[index2] swap..

힙과 배열 일반적으로 힙 구현 시, 배열 자료구조 활용 배열은 인덱스 0 부터 시작하지만, 힙 구현의 편의를 위해 root 노드 인덱스 번호를 1로 지정 부모 노드 인덱스(parent node's index) = 자식 노드 인덱스(child node's index) //2 왼쪽 자식 노드 인덱스(left child node's index) = 부모 노드 인덱스(parent node's index) * 2 오른쪽 자신 노드 인덱스(right child node's index) = 부모 노드 인덱스(parent node's index) * 2 + 1 힙과 데이터 삽입(Max Heap) class Heap: def __init__(self, data): self.heap_array = list() self.h..

힙 (Heap) ? 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) - 완전 이진 트리 : 노드를 삽입할 때, 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림