위상 정렬 Topological Sort
위상정렬이란?
유향 그래프의 정점들을 선형으로 나열하되, 모든 정점들의 등장 순서가, 간선들이 가진 방향의 순서릴 지키도록 나열하는 알고리즘입니다. 예를 들어 여러 작업들이 존재하는데, 몇몇 작업은 특정 다른 작업보다 먼저 수행되어야 할 경우(의존성), 그 순서를 지킬 수 있는 방법을 구하는 알고리즘입니다.
위상정렬 특징
DAG(사이클이 존재하지 않는 방향 그래프)에서만 수행 가능합니다.
위상 정렬의 시간 복잡도
O(V+E) //V : Vertax(정점) E : Edge(간선)
위상정렬 예시 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class TopologicalSort {
private List<List<Integer>> adjList;
private int nodes;
public void topologicalSort() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer infoToken = new StringTokenizer(reader.readLine());
// 정점 갯수 기록
nodes = Integer.parseInt(infoToken.nextToken());
// 간선 갯수 기록
int edges = Integer.parseInt(infoToken.nextToken());
adjList = new ArrayList<>();
// 인접 리스트 초기화
for (int i = 0; i < nodes; i++) {
adjList.add(new ArrayList<>());
}
// 그래프 입력받기
for (int i = 0; i < edges; i++) {
StringTokenizer edgeToken = new StringTokenizer(reader.readLine());
int start = Integer.parseInt(edgeToken.nextToken());
int end = Integer.parseInt(edgeToken.nextToken());
adjList.get(start).add(end);
}
}
// nodes: 정점의 갯수, adjList: 인접 리스트
private void kahn(){
// 1. 진입 차수를 구한다.
int[] inDegrees = new int[nodes];
// List<Integer> neighbors: 각 정점에서 도달할 수 있는 정점들 리스트
for (List<Integer> neighbors: adjList){
// neighbor: 그 정점에서 도달 가능한 정점들 (개별)
for (int neighbor : neighbors) {
// 그들의 진입 차수를 높여라
inDegrees[neighbor]++;
}
}
// 2. 진입 차수가 0인 정점을 Queue에 삽입
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < nodes; i++) {
if (inDegrees[i] == 0) queue.offer(i);
}
List<Integer> result = new ArrayList<>();
// 3. Queue가 비어있지 않는 동안
while (!queue.isEmpty()){
// 3-1 이번 정점 기록
int node = queue.poll();
result.add(node);
// 3-2 현재 정점의 인접 정점들의 진입 차수를 줄인다.
for (int neighbor: adjList.get(node)){
inDegrees[neighbor] --;
// 3-3 진입 차수가 0이 되면 방문 가능(Queue에 삽입)
if (inDegrees[neighbor] == 0)
queue.offer(neighbor);
}
}
// 4. 결과 확인, 실제 정점 갯수보다 위상정렬 정점갯수가 적으면 불가하다!
if (result.size() < nodes){
System.out.println(new ArrayList<>());
}
else System.out.println(result);
}
public static void main(String[] args) throws IOException{
new TopologicalSort().topologicalSort();
}
}
Depth First Search 기반 위상정렬
1. 각 정점을 시작 정점으로 DFS 진행
2. DFS를 진행하며 한 정점에 도착할 때, 해당 정점 방문 기록
1. 재귀적으로 방문하지 않은 모든 인접 정점 방문 (DFS)
2. 더이상 방문하지 않은 인접 정점이 없을 경우, 해당 정점을 기록
3. 모든 정점을 다 검사한 뒤, 기록된 정점을 뒤집으면 위상 정렬의 결과
이때, DFS 탐색 중 아직 인접 정점이 남은, 이미 방문했던 정점을 다시 만난다면, 순환 구조가 존재하기 때문에 위상 정렬이 불가하다는 의미
- 방문 기록과, 과정 기록이 동시에 이뤄져야 함
- boolean[] visited; && boolean[] inProcess
RDS MySQL
지금까지 수업과 실습에서는 SQLite를 사용하여 실습을 진행했는데, 이번에는 AWS의 RDS 서비스를 이용해 MySQL 데이터베이스를 구성하고, MySQL Workbench를 이용해 접속해 봅시다. 이후 MySQL Workbench의 기능을 활용해 MySQL 데이터베이스에 추가 스키마를 구성, 사용자 정보를 새로 구성해 애플리케이션 별로 스키마와 사용자를 별도로 관리해 봅시다.
AWS RDS 생성하기
- Mysql workbench 사용
- AWS RDS 사용 (프리티어 가능)
실습
1. AWS에서 'RDS' 검색 후 이동 한 뒤, 데이터베이스 생성을 누른다.
2. 데이터베이스 생성 방식 선택 : 표준생성, MySQL을 선택한다.
3. 템플릿: 프리티어로 선택한다.
4. 설정 : DB 인스턴스 식별자에 각자 DB 이름을 작성해준다.
마스터 사용자 이름으로 admin을 선택하여 작성했다.
단, 마스터 암호는 기억할 수 있는 값으로 작성한다.
5. 인스턴스 구성 : db.t3.micro를 사용한다.
6. 스토리지 : 스토리지는 20GIB로 해주고 무조건! 스토리지 자동 조정 활성화에 체크를 해제한다!
7. 연결 : EC2 컴퓨팅 리소스에 연결안함을 선택하고 퍼블릭 엑세스도 예를 선택해준다.
8. 추가 구성 : 데이터베이스 포트는 3306포트로 지정해주었다.
9. 백업 : " 자동백업을 활성화 합니다" 체크를 해제해준다!!!
암호화 : 암호화 활성화를 선택한 뒤 데이터 베이스 생성을 한다.
10. 데이터베이스를 시작한다.
11. 데이터베이스가 생성되었으면 접속 권한 설정을 진행한다.
새로 생성된 데이터베이스 항목의 DB식별자를 클릭한다.
아래와 같은 창이 나오면, "보안" 항목의 VPC 보안 그룹, default 링크를 클릭한다.
아래와 같은 창이 나오면 인바운드 규칙 편집을 선택한다.
이후, 사용자 지정 TCP(또는 MYSQL/Aurora), 포트범위는 3306, 소스는 내 IP 또는 Anywhere - IPv4를 선택한다.
다시 database - 1 창으로 돌아가서, 연결 & 보안 항목을 살핀다.
여기에서 엔드 포인트 및 포트에서 엔드포인트를 확인한다.
12. 이제 생성한 RDS를 MySQL Workbench에 연결해보자.
접속 후 +버튼을 눌러서 새로운 DB를 생성해준다.
위에서 확인한 엔드포인트는 MySQL Workbench에서 Hostname에 입력하고,
포트 번호는 Port에 입력한다.
Username : 아까 생성시 작성했던 'admin'으로 바꿔준후
Password: 각자 지정한 비밀번호를 입력해준 뒤 'OK'를 눌러준다.
13. MySQL Workbench 접속 화면 -> 이렇게 나온다면 RDS와 MySQL Workbench가 잘 연결된 것이다.
추후 SQL 명령을 통해 스키마와 테이블을 생성하면 된다.
