WASD BLOG

 데이터 베이스 트랜잭션(Transaction) 데이터 베이스의 상태를 변화시키는 작업 중 더 이상 쪼개선 안되는 작업들의 모임이다. 즉, 원자성을 보장하는 작업들을 말한다. 트랜잭션이 진행되는 도중에 부분 작업이 실패하면 전체 작업에 영향을 끼치므로 롤백 을 통해 처음으로 되돌려햐 하며 모든 부분 작업이 성공적으로 완료되면 커밋 을 통해 변경 사항을 한꺼번에 데이터베이스에 반영하게 된다. RDBMS - 관계형 데이터베이스 관리 시스템 모든 데이터가 관계로서 표현되는 데이터 베이스 시스템으로, 모든 데이터는 행, 열로 묶인 테이블의 형태로 사용자에게 제공된다. 테이블 형식의 데이터를 관계 연산자를 사용한 쿼리문을 날려 조작하게 된다.(SQL) ex) MySQL, OracleDB, MariaDB ... 특징 데이터의 분류, 정렬, 탐색이 비교적 빠르다. 스키마가 정해져 있어 유연성이 떨어진다. NoSQL - 비관계형 데이터베이스 관리 시스템 RDBMS와는 반대되는 형태의 데이터 베이스 시스템이다. 데이터를 Key-Value 나 Dovument(JSON), Graph 형태로 저장하기 때문에 관계형보다 간단하게 데이터 베이스를 구성할 수 있다. ex) MongDB, Redis, Cassandra ... 특징 관계형 데이터 베이스에 비해 대용량의 데이터를 저장할 수 있다.(분산형 구조) 스키마가 정의되지 않아 변화에 유연하다. B-Tree 데이터베이스나 파일 시스템에서 데이터 인덱싱을 위해 사용되는 트리로, 다음과 같은 특징을 갖는 트리이다. 각 노드들은 M 개의 데이터를 가질 수 있고, 각 데이터 사이마다 양 옆 데이터의 사이에 있는 데이터들을 가진 자식 노드에 대한 링크가 있다. ex) A (B~E를 갖는 자식 노드 링크) F 한 노드가 M개를 넘어가게 되면 그 노드를 반으로 쪼개어 두 노드로 분할한다. 그리고 중간의 데이터를 부모 노드로 넘긴다. 부모 노드도 꽉찬다면 계속 반복한다. B+ Tree 기존의 B 트리는 데이터에 대해 순차적으로 접근하기 힘들다.(오름

 스위핑 알고리즘이란? 스위핑(sweeping) : 청소하다, 휩쓸다 스위핑 알고리즘이란 단어의 뜻 그대로 휩쓸고 지나가며 문제를 해결하는 방식으로, 특정 기준에 따라 정렬한 후 순서대로 처리하는 알고리즘이다. 여러 문제를 풀어보았는데 보통 N = 100000 정도가 주어지고, 선분의 겹침 처리 문제가 많이 나오는 것 같고 시간 복잡도는 정렬의 시간복잡도인 NlogN이 대부분이다.(백준 골드 기준) 예제 1번 : 백준 - 공주님의 정원(2457) 문제 링크 간단한 날짜 전처리 + 그리디(정렬 기준 중요) + 스위핑 문제이다. 먼저, 월과 일로 주어지는 시작, 끝 점을 1 ~ 365 사이의 수로 전처리하는 과정이 필요하다. 각 점들을 직선 상의 선분들로 나타낸 뒤 시작점의 오름차순, 끝점의 내림차순으로 정렬해 스위핑한다. end 점 : 현재까지 심은 꽃의 마지막 좌표 maxE 점 : end 점과 새로운 선분을 이을 때 가장 멀리 갈 수 있는 끝점 좌표 maxE 보다 새로운 선분의 시작 점(nowS)이 크다면 선분은 중간에 끊어지게 되므로 카운트 0이 되고 종료한다.(시작점에 대해 정렬되어 있으므로) 아니라면 현재 선분과 새로운 선분을 이을 수 있다. 다음과 같이 진행한다. - end 보다 새로운 선분의 시작 점(nowS)이 크다면 -> 새로운 선분을 이어야 한다.(카운트 1증가) - 새로운 선분의 끝 점(nowE)과 maxE를 비교해 maxE를 계속 갱신한다. - maxE 가 11월 30일을 넘어가게 되면 그 선분과 바로 이으면 되므로 카운트 1을 증가시키고 종료한다. (끝점에 대해 내림차순이므로 다음 선분은 더 짧다) 예제 2번 : 백준 - Lifeguards(Silver)(15589) 문제 링크 여러 선들이 주어지는데, 단 하나의 선만 제거했을 때 선들이 겹치는 길이를 최대화하는 문제이다. 아이디어는 다음과 같다. fixLine = 두 개 이상의 선들이 겹치는 구간으로, 선 하나를 제거해도 여전히 유효하므로 답에 무조건 더해져야 한다. line = 단

  링크 그리디 + dp 메모이제이션 문제이다. 문제에서 최적의 방법이란 매 라운드마다 다음 라운드로 최대한의 칩을 보내는 것이다. 따라서 현재 남은 칩과, M 에 의해 칩의 배치가 결정된다. 1. 칩 < M  --> 칩을 한 개씩만 놓는 게 최선이다. 2. 칩 % M == 0  --> 칩을 (칩 / M) 개씩 모든 M 자리에 놓는 게 최선이다. 3. 칩 % M != 0  --> 칩을 (칩 / M) 개씩 모든 M 자리에 놓아도 나머지만큼의 칩이 남는다. 남는 칩들은 하나씩 각기 다른 자리에 놓는다. 1 번의 확률은 딜러가 칩을 집을 확률 = 칩의 개수 / M + 칩을 집지 않을 확률 = (M - 칩의 개수) / M 2 번의 확률은 모든 자리의 칩의 개수가 같으므로 1이다. 3 번의 확률은 딜러가 (칩 / M) 개의 칩을 집을 경우 = (M - 나머지) / M + (칩 / M + 1) 개의 칩을 집을 경우 = 나머지 / M 위와 같이 현재 라운드의 칩의 개수에 따라 재귀 함수를 진행하면 된다. 하지만 매 라운드마다 최대 2개의 분기가 일어나므로 2^50 의 시간 초과가 난다. 1, 2, 3 번을 나누는 기준은 (칩 % M) 임을 알 수 있다. 따라서 각 라운드마다 (칩 % M) 인 상태를 메모이제이션 해 주어 시간을 줄일 수 있었다. #include<iostream> #include<memory.h> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> #include<set> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair&l

  링크 우선순위 큐를 이용한 BFS로 풀이했다. 위 아래로 갈 수 있는 땅을 굳이 왼쪽, 오른쪽을 사용하여 갈 필요가 없다. 따라서 땅을 들를 때마다 그 땅의 위아래를 무조건 먼저 탐색한다. 위,아래 갈 때의 우선 순위를 1로 주고 왼쪽, 오른쪽 갈 때의 우선 순위를 0으로 주면 항상 위아래가 큐에서 먼저 나온다. 단, 큐에 왼쪽, 오른쪽밖에 남지 않았다면 이동 횟수가 적은 쪽에게 우선 순위를 높게 준다. (이동 횟수 = 왼쪽, 오른쪽으로 간 횟수, 위아래는 이동 횟수에 포함시키지 않는다) #include<iostream> #include<memory.h> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> #include<set> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> #define pdd pair<double, double> #define pic pair<int, char> #define ll long long #define pll pair<ll, ll> #define vi vector<int> #define vl vector<long long> #define vc vector<char> #define vii vector<pii> #define IMAX 2000000001 #define LMAX 1000000000000000000 #define DMAX 0xFFFFFFFFFFFFF #define MOD 100003

  링크 라빈-카프 알고리즘을 살짝 변형하고, prefix sum을 이용해 선형 탐색으로 풀이했다. 모든 알파벳에 대한 해시 값을 다음과 같이 두었다. a = 1, b = 2, c = 3, d = 4 ... 즉, aba = 1 + 2 + 1 = 4, baa = 2 + 1 + 1 이 되어 자리가 다르더라도 총 해시값이 같다면 문제의 조건을 충족하게 된다. 하지만 bb = 2 + 2 = 4 == aba 처럼 문자열이 다르더라도 해시값이 같을 수 있기 때문에 충돌을 처리해 주어야 한다. 먼저, 문자열1에 대해 라빈-카프 알고리즘과 같은 방식으로 길이가 m 인 부분 문자열들에 대해 모든 H 값을 구한다. (단, 길이가 가장 길어야 하므로 m은 최대 길이부터 감소한다.) 그리고 구해진 H 값들(50000을 넘지 않는다 -> 27 * 1500) 의 시작 index를 체크 배열에 push 한다. 다음으로 문자열2에 대해 같은 방식으로 H를 구해 나가는데 문자열1에서 H가 나왔었다면 -> 충돌이므로 두 부분 문자열을 검사한다. 이 때 부분 문자열을 일일히 검사하려면 N^2 의 시간이 걸릴 수 있으므로 문자열1, 문자열2에 대해 각 자리마다의 알파벳 수 prefix sum을 구해 놓고, 두 부분 문자열의 구간에 대해 26번 반복해주면 두 부분 문자열이 일치하는지 여부를 알아낼 수 있다. #include<iostream> #include<memory.h> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> #include<set> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #defin