전체 글

단절점(Articulation Point), 단절선(Articulation Bridge)

단절점(Articulation Point)이란? 하나의 컴포넌트로 구성된 무방향 그래프에서 특정 정점을 제거했을 때 두 개 이상의 컴포넌트로 나눌 수 있는 정점을 단절점이라고 한다 아래의 그래프에서 하이라이트된 정점들이 A-point이다 단절점 구하는 방법 단절점을 구하기 위해서는 먼저 단절점의 특성에 대해 알아야 한다. 어느 한 정점이 단절점이라면, 단절점에 바로 인접해 있는 정점들의 쌍은 단절점이 없으면 우회로로 인해 연결되어 있지 않아야 한다 예를 들어 5번 정점이 단절점이라고 생각해보자. 5번 정점을 제거하더라도 인접노드인 4, 6을 우회로(4-8-6)로 연결되어 있으므로 5번은 단절점이 될 수 없다 이번에는 4번 정점이 단절점이라고 생각해보자 4번 정점을 제거하게 되면 (2,3) 과 (5,8)은..

세그먼트 트리 Segment Tree

세그먼트 트리란? 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터 합을 빠르고 간단하게 구할 수 있는 자료구조 세그먼트 트리에서 노드들의 의미 리프 노드 : 배열의 구 수 자체 리프 노드를 제외한 다른 노드 : 왼쪽 자식과 오른쪽 자식의 최솟값 또는 합을 저장 n = 10인 경우 세그먼트 트리는 다음과 같다 트리 만들기 세그먼트 트리는 포화 이진 트리에 가깝기 때문에 배열에 모든 값이 대부분 가득 차게 됨 따라서 배열로 트리를 만들어 사용 이 경우 임의의 노드의 인덱스가 i일 때 왼쪽 자식의 인덱스는 2*i 오른쪽 자식의 인덱스는 2*i + 1 세그먼트 트리의 구현(C++) #include #include #include using namespace std; // arr : intial a..

강한연결요소 : Strongly Connected Component

강한연결요소 : Strongly Connected Component Concept 방향 그래프 G의 임의의 노드 쌍 u,v에 대해 u->v, v->u로 가는 경로가 존재하면 G는 Strongly Connected 되었다고 한다 따라서 G의 u->v 로 가는 경로가 있을 때, 엣지의 방향을 정반대로 바꾼 transpose G에도 u->v로 가는 경로가 있다면 두 노드 사이에 사이클이 있어 SCC를 만족한다 Kosaraju's Algorithm #include #include #include #include #define MAX 10001 using namespace std; int n, out_len; bool check[MAX], check2[MAX]; vector r[MAX], r2[MAX]; stac..

위상 정렬 Topological Sort

위상 정렬(Topological Sort)이란? 정렬 기준이 '위상'으로 여기서 위상이란 진입차수(incoming edge의 수)를 의미한다 위상 정렬의 특징 - Directed Acyclic Graph(DAG)에서만 가능 - 즉, 방향을 가지며 싸이클은 형성하지 않는 그래프를 말한다 - 보통 일의 순서를 정하는 알고리즘에서 많이 사용됨 위상 정렬 알고리즘 각 노드의 위상(incoming edge의 수)를 저장 위상이 0인 노드를 큐에 푸쉬 큐가 빌 때까지 아래 과정 반복 큐에서 노드를 꺼내 해당 노드와 연결된 노드의 간선을 모두 제거(동시에 연결된 노드의 위상을 하나씩 낮춰줌) 큐에서 꺼낸 노드를 위상정렬에 넣어줌 위상이 0인 노드를 큐에 푸쉬

[이론] 우선순위 큐 (Priority Queue)

우선순위 큐란? 일반적인 큐는 선입선출(FIFO) 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 되는데, 우선순위 큐는 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 된다 우선 순위 큐는 최소 우선 순위, 최대 우선 순위 2가지로 구분할 수 있다 최소 우선순위 큐 : 가장 우선 순위가 낮은 요소를 삭제 최대 우선순위 큐 : 가장 우선 순위가 높은 요소를 삭제 스택 vs 큐 vs 우선순위 큐 자료구조 삭제되는 요소 스택 가장 최근에 들어온 데이터 큐 가장 먼저 들어온 데이터 우선순위 큐 가장 우선순위가 높은 데이터 우선순위 큐의 추상 자료형(ADT) 객체 : n개의 element형의 우선순위를 가진 요소들의 모임 연산 create() ::= 우선순위 큐를 생성 init(q) ::..

[이론] 힙(Heap)

힙(Heap)란?여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조로  최대 힙(max heap)와, 최소 힙 (min heap)두 가지 종류로 나뉘게 된다최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 최대 힙과 최소 힙은 항상 아래의 조건이 성립하게 된다최대 힙 : $key(부모노드) >= Key(자식노드)$최소 힙 : $key(부모노드)  힙의 특징힙의 목적은 삭제 연산이 수행될 때마다 가장 큰/작은 값을 찾아내기만 하면 된다(가장 큰/작은 값은 루트 노드에 있음) 따라서 힙 안에서 데이터들은 느슨한 정렬 상태를 유지한다 즉, 전체 데이터를 정..

[ML] 모델 성능을 측정하는 네가지 지표

기계학습(ML : Mahine Learning) 모델의 성능을 측정하는 통계적 지표로는 다음과 같이 네 가지 종류가 존재한다 인식 성능 측정 Accuracy: 정확도 혼동 행렬(Confusion Matrix)을 이용한 방식 (또는 오차행렬이라고 부름) Recall : 재현율 Precision : 정밀도(정확율) F1-score : Recall, Precision의 산술평균 각 지표에 대한 공식을 알아보도록 하자 인식 성능 측정 Accuracy (정확도) 가장 보편적으로 간단하게 성능을 측정하는 방법으로 공식은 아래와 같다 Accuracy = (올바르게 예측된 데이터 수) / (전체 데이터 수) Accuracy의 문제점 데이터에 따라 매우 잘못된 통계 결과가 나올 수 있는데 예로 y label이 심각한 불..

경사하강법과 손실함수

선형 회귀(Linear Regression) 선형 회귀는 머신러닝 알고리즘 중 가장 간단하면서도 딥러닝의 기초가 되는 개념이다 1차 함수로 이해하는 선형 회귀 $y=ax+b$ : 선형 회귀는 1차 함수로 표현 가능하다. 위와 같이 1차 함수의 기울기(slope)는 a이고, 절편(intercept)은 b이다 선형 회귀는 기울기와 절편을 찾는 것이 목표 고등과정에서 배운 1차 함수의 경우 x에 따른 y값을 찾는데 집중한 반면, 선형 회귀에서는 이와 반대로 x, y가 주어졌을 때 기울기 a와 절편 b를 찾는데 집중한다. 그래프를 통한 선형 회귀의 문제 해결 과정 이해 그래프에 찍힌 (x,y)좌표로 기울기와 절편을 추정하여 1차 함수를 추정해내는 것으로 선형 회귀로 만든 모델 또한 이런 모델을 통해 새로운 점에..