전체 글
Connected Components 적어도 한 개 이상의 경로로 연결된 정점들로 구성된 종속 그래프이다. connected components는 단순히 연결되었는지 아닌지만 판단하면 되기 때문에 BFS나 DFS로 찾을 수 있다. ( Search가 가능하면 연결된거니까) 2023.06.13 - [Computer Science/Data structure & Algorithm] - [Algorithm] BFS, DFS [Algorithm] BFS, DFS 그래프를 탐색하는 대표적인 방식에는 BFS와 DFS가 있다. 그래프 관련 알고리즘, 동적 프로그래밍 등 다양한 알고리즘 과정에서 응용된 형태로 많이 사용하기 때문에 알고리즘 공부를 할 때에는 mobuk.tistory.com Strongly Connected..
그래프를 탐색하는 대표적인 방식에는 BFS와 DFS가 있다. 그래프 관련 알고리즘, 동적 프로그래밍 등 다양한 알고리즘 과정에서 응용된 형태로 많이 사용하기 때문에 알고리즘 공부를 할 때에는 필수적으로 알고 있어야 하는 개념이다. 원래 귀찮아서 글을 안썼는데 알고리즘 시험 범위에 들어가있어서 이번 기회에 정리했다. BFS (Breadth First Search) 너비우선탐색 : 임의의 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법 Queue를 이용하여 구현한다. 과정 q와 visitied을 이용해 구현할 것이다. - q : 다음 방문할 노드를 담아두는 자료구조 - visited : 노드의 방문 여부를 기록해두는 곳 -> visited를 사용하지 않으면 무한 루프에 돌 수 있다. 시작 정점을 q에 삽입..
그래프 정의 G = (V, E) V : 공집합이 아닌 유한한 정점의 집합 E : 유한한 edge들의 집합. 그래프 종류 방향성에 따른 분류 Undirected Graph 방향성이 없는 그래프 (u, v) = (v, u) Directed Graph 방향성이 있는 그래프 != 위 사진의 a, b가 undirected이고 c가 directed이다. 순환성에 따른 분류 Cyclic Graph 시작과 끝이 동일한 path가 있는 그래프 Acyclic Graph 순환할 수 없는 그래프 (tree가 대표적인 acyclic graph이다.) 가중치에 따른 분류 Unweighted Graph edge에 가중치가 없는 경우 Weighted Graph edge에 가중치가 있는 경우 / 인접 행..
다양한 DCNN 구조에 대해 간단하게 살펴보겠다. 아래에서 살펴볼 4개의 모델들은 ILSVRC(ImageNet Large Scale Visual Recognition Challenge)라는 대회에서 만들어진 모델이다. 2010년부터 2017년까지 진행되었으며 이 대회는 DCNN에 큰 혁신을 일으켰다. AlexNet (2012) 최초로 DCNN 구조를 사용한 방식이다. 이 방식이 기존의 ML 방식을 크게 뛰어넘게 되고, 이후의 방법에도 큰 영향을 주었다. 구조 5개의 convolution 층과 3개의 FC 층이 있다. 커널을 11*11,5*5,3*3 형태를 사용하였다. 특징 활성화 함수롤 ReLU 처음 사용 FC layer 사이에 dropout 사용 데이터 증강 기법 사용 Batch size 는 128 V..
생성 모델 주어진 학습 데이터를 기반으로 해당 분포에서 새로운 샘플을 생성한다. 우리는 P_model(x)를 얻어서 새로운 x를 샘플링하는 것이 목적이다. 명시적(explicit) 밀도 추정 : P_model(x) 를 명시적으로 정의하고 찾아내는 방법 암시적(implicit) 밀도 추정 : P_model(x)를 명시적으로 정의하지 않고도 샘플링 할 수 있는 모델을 학습하는 방법 화소를 독립적으로 생각하여 이미지를 생성하는 모델 확률적 생성모델 화소 별로 확률을 파악해 랜덤으로 생성한다. 화소별로 학습해 생성한 결과는 그리 좋지 않게 보인다. 그래서 뒤쪽에 나오는 오토인코더나 GAN 등이 만들어졌다. 화소가 서로 독립적이지 않다고 생각하는 모델 PixelRNN 순환 신경망을 이용하여 생성하는 방법 새롭게 ..
강화 학습 보상 또는 페널티와 같은 피드백으로 에이전트의 학습 과정을 돕는 방법 강화학습과 지도학습의 비교 지도 학습 (신경망) 강화 학습 문제(데이터) 훈련 집합 X와 Y 환경 또는 환경에서 수집한 데이터 최적화 목표 o 과 y의 오차인 |o-y| 최소화 누적 보상 최대화 학습 알고리즘이 알아내야 하는 것 오차 최소화하는 신경망의 가중치 누적 보상을 최대화하는 최적 정책 품질을 평가하는 함수 손실함수 가치함수 학습 알고리즘 SGD 동적 프로그래밍, Salsa, Q러닝, DQN 등 탐사형 정책과 탐험형 정책 에이전트가 주어진 state에서 어떤 action을 선택할지 결정하는 규칙이나 전략 탐사형 정책 (exploitation policy) 이미 알려진 영역이나 분야를 더 자세히 조사하고 연구하는 과정 ..
시계열 데이터 시계열 데이터란? 시간 축을 따라 신호가 변하는 동적 데이터 심전도, 주식, 음성인식 등이 있다. 시계열 데이터 특성 요소의 순서가 중요하다. (time dependency) 샘플의 길이가 다르다. 문맥 의존성 (context dependency) 를 가진다. 계절성(seasonality)을 가지는 데이터가 있다. 시계열 데이터 표현 (가변길이, 벡터의 벡터로 구성) 시계열 데이터 구조 윈도우 크기 (w) : 문제의 이전 요소를 얼마나 볼 것인가? 수평선 계수 (h) : 얼마나 먼 미래를 예측 할 것인가? 데이터가 다중 품목을 표현하고 있을 수도 있다. 다중 채널의 데이터는 벡터의 벡터 구조로 표현하면 된다. X1 = ((34,12), (35,10), (36,8)) Y1 = (35, 15)..
https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다...
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작..
최단 경로 문제 (Shortest path problem) 가중치가 있는 그래프에서 한 정점에서 다른 정점까지 갈 수 있는 최단 경로를 구하는 문제이다. s 에서 t로 갈 때 지나가는 경로 상에 있는 cost의 합이 최소화 되는 경로를 찾는 경우이다. 최단경로 문제는 Internet packet routing, flight reservation, driving directions 등 다양한 경우에 사용된다. 최단경로 문제를 해결하는 방법은 여러가지가 있는데 그 중에 대표적인 것은 아래 세 가지이다. 다익스트라 알고리즘 (Dijkstar's algorithm) 플로이드-와샬 알고리즘 (Floyd Warshall algorithm) 벨만 포드 알고리즘 (Bellman Ford algorithm) 오늘은 이 ..
