데이터과학 삼학년

동적 계획법(DP, Dynamic Programming) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용하여 보다 큰 크기의 부분 문제를 해결 위 단계를 반복하며 전체 문제를 해결하는 알고리즘 상향식 접근법으로, 가장 최하위 해답을 구한 후 이를 저장해 다음 결과값을 풀어나가는 방식 Menoization(메모이제이션) 프로그램 실행시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 해 실행 속도를 빠르게 하는 기술 예) 피보나치 수열 def fibo_dp(num): cache = [0 for ind in range(num+1)] cache[0] = 0 cache[1] = 1 for ind in range(2, num+1): cache[ind] = cache[ind-1] + c..

DFS(Depth First Search) : 깊이 우선 탐색 - 깊이(종)로 내려가면서 탐색 --> 전수조사 - Stack 의 개념을 사용하여 구현 > [1,2,3,4] --> [1,2,3] --> [1,2] --> [1] > [1,5,6,7] --> [1,5,6] --> [1,5] --> [1,5,8] > [1,9,10] BFS(Breadth First Search) : 너비 우선 탐색 - 너비(횡)로 내려가면서 탐색 --> 일부조사만의 끝날 수 있는 경우 - Queue 의 개념을 사용하여 구현 > [1] > [2,3,4] --> [3,4,5] --> [4,5,6,7] --> [5,6,7,8] > [6,7,8,9] --> [7,8,9,10] 참고 : coding-factory.tistory.com/6..

stack 2개를 이용하면 queue를 만들 수 있다. stack은 LIFO (Last In First Out) queue 는 FIFO (First In First Out) 즉, stack을 두개를 이용해서 빈 스택에 다른 스택을 담고 다시 빼는 식으로 queue를 만들 수 있는 것이다. 구현 코드 예시 # stack 2개로 queue 만들기 class Stack: def __init__(self): self.stack = [] def __repr__(self): return f"{self.stack}" def push(self,item): self.stack.append(item) def pop(self): return self.stack.pop() def is_empty(self): if len(se..

피보나치 수열은 앞의 두개의 숫자를 합한 값이 자신의 value가 되는 수열을 말한다. 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 기초적으로 이런 피보나치 수열을 푸는 알고리즘의 예로 recursive function을 쓰긴 하지만 이는 숫자가 커지면 그만큼 함수의 호출이 많아지므로 메모리가 터지는(?) 문제가 생긴다 def fibonacci(n): if n < 2: return n return fibonacci(n-1) + fibonacci(n-2) 이러한 문제를 해결하기 위해 memoization 을 이용해 (캐쉬와 비슷한 개념) 푸는 접근 방법도 있다. memo = {1:1, 2:1} def fibonacci(n): if n == 0: return 0 if n not in memo..

버블 정렬 두 개의 데이터를 서로 비교 하면서 큰지, 작은지의 여부에 따라 정렬하는 방법 시간복잡도는 O(n^2) 으로 가장 단순하면서 오래걸리는 정렬 방법이다. - 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다. - 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 파이썬 코드 def bubble(lst): for j in range(len(lst..

이진분할로 중간 pivot을 이용해 데이터를 정렬하는 기법 recursion을 이용하면..간단히(?) 풀 수 있다. def quick_sort(arr): if len(arr) pivot: greater_arr.append(num) else: equal_arr.append(num) return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)

계수 정렬 계수 정렬(Counting Sort)는 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘입니다. 각 데이터 를 바로 크기를 기준으로 분류하므로 O(N)의 시간 복잡도를 가집니다. 한마디로 0 부터 정렬하고자 하는 숫자의 최대값 만큼 인덱스를 만들어서 숫자를 count 하고 정렬하는 방식

합병 정렬(merge sort) 알고리즘의 개념 요약 ‘존 폰 노이만(John von Neumann)’이라는 사람이 제안한 방법 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다. 분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 과정 설명 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트..