본문 바로가기

ALL

[BOJ] 백준 1916번 최소비용 구하기 (Java)
Dot Algo∙ DS/PS 2021. 4. 29. [BOJ] 백준 1916번 최소비용 구하기 (Java) #1916 최소비용 구하기 난이도 : 골드 5 유형 : 그래프/ 최소비용(Dijkstra) / 우선순위 큐 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net ▸ 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. ▸ 입력 첫째 줄에 도시의 개수 ..
[BOJ] 백준 2644번 촌수계산 (Java)
Dot Algo∙ DS/PS 2021. 4. 28. [BOJ] 백준 2644번 촌수계산 (Java) #2644 촌수계산 난이도: 실버 2 유형 : 그래프 탐색/ DFS / BFS 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net ▸ 문제 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아..
[스프링 웹앱 프로젝트 #42] PostgreSQL 설치 및 Spring 연동
Dot Programming/Spring Clone 2021. 4. 28. [스프링 웹앱 프로젝트 #42] PostgreSQL 설치 및 Spring 연동 1. Mac에 PostgreSQL 설치 및 설정 PostgreSQL (Postgres.app) 설치 (for mac) 1. 설치 방법 1) Postgres.app 2) Homebrew 3) MacPorts 4) Fink 3,4 번은 처음 보는 것들이라 몸르겠고 1번과 2번중 간단하고 직접적으로 설치가 가능한 Postgres.app 방법을 선택. 이런 프로그램을 받을 때 버.. loosie.tistory.com 2. Spring Project 개발환경에 설정 1) DB와 유저(role) 만들고 유저에게 권한 할당하기 create database testdb; create user testuser with encrypted password 'testpass'; grant all privileges on da..
Mac OS에서 PostgreSQL (Postgres.app) 설치 및 사용법 정리
Dot ./개인 공부 기록용 2021. 4. 28. Mac OS에서 PostgreSQL (Postgres.app) 설치 및 사용법 정리 1. 설치 방법 설치 방법으로는 총 4가지가 있다. Postgres.app Homebrew MacPorts Fink 3,4 번은 처음 보는 것들이라 패스하고 1번과 2번중 간단하고 직접적으로 설치가 가능한 Postgres.app 방법을 선택했다. 이런 프로그램을 받을 때 버전은 latest release 보다는 검증이 된 이전 버전 additional release을 받는 것을 더 선호한다. (최신버전은 구버전보다 오류가 있을 가능성이 높음) 2. Postgres.app 설치 프로세스 코끼리를 응용프로그램 드래그 후 설치 완료하면 상단 바에 코끼리가 뜬다. 코끼리 > open postgres > start 했을 때 초록색 체크 표시와 함께 running이 뜨면 성공 2-1. $PATH 설정하기 (.zsh..
[알고리즘/ 그래프] 벨만 포드 알고리즘 (Bellman-Ford Algorithm) (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 4. 25. [알고리즘/ 그래프] 벨만 포드 알고리즘 (Bellman-Ford Algorithm) (Java) 최단경로 알고리즘 최단 경로 문제는 다음과 같이 분류할 수 있다. 모든 간선이 양수인 경우 음수 간선이 있는 경우 음수 간선 순환은 없는 경우 음수 간선 순환이 있는 경우 위의 분류를 3가지 알고리즘을 통해 구할 수 있다. 벨만포드 알고리즘 (Bellman-Ford Algorithm) → 2-1),2-2) 음수 간선이 있는 경우 다익스트라 알고리즘(Dijkstra Algorithm) → 1)모든 간선 양수 플로이드 와샬 알고리즘(Floyd-Warshall Algorithm) → 1)모든 간선 양수 벨만포드 알고리즘 벨만포드 최단 경로 알고리즘은 음수 간선이 포함된 상황에서의 최단 거리 문제를 풀 때 사용할 수 있다. 또한, 음수 간선의 순환을 감지할 수 있다. 동작 과정 출발 노드를 설정한다. (to, ..
[알고리즘/ 그래프] 위상 정렬 (topology Sort) (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 4. 23. [알고리즘/ 그래프] 위상 정렬 (topology Sort) (Java) 위상 정렬 사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 진입 차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출 차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 큐를 이용하는 위상 정렬 알고리즘의 동작 과정 진입차수가 0인 모든 노드를 큐에 넣는다. 큐가 빌 때 까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. ☞ 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다. 위상 정렬 특징 위상 정렬은 DAG에 대해서만 수행할 수 있다. DAG(Direct Acyclic Graph) : 순환하지 않는 방향 그래..
[스프링 웹앱 프로젝트 #33~41] 관심주제/ 지역정보 (Tag) 기능
Dot Programming/Spring Clone 2021. 4. 23. [스프링 웹앱 프로젝트 #33~41] 관심주제/ 지역정보 (Tag) 기능 1. 관심 주제 도메인 관심 주제 (Tag)는 엔티티인가? 도메인인가? Tag 독자적인 라이프사이클이 있고 다른 곳(Study)에서도 참조할 것이기때문에 엔티티이다. @Entity @Getter @Setter @EqualsAndHashCode(of = "id") @Builder @AllArgsConstructor @NoArgsConstructor public class Tag { @Id @GeneratedValue private Long id; @Column(unique = true, nullable = false) private String title; } Tag 엔티티 관계 구현코드 github.com/loosie/spring_jpa_study__dotStudy/commit/13235f8686fc27..
[알고리즘/ 그래프] 최소 스패닝 트리 - 크루스칼(Kruskal)과 프림(Prim) 알고리즘 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 4. 22. [알고리즘/ 그래프] 최소 스패닝 트리 - 크루스칼(Kruskal)과 프림(Prim) 알고리즘 (Java) 스패닝 트리 또는 신장 트리 어떤 무향 그래프의 스패닝 트리는 원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다. 이때 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 한다. 트리 형태여야 한다는 말은 선택된 간선들이 사이클을 이루지 않는다는 뜻이며, 정점들이 꼭 부모-자식 관계로 연결될 필요는 없다는 데 유의하자. 즉, 스패닝 트리는 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다. 최소 스패닝 트리 (MST) 최소 스패닝 트리란 최소한의 비용으로 구성되는 스패닝 트리를 말한다. 두 가지 유명한 알고리즘으로 크루스칼과 프림이 있다. 크루..

티스토리툴바

티스토리툴바