JUINTINATION

프로젝트 개요 원하는 키워드에 관련된 하루의 뉴스들의 주요 키워드를 추출하여 하나의 워드 클라우드로 만들어주는 웹 서비스 LDA 모델을 이용하여 크롤링한 뉴스에 대한 최적의 토픽 개수를 기반으로 얻은 키워드를 이용한 워드 클라우드 생성기 참여 인원 Back-end : 권덕재(B989003, 스프링 프레임워크를 이용한 웹 개발 및 프론트엔드, 크롤링 보조) Front-end : 이승호(B989037, html5, css3, javascript를 이용한 UI 개발 및 백엔드, 크롤링 보조) Crawling : 김기현(B989009, python을 이용한 크롤링을 비롯한 전처리 및 백엔드, 프론트엔드 보조) 목차 사용 방법 실행 화면과 기능 설명 워드 클라우드 생성 관련 알고리즘 설명 사용 방법 jdk 11,..

프로젝트 개요 원하는 키워드에 관련된 하루의 뉴스들의 주요 키워드를 추출하여 하나의 워드 클라우드로 만들어주는 웹 서비스 LDA 모델을 이용하여 크롤링한 뉴스에 대한 최적의 토픽 개수를 기반으로 얻은 키워드를 이용한 워드 클라우드 생성기 참여 인원 Back-end : 권덕재(B989003, 스프링 프레임워크를 이용한 웹 개발 및 프론트엔드, 크롤링 보조) Front-end : 이승호(B989037, html5, css3, javascript를 이용한 UI 개발 및 백엔드, 크롤링 보조) Crawling : 김기현(B989009, python을 이용한 크롤링을 비롯한 전처리 및 백엔드, 프론트엔드 보조) 목차 사용 방법 실행 화면과 기능 설명 워드 클라우드 생성 관련 알고리즘 설명 사용 방법 jdk 11,..

APSP(All-pairs shortest paths) 알고리즘이란? 어떤 그래프에서 모든 노드(시작 노드)부터 각각의 노드(도착 노드)까지의 모든 최단거리를 구하는 알고리즘이다. 여러 APSP 알고리즘 중에서 2가지를 살펴보겠다. 모든 정점에서 SSSP 알고리즘 실행하기 모든 정점에서 SSSP 알고리즘을 실행해야 하기 때문에 |V| 만큼 시간 복잡도가 증가한다. Dijkstra’s algorithm(음의 간선 X): O(|V||E| + |V|² log |V|) Bellman-Ford algorithm(음의 간선 O, 음의 사이클 X): O(|V|²|E|) DAG Shortest Path using Topological Sort: O(|V|² + |V||E|) 음의 사이클이 존재하지 않는 경우 Floyd..

SSSP(Single-source shortest paths) 알고리즘이란?어떤 그래프에서 시작 노드부터 도착 노드까지의 최단거리를 구하는 알고리즘이다.SSSP 알고리즘은 대표적으로 3가지로 나눌 수 있다.그래프에 음의 간선이 없는 경우Dijkstra’s algorithm: O(|E| + |V| log |V|)음의 사이클이 존재하지 않는 경우Bellman-Ford algorithm: O(|V||E|)DAG(Directed Acyclic Graph, 유향 비순환 그래프)의 경우One pass of Bellman-Ford: O(|V||E|)DAG Shortest Path using Topological Sort: O(|V| + |E|)다익스트라 알고리즘(Dijkstra's Algorithm)dijkstra(..

위상정렬(Topological Sort)이란? 유향 비순환 그래프(DAG, Directed Acyclic Graph)에서 정점을 간선의 방향을 거스르지 않도록 나열하는 알고리즘이다. 다음 라면 끓이기 예제를 보자 우리는 라면을 끓일 때 냄비에 물을 먼저 부어도 되고 라면 봉지를 먼저 뜯어도 되지만 계란은 맨 마지막에 풀어야 한다. 이러한 방향은 있지만 사이클은 없는 그래프를 간선의 방향을 거스르지 않고 한 줄로 정렬시키는 것이 위상정렬이라고 보면 될 것 같다. 위상정렬 알고리즘(1) 진입 간선이 없는 정점을 연결리스트 R의 맨 뒤에 연결하고 해당 정점과 그 정점의 진출 간선을 제거하는 과정을 반복한다. 의사 코드는 다음과 같으며 위의 예시를 구하는 과정은 그 다음 그림과 같다. topological_so..

최소 신장 트리(MST)란? 가중치 그래프에서 사이클 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 즉, 어떤 가중치 그래프의 신장 트리 중 선분들의 가중치 합이 최소인 트리 신장 트리는 그래프에서 사이클 없이 모든 점들을 연결시킨 트리로 주어진 그래프의 신장 트리를 찾으려면 사이클이 없도록 모든 점을 연결시키면 된다. 신장 트리는 그래프에서 사이클 없이 모든 점들을 연결시킨 트리로 그래프의 점이 n개 있다면 신장 트리에는 n-1개의 선분이 있다. 다음 예시에서 왼쪽 그림의 그래프의 최소 신장 트리는 오른쪽 그림의 그래프와 같다. MST를 찾기 위한 알고리즘 최소 신장 트리를 찾는 대표적인 그리디 알고리즘으로는 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리..