개발조아

데이터베이스의 상태를 변화시키는 작업의 단위, 한번에 수행하는 되어야하는 작업 트랜잭션 특성(ACID) 원자성(Atomicity) 트랜잭션의 연산이 모두 반영이되던가 반영이 안되던가 둘중 하나여야한다. 트랜잭션의 모든 연산이 완료되어야하며 하나라도 안된다면 모든 트랜잭션은 취소 되어야한다. 일관성(Consistency) 트랜잭션 수행 전후 데이터베이스의 상태가 같아야한다. 데이터의 타입이 바뀐다던디 제약조건이 바뀐다던지 하면 안됨 독립성(Isolation) 동시에 여러 트랜잭션이 실행될 때 서로의 트랜잭션에 영향을 미치지 않는 독립적으로 실행되야한다. 즉, 서로의 트랜잭션에 끼어들면 안된다. 한 트랜잭션이 완료될때까지 해당 트랜잭션의 결과는 참조할 수 없다 영속성(Durability) 트랜잭션의 결과는 ..

관계형 데이터베이스에서 한 릴레이션에 여러 애트리뷰트(속성)들을 혼합하게 되면 정보가 중복 저장되고 저장 공간이 낭비 된다. 또한 중복된 데이터로 인해 이상 현상(Anomaly)도 발생한다 이상 현상 불필요하게 중복된 데이터들로 인해 데이터 조작 시 발생하는 문제들 삽입 이상 데이터 삽입시 이상한 데이터가 삽입된다던가, 데이터가 없어서 삽입이 안되는 문제 갱신 이상 갱신 시 중복된 데이터 모두 갱신되어야하지만 일부만 갱신되어 일관성이 유지하지 못해 발생하는 문제 삭제 이상 삭제 시 원하지 않는 데이터까지 모두 삭제되서 발생하는 문제 정규화 관계형 데이터베이스에서 중복을 최소화하기 위하여 데이터를 구조화 하는 작업 정규화 단계 제1 정규형 : 애트리뷰트의 도메인값은 원자값이어야하며, 모든 튜플의 값은 도메..

데이터의 검색 속도를 높이기 위한 기술 보통 B+Tree 자료구조를 활용하여 인덱싱함 데이터를 검색할 때 모든 테이블의 데이터를 확인하면 오래 걸린다.(Full Scan) 그래서 인덱스를 구성하여 해당 인덱스에서 검색을 수행 인덱스로 등록된 컬럼을 검색 시 해당 인덱스에서 검색하여 빠르게 데이터에 접근이 가능하다. 인덱스는 컬럼의 값과 그 컬럼의 주소의 쌍으로 이루어짐 인덱스는 컬럼 값이 오름차순 형태로 저장되어있다. 따라서 데이터 검색 시 모든 데이터를 찾는게 아니라 해당 위치까지만 찾아보면 된다. 검색 시 사용되는 모든 컬럼을 인덱스로 등록하면 역효과가 날 수 있음 인덱스는 정렬되어 있기 때문에 새로운 데이터를 추가, 삭제, 수정 시 인덱스에 별도의 작업이 수행됨 저장 성능을 희생하고 검색 성능을 높..

여러 사람들이 공유하고 사용할 목적으로 통합한 데이터들의 모임 DBMS(Database Management System, 데이터베이스 관리 시스템) 데이터베이스를 사용자가 더 쉽고 편리하게 접근하여 관리할 수 있게 해주는 소프트웨어 Mysql, Oracle, MariaDB 데이터베이스를 사용하는 이유 데이터베이스를 사용하기 전에는 파일 시스템으로 데이터를 관리 해서 종속성, 중복성, 무결성으로 인한 문제가 발생하였다. 종속성 문제 데이터를 저장하거나 접근하는 방식등이 바뀌면 프로그램도 변경해야했다 중복성 문제 프로그램에 따라 같은 데이터들을 서로 가지고 있을 수 있어서 문제가 생김 일관성 : 중복된 데이터들 간에 내용이 맞이 않아 문제가 생김 보안성 : 중복된 데이터들있는 모든 곳에 동등한 보안을 유지하..

