동적 계획법 ( Dynamic Programming ) 이란? - 문제의 일부분을 풀고 그 결과를 재활용하는 방법 - 하나의 문제를 중복되는 서브문제로 나누어 푸는 방법 - DP는 분할정복에 아래 개념이 추가됨 중복된 ( 반복되는 ) 서브문제 ( Overlapping Subproblems ) 최적 부분 구조 ( Optimal Substructure ) - DP에 두 가지 방법론이 존재함 메모이제이션 ( 하향식 방법 ) : 메인무제를 분할하면서 해결을 하는 법 def memo_fib(input_value, save_memo): if input_value < 3: save_memo[input_value] = 1 if input_value in save_memo: return save_memo[input_va..

BFS ( Breadth - First Search, 너비우선탐색 ) 이란? - BFS는 큐의 개념이 사용됨 노드 ' S ' 부터 저장되고 사용됨 ( FIFO ) 순서 : S -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 - BFS ( 너비우선탑색 ) 은 노드가 적은 경우 최단경로를 탐색할 때 유용함 - 너비우선적으로 노드를 탐색하는 경우, 큐를 활용하므로 노드가 많아지는 경우 메모리 저장공간이 증가하는 단점이 있음 - BFS는 재귀적으로 동작하지 않는데, 인접한 노드에 대해 먼저 탐색을 하기 때문에 재귀적으로 재호출할 필요가 없음 DFS ( Depth - First Search, 깊이우선탐색 ) 이란? - DFS는 스택의 개념이 사용됨 LIFO 순서 : 1 -> 2 -> 4 -> 5 -..

그래프 ( Graph ) 란? - 노드 간에 연결될 수 있다는 점을 제외하고는 트리와 비슷하며, 루프를 형성할 수도 있음 - 트리에서는 노드를 탐색하는 경우 제한이 있지만, 그래프는 루프형성이 가능하기 때문에 다른 범위의 개념으로 필요한 자료구조 - 그래프는 기본적으로 Vert ( 노드 또는 정점 ) 와 Edge ( 간선 ) 으로 연결되어 있음 ▶ 그래프의 유형 - 그래프의 특성은 방향성 ( Directed ) 또는 무방향성 ( Undirected ) 그래프가 있음 ■ 순환 및 비순환 그래프 ( Cyclic and Acyclic Graphs ) - 순환 ( 루프 ) 을 형성할 수 있는 경우 그래프는 순환 그래프임 - 무방향성 ( Undirected ) 그래프는 항상 동일한 노드에 재방문할 수 있으므로 순..

해시테이블이란? - 해시테이블은 키를 활용하여 값에 직접 접근이 가능한 구조 - 해싱의 장점 : 데이터 양에 영향을 덜 받으면 성능이 빠름 ( 키를 통해 값을 검색함 ) - 파이썬의 딕셔너리는 내부적으로 해시테이블 구조로 구현되어있음 - 해시테이블은 검색을 위한 역할도 하고, 딕셔너리를 위한 자료구조의 역할도 함 - 해시테이블은 키를 빠르게 저장 및 검색할 수 있는 테이블형태의 자료구조 - 해시함수는 여러 키를 분할하기 위해 키를 해시값 ( 정수값 ) 으로 매칭시키는 역할 - 해싱 ( Hashing ) 은 쉽게 말해서 다 흩뜨려놓고, 키와 매칭되는 값을 검색하는 과정 class hash_table: def __init__(self): self.table = [None for _ in range(256)]..

분할정복을 활용한 알고리즘 ▶ 분할 정복 ( Divide and Conquer ) - 복잡하거나 큰 문제를 여러 개로 나눠서 푸는 방법 - 재귀호출은 같은 함수코드를 재호출하는 것 ( 같은 함수코드 사용 ) - 분할정복은 비슷한 작업을 재진행하는 것 ( 같은 함수코드는 아닐 수 있음 ) ■ 분할정복의 과정 본 문제를 서브문제로 분할 ( Divide ) 서브문제의 답을 구한 경우, 해당 답을 본 문제에 대한 답이 되도록 병합함 ( Merge ) 문제를 분할할 수 없거나, 할 필요없는 경우에 대한 답을 구함 ( Base case, 기본 케이스 ) ■ 분할정복의 조건 본 문제를 서브문제로 분할할 수 있는가? ( Divide ) 서브문제의 답을 병합 ( 또는 조합 ) 하여 본 문제의 답을 구하는 것이 효율적인가..

선형 및 이진검색 ▶ Linear Search ( 선형 검색 ) - 선형 검색은 기본적인 검색 알고리즘으로 한 번에 하나씩 모두 검색하는 것 ▶ Binary Search ( 이진 검색 ) - 반복을 통해 숫자를 반으로 줄이면서 검색을 진행하기 때문에 속도가 더 빠름 - 이진 검색 방법은 데이터가 이미 정렬된 경우에만 작동 반복 정렬 ( Iteratibe Sorting ) ▶ 선택 정렬 ( Selection Sort ) - 최소노드 선택 -> 왼쪽부터 비교 -> 교환 - 선택정렬은 가장 작은 노드 ( 최소값 ) 를 선택하고 왼쪽부터 정렬을 하기 위해 알맞은 위치와 교환하는 작업을 반복하는 것 - 시간 복잡도 : O(n^2) def selection_sort(li): for i in range(len(li)..