얄루의 개발일기🥑

3. DFS in directed graphs 1. DFS tree 엣지의 종류 Tree edge: DFS에 포함되는 엣지 Forward edge: 후손이 아닌 관계로 가는 엣지 Backward edge: 조상으로 가는 엣지 Cross edge: 아무 관계도 아닌 vertex(노드)를 연결하는 관계 2. DAG (Directed Acyclic Graph) DAG는 비순환그래프로 사이클이 존재하지 않고 일방향성만 갖는 것을 의미한다. source: 나가는 엣지만 있는 정점 sink: 들어오는 엣지만 있는 정점 3. DAG 성질 어떤 그래프에 사이클이 있다면 Back edge가 있다. dag의 모든 edge는 더 낮은 post number로 간다. 어떤 DAG는 적어도 하나의 source와 sink를 가진다..

2. DFS in undirected graphs 1. 정의 DFS(Depth-First Search)는 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미한다. 이 알고리즘을 사용해서 풀 수 있는 문제의 경우는 특정 도시에서 다른 도시로 갈 수 있는지 여부를 판단할 수 있고, 또 특정 지역과 지역이 연결되어 있는지 등의 여부를 판단할 수 있다. 2. DFS의 구조(흐름도) # DFS의 경우엔 BFS와 다르게 기준점이 되는 노드에서 우선순위가 높은 노드를 먼저 순회한다. 즉, 제일 깊은 곳까지 갔다가 갈 곳이 없으면 다음으로 넘어가는 것!!!! 3. DFS 사용 스택(Stack) 재귀 함수(recursive) 대표적으로 DFS는 스택과 재귀를 사용해서 구현한다. 또한 DFS는 ..

0. Introduction 1. 정의 그래프란? 몇 쌍의 Object들이 link로 연결된 Object의 집합에 대한 추상적인 표현이다. 개체와 개체간의 일대일 관계를 시각적으로 나타내는 수학적 모델이다 1. what is graph? 2. 그래프의 구성 Vertex: 일반적으로 노드라고 부르는 정점 Edges: 노드들을 이어주는 엣지로 구성 3. 그래프의 종류 undirected graph : {V, W} = {W, V} directed graph : {V, W} ≠ {W, V} 무방향 그래프 방향 그래프 가중치 그래프 가중치 방향 그래프

DFS(Depth First Search-깊이 우선 탐색) ▶ 스택, 재귀를 통한 구현이 가능하다. BFS(Breadth First Search-너비 우선 탐색) ▶ 큐, 덱을 통한 구현이 가능하다. ▶ 최단거리를 구할 때 BFS를 사용하는데 종류는 3가지다. ▶ 다익스트라 알고리즘 - 가장 유명한 최단경로를 구하는 알고리즘으로 단일 정점의 최단 경로를 구할 수 있으며 음의 가중치를 가지고 있을 땐 사용 불가하다. ▶ 플로이드 마샬 알고리즘 - 단일 정점이 아닌 모든 정점 사이의 최단거리를 구할 수 있다. ▶ 벨만 포드 알고리즘 - 음의 가중치를 가진 경로에서도 최단거리를 구할 수 있다. (경로 추적이 가능함) 벨만 포드 알고리즘은 DP(다이나믹프로그래밍)이 사용된다. GREEDY(탐욕법) ▶ 늘 가장 ..

3. Divide & Conquer 3.0 Introduction 3.1 Recurrence relation 3.2 Multiplication 3.3 Sorting 3.4 Medians 3.5 Matrix multiplication 3.1 Recurrence relation Multiplication이란? 곱하기 연산을 의미한다. - 더하기 연산을 하게 될 때 O(n)의 시간복잡도를 갖는다. - 곱하기 연산을 할 때 시간 복잡도는 O(n^2)이다.

3. Divide & Conquer 3.0 Introduction 3.1 Recurrence relation 3.2 Multiplication 3.3 Sorting 3.4 Medians 3.5 Matrix multiplication 3.1 Recurrence relation Recurrence relation이란? 수열의 각 항이 선행 항의 함수로 정의되는 방정식 기본 점화식

3. Divide & Conquer 3.0 Introduction 3.1 Recurrence relation 3.2 Multiplication 3.3 Sorting 3.4 Medians 3.5 Matrix multiplication 3.0 Introduction Divid & Conquer의 핵심 (3단계) Divid - 쪼개기 Conquer – 쪼갠 부분을 재귀적으로 해결하기 Combine(optional) – 쪼갠 것을 합치는 것은 선택적인 사항임 필수가 아니다 3.0 Introduction의 예제 Tournament #Tournament elit8 = ['URG', 'FRA', 'BRA', 'BEA', 'SWE', 'ENG', 'RUS', 'CRO'] def Champion(s, e): if (s ..

0. STL 이란? 1. Vector 2. List 3 Stack/Queue 4. Set 5. Map 6. Example: DFS(Depth first search)/깊이 우선 탐색 7. Python code 0.1 STL이란? STL은 표준 템플릿 라이브러리(STL: Standard Template Library)는 C++을 위한 라이브러리로서 C++ 표준 라이브러리의 많은 부분에 영향을 끼쳤다. 0.2 STL 구성요소 이것은 알고리즘(연산), 컨테이너, 그리고 반복자라고 불리는 세 가지의 구성 요소를 제공한다. 📌출처: https://ko.wikipedia.org/wiki/%ED%91%9C%EC%A4%80_%ED%85%9C%ED%94%8C%EB%A6%BF_%EB%9D%BC%EC%9D%B4%EB%B8%..