신장 트리중 가중치의 합이 최소인 신장트리 크루스칼 알고리즘 간선 선택 기반 알고리즘 동작 모든 간선을 가중치로 오름차순 정렬 정렬된 간선에서 사이클이 형성되지 않도록 간선을 선택 오름차순으로 되어 있으므로 작은 것부터 먼저 선택하게 됨 사이클이 형성되는 간선은 제외 선택한 정점을 MST 집합에 포함 간선의 개수가 n-1개가 될때까지 수행 Union-Find 알고리즘으로 사이클 형성 확인 프림 알고리즘 정점 선택 기반 알고리즘 동작 시작 정점을 MST 집합에 포함 MST 집합에 연결된 정점 중 아직 방문하지 않았고 가중치가 가장 작은 간선 선택 가장 낮은 가중치를 먼저 선택 선택한 간선으로 연결된 정점 MST 집합에 포함 간선의 개수가 n-1개가 될때까지 수행 우선순위 큐로 구현 다익스트라와의 차이 다익..

한 정점에서 다른 한 정점까지의 최단 경로 가중치가 없거나 1 인경우 BFS 가중치가 양수인 경우 다익스트라 가중치가 음수인 경우 벨만포드 모든 정점에서 다른 정점으로 최단 경로 위의 알고리즘으로도 풀이 가능 플로이드 와샬 다익스트라 알고리즘 가중치가 가장 적은 노드를 우선적으로 선택하여 탐색하는 방식 동작 1시작 노드와 연결된 정점과의 가중치 업데이트 및 시작 노드 방문 표시 2.방문한 노드에 연결된 정점들의 가중치가 작은 정점을 선택 3.해당 노드로 가는 가중치 업데이트 및 방문 표시 4.아직 선택되지 않은 노드가 남았다면 2,3 과정 반복 구현방법 우선순위 큐를 활용하여 구현 가능 최단 경로로 이동해야하므로 우선순위큐 최소힙으로 구성 항상 최소 가중치의 노드를 선택하여 탐색하도록 함 시간 복잡도 우..

깊이 우선 탐색(Depth First Search : DFS) 한 정점으로부터 연결된 한 정점으로만 탐색하여 끝까지 탐색하는 방법 한 정점에서 연결된 정점을 찾아 해당 정점으로 이동 만약 연결된 정점이 없다면 이전 정점으로 이동해 다른 정점 탐색 모든 정점에 대해서 탐색이 이루어진다 구현 방법 Stack 현재 정점에 연결된 다른 정점을 찾을 시 돌아갈 정점, 즉 현재 정점을 스택에 저장 현재 정점에서 연결할 정점이 없어면 스택에서 다시 정점을 빼서 수행 재귀로도 구현 가능 현재 정점에 연결된 다른 정점이 있다면 다시 재귀 호출 현재 정점에서 연결할 정점이 없다면 해당 재귀 탈출 시간 복잡도 O(V+E) 너비 우선 탐색(Breadth First Search : BFS) 한 정점에 연결된 모든 정점을 모두 ..

정점(Vertex)와 간선(Edge)의 집합 트리 또한 그래프의 일종이고 이때 트리는 사이클을 허용하지 않는 그래프이다 무방향 그래프 말 그대로 간선의 방향이 없는 그래프 (3,4)나 (4,3)이나 같은 간선 방향 그래프 간선에 방향이 있는 그래프 (3,4)와 (4,3)은 다른 간선 Degree 무방향 그래프 간선의 개수 방향 그래프 Indegree : 정점으로 들어오는 간선 outdgree : 정점에서 나가는 간선 그래프를 표현하는 방법 인접 행렬(Adjacency Matrix) 정점과 정점의 연결 관계를 행렬로 표현 연결 관계를 한번에 파악할 수 있다 간선의 개수와 무간하게 정점의개수^2의 공간이 필요 해당 정점에 연결된 간선의 정보 파악 위해선 O(정점의 개수)의 시간이 걸린다 인접 리스트(Adja..