알고리즘 스터디

** > ### 그래프 = node + edge node: 데이터를 표현하는 단위 edge: 노드를 연결해줌 그래프 알고리즘 1. 유니온 파인드 그래프의 사이클이 생성되는지를 판별하는 알고리즘 2. 위상 정렬 조건 i) 사이클 X (전-후 관계가 있음)

= 모든 Node와 Edge를 한 번씩 지정된 순서로 방문Graph Traversal 종류1\. 깊이 우선 탐색 (DFS: Depth First Search)2\. 너비 우선 탐색 (BFS: Breath First Search)=> 그래프에서 깊은 부분을 우선적으로 탐

신장 트리(Spanning Tree)란? 모든 임의의 정점이 연결된 그래프인 연결 그래프의 부분 그래프다. 모든 정점이 간선으로 연결되어 있지만 사이클이 존재하지 않은 그래프다. Minimum Spanning Tree(MST) 최소신장트리란? 무방향 연결 그래프에

가능한 모든 경우의 수를 무식하게 (=brute-force) 전부 탐색해서 정답을 찾는 방법일종의 완전 탐색 기법으로, 문제 해결을 위해 조건을 만족하는 모든 조합이나 경우를 일일이 검사함직관성구현이 매우 단순하고 직관적임정확도정답을 반드시 찾을 수 있음(단, 경우의

greedy : 탐욕스러운, 욕심 많은최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘입니다.이때, 항상 최적의 값을 보장하는것이 아니라 최적의

복잡한 문제를 작고 단순한 문제로 나눈 후, 각각을 해결하고 다시 합쳐서 전체 문제를 푸는 알고리즘 설계 기법1\. Divide (분할)문제를 더 작은 부분 문제(subproblem)로 나눈다.2\. Conquer (정복)분할된 작은 문제를 재귀적으로 해결한다.충분히

(=복잡한 문제를 작은 하위 문제로 나누어 푸는 방식)큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말1\. 중복되는 부분 문제 (Overlapping Subproblems)전체 문제를 해결하는 과정에서 같은 하위 문제가 반복해서 등장한다.예를 들어, 피보나치 수열에