장애의 유형 데이터베이스에 장애가 발생해도 DBMS의 회복 기능을 통해 데이터베이스는 정확하고 일관된 상태로 유지 할 수 있다. 장애가 발생하는 원인은 정전, 사용자의 실수, 하드웨어 고장, 소프트웨어 오류, 미디어 장치 고장, 트랜잭션 논리적 오류 등 매우 다양하다. 데이터베이스 저장 연산 데이터베이스는 비휘발성 저장 장치인 디스크에 저장되어 있다. 응용 프로그램에서 트랜잭션 수행을 지시하면 디스크에서 메인 메모리로 데이터를 보내고 데이터를 다시 디스크로 보내는 작업이 필요하다. 디스크와 메인 메모리 간의 데이터 이동은 블록(block) 단위로 이동하며 디스크에 있는 블록을 디스크 블록, 메인 메모리에 있는 블록을 버퍼 블록이라 한다. 디스크와 메모리 간의 데이터 이동은 다음 두 연산으로 수행된다. i..
회복과 동시성 제어 DBMS는 데이터베이스가 항상 정확하고 일관된 상태를 유지할 수 있도록 장애 발생 시 회복 기능과 동시성 제어 기능을 제공한다. 장애 발생 시 회복 기능을 통해, 여러 사용자가 동시에 데이터베이스를 사용해도 동시성 제어 기능을 통해 데이터베이스는 항상 일관된 상태를 유지한다. 회복과 동시성 제어 기능은 트랜잭션을 기반으로 동작한다. 트랜잭션 (Transaction) 트랜잭션이란 하나의 작업을 수행하는데 필요한 데이터베이스의 연산들(SELECT, INSERT, UPDATE, DELETE)을 모아놓은 것이다. 데이터베이스는 트랜잭션 단위로 작업을 수행한다. 계좌이체 트랜잭션은 2개의 UPDATE 문으로 구성되어 있다. 하나는 성호 계좌에서 5000원을 감소시키는 UPDATE문이며 다른 하..
처음엔 무식하게 풀어본다. 이때 해당 문제가 최적 부분 구조를 만족한다는 것을 쉽게 알 수 있다. 예를 들어 임의의 위치에 있는 수 A를 LIS의 첫 숫자로 골랐다고 가정하면 A부터 시작한 LIS 개수는 A보다 뒤에 있고 큰 원소부터 시작한 LIS 개수(B) + 1이라는 것을 알 수 있다. B를 구할 때 이전에 선택한 수 A는 알 필요가 없다. 최적 부분 구조를 만족하므로 DP를 적용해 중복되는 부분 문제를 제거한다. 백준 11053번 가장 긴 증가하는 부분 수열 문제이다. 함수 f는 start_idx 위치의 수를 시작으로 하는 LIS 개수를 리턴한다. 함수 f를 호출 할 때마다 최대 n개의 부분 문제가 발생하고 함수 f를 n번 반복 호출하므로 O(n²)의 성능을 보인다. import java.lang...
무식하게 풀 수 없을까? 한국 선수들의 순열을 만들어 러시아 선수들과 매칭 시킨다면 n!의 경우의 수가 발생하므로 시간 초과가 발생한다. 그럼 러시아팀을 상대로 최다승을 할 한국 선수들을 탐욕적으로 선택할 수는 없을까? → 남은 선수 중 상대방 선수를 한명이라도 이길 수 없는 선수가 있다면 가장 레이팅이 높은 러시아 선수와 매칭시킨다. 남은 선수 중 상대방 선수를 이길 수 있는 선수들이 있다면 그 선수들 중 가장 레이팅이 낮은 선수를 매칭시킨다. import java.lang.*; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Buffered..
무식하게 풀 수 없을까? 모든 회의의 선택을 고려하려면 각 회의를 선택할 것인지 말 것인지 결정하면 된다. 따라서 2ⁿ의 경우의 수가 생기므로 시간 초과가 발생한다. 그럼 가장 많은 회의를 할 수 있도록 각 회의를 탐욕적으로 선택할 수 없을까? → 가장 빨리 끝나는 회의만을 선택한다. 가장 빨리 끝나는 회의만을 선택해도 문제의 답을 구할 수 있게 된다. 백준 1931번 회의실 배정 문제이다. import java.lang.*; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(..
Greedy (탐욕적 알고리즘)그리디는 경우의 수를 완성시킬 때, 지금 상황에서 가장 좋은 조각을 선택해 경우의 수 상태의 일부로 만들면서 경우의 수를 완성시키는 방식이다. 즉 탐욕적 선택으로 답을 완성시킨다. 성능이 뛰어나지만 최적해를 구한다고 보장할 수 없다.동작 방식경우의 수를 완성시키기 위해 조각 하나를 선택해 상태의 일부로 설정, 이때 가장 좋은 조각을 선택한다. 이때 아래 두 가지 속성을 증명한다.나머지 상태도 1번과 같은 방식으로 구한다.A) 탐욕적 선택 속성 : 우리가 선택한 가장 좋은 조각이 정답에 무조건 포함됨을 보인다. 귀류법으로 쉽게 증명할 수 있다.B) 최적 부분 구조 : 항상 최적의 선택만을 했을 때 전체 최적해를 구할 수 있는지를 증명한다. 대개의 경우 이 속성이 성립하는지는 ..
처음엔 무식하게 풀어본다. 이때 해당 문제가 최적 부분 구조를 만족한다는 것을 쉽게 알 수 있다. 예를 들어 임의의 수 A부터 시작한 최대 경로는 A 바로 아래 수부터 시작한 최대 경로(i), A 바로 오른쪽 아래 수부터 시작한 최대 경로(ii) 둘 중 하나다. i나 ii를 구할때 이전에 선택한 값 A는 필요없다. 최적 부분 구조를 만족하므로 DP를 적용해 중복되는 부분 문제를 제거한다. 함수 f는 x,y수를 시작으로 한 최대 경로의 숫자 합을 반환한다. 삼각형의 원소 개수만큼 부분 문제가 발생하므로 O(n)의 성능을 보인다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) thr..
DP두번 이상 반복 계산되는 부분 문제들의 답을 미리 저장(메모이제이션)해 한번만 계산 되도록 함으로써 속도의 향상을 꾀하는 방식의 알고리즘 패러다임 이항 계수를 계산하는 함수 bino(n,r)를 완전 탐색 방식으로 작성하면 아래와 같이 중복되는 부분 문제가 발생한다. 이때 DP를 적용하면 부분 문제를 중복 계산하지 않아 성능을 높일 수 있다. 중복되는 부분 문제가 많을수록 성능은 더욱 높아진다.[동작 방식]주어진 문제를 완전 탐색을 이용해 해결한다.중복된 부분 문제를 한번만 계산하도록 메모이제이션을 적용한다.최적화 문제와 DP최적화 문제란 문제의 답이 하나가 아닌 여러개 이고 그 중 어떤 기준에 따라 가장 좋은 답을 찾아 내는 문제를 말한다. 예를 들어 n개의 사과 중에서 r개를 골라 무게의 합을 최대..
