위상 정렬(Topological Sortin) 위상 정렬이란 순서가 있는 작업(방향이 있는)을 차례로 진행해야 할 때 순서를 결정해 주기 위해 사용하는 알고리즘 사이클이 없는 방향 그래프(DAG; Directed Acyclic Graph)의 모든 노드를 주어진 방향성에 어긋나지 않게 순서를 나열하는 것 Ex) 대학 선수과목, 공장의 작업 순서, 요리 순서, ... 등 사전 지식 진입 차수: 특정 노드로 들어오는 간선의 개수 진출 차수: 특정 노드에서 나가는 간선의 개수 위상 정렬 Queue 구현 위상 정렬 방법(Queue 사용) 진입 차수가 0인 모든 노드를 Queue에 삽입 Queue가 공백 상태가 될 때까지 반복 수행 Queue에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 (연결된 노..

교착 상태의 개요 교착 상태의 정의 교착 상태(deadlock) 2개 이상의 작업이 동시에 이루어지는 경우, 다른 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태 교착 상태(deadlock) vs 아사 현상(starvation) 아사 현상 : 잘못된 정책으로 특정 프로세스의 작업이 지연되는 문제 교착 상태 : 여러 프로세스가 작업을 진행하다 보니 발생하는 자연적인 현상 컴퓨터 시스템에서 교착 상태는 시스템 자원을 사용하거나 잠금을 사용할 때 발생할 수 있다. 시스템 자원 교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생 잠금 교착 상태는 잠금을 사용할 때 발생 예시 코드 - 무한 대기를 막지 못해 교착 상태가 발생한 경우 p1이 lock1을 true로 만든 다음 p2가 l..

프림 알고리즘 프림 알고리즘이란? 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 임의의 정점을 선택하여 시작 어짜피 모두 연결되므로 임의의 정점을 선택해도 된다 그러므로 첫 정점(0번 또는 1번)을 고른다 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때까지 2번 과정을 반복 서로소인 2개의 집합 정보를 유지 트리 정점: MST를 만들기 위해 선택된 정점들 비트리 정점들: 선택되지 않은 정점들 프림 알고리즘 의사코드 MST-PRIM(G, r) FOR u in G.V u.key ← ∞ u.p ← NULL r.key ← 0 Q ← G.V WHILE Q != 0 Q ← Extract-MIN(Q) FOR v in G.Adj[u]..

서로소 집합(Disjoint-sets) 상호 배타 집합 중복 포함된 원소가 없는 집합 → 교집합이 없음 각 집합은 대표자를 통해 구분 상호 배타 집합 표현 방법 연결 리스트 트리 연결리스트 배열 상호 배타 집합 연산 Make-Set(x) : 단위집합을 만드는 연산 (초기화 함수) Find-Set(x) : 어떤 한 element가 주어졌을 때, 그 element의 대표자를 구하는 연산 Union(x, y) : 두 구성요소가 주어지고, 그 두 구성요소의 각 상호배타 집합을 합치는 연산 Make-Set / Union / Find-Set 연산 상호 배타 집합 표현 - 연결리스트 같은 집합의 원소들은 하나의 연결리스트로 관리 연결리스트의 맨 앞의 원소를 집합의 대표자로 결정 각 원소는 집합의 대표원소를 가리키는 ..

JDBC JDBC란? Java Database Connectivity, 자바 프로그래밍 언어를 사용해 데이터베이스에 접근할 수 있도록 하는 자바 API JDBC를 이용하여 DB에 접속, SQL 실행, 데이터를 가져오거나 삭제하는 등 데이터를 다룰 수 있음 JDBC가 등장하게 된 배경 DB 접근의 표준화를 위해서 등장 JDBC 등장 이전 DB마다 존재하는 고유한 API를 직접 사용 이에 따라 개발자는 기존의 DB를 다른 DB로 교체해야하는 경우 DB에 맞게 기존의 코드도 모두 수정해야 했으며 심지어 각각의 DB를 사용하는 방법도 새로 학습해야 했음 → JDBC의 표준 인터페이스 덕분에 개발자는 DB를 쉽게 변경할 수 있게 되었고 변경에 유연하게 대처할 수 있게 됨 JDBC를 알아야 하는 이유 JDBC는 매..

조인(Join) 두 개 이상의 테이블에서 행을 결합하는 방법 일반적으로 조인조건은 PK(Primary Key) 및 FK(Foregin Key)로 구성 PK 및 FK 관계가 없더라도 논리적인 연관만 있으면 JOIN 가능 내부 조인 (INNER JOIN) 두 테이블의 교집합을 반환. 조인 조건을 충족하는 행만 반환 동등 조인(Equi-join)이라고도 함 N개의 테이블 조인 시 N-1개의 조인 조건 필요 외부 조인 (OUTER JOIN): 하나의 테이블에는 존재하지만 다른 테이블에는 존재하지 않는 행도 포함하여 결과를 반환 LEFT OUTER JOIN: 첫 번째 (왼쪽) 테이블의 모든 행과 일치하는 오른쪽 테이블의 행을 반환 RIGHT OUTER JOIN: 두 번째 (오른쪽) 테이블의 모든 행과 일치하는 왼..