본문 바로가기

컴퓨터공학54

[데이터베이스] DBMS와 옵티마이저 MySQL 기준 사용할 땐 하더라도 내부 엔진을 알고 사용하자클라이언트-서버 아키텍처 클라이언트 층 서버에 명령, GUI Connection Handling : 클라이언트가 서버에 접속하면 연결을 클라이언트는 위한 스레드를 얻음 Authentication : Mysql에 연결할 때 서버쪽에서 수행, username과 password로 인증 Security : 서버와 연결된 후 특정 사용자에게 쿼리 권한이 있는지 확인 서버 층 (a.k.a “Brain of MySQL Architecture”) RDB의 논리적인 기능을 책임짐 Thread Handling : 연결된 클라이언트가 스레드를 할당받을 때 그 스레드를 제공, 스레드로 실행되는 클라이언트 쿼리들을 핸들링 Parser : SQL을 분석해 문법 검사, .. 2023. 8. 20.
[데이터베이스] 트랜잭션과 ACID 성질 데이터베이스의 상태를 변화시키는 하나의 논리적인 작업 단위, 하나의 트랜잭션은 Commit 또는 Rollback 된다. ACID 데이터의 무결성과 안정성을 보장하기 위해 트랜잭션이 지녀야 하는 성질! Atomicity 원자성 : All or Nothing 트랜잭션 결과가 데이터베이스에 모두 반영되거나 반영되지 않아야 하는 성질 Consistency 일관성 : 트랜잭션 수행 전후 데이터베이스는 일관된 상태를 가져야 하는 성질 Isolation 독립성 : 모든 트랜잭션은 다른 트랜잭션부터 독립되야 하는 성질 Durability 영속성 : 트랜잭션이 성공적으로 수행되었다면 그 결과는 영구적으로 기록되는 성질 永續性 영속성 : 영원히 지속되는 성질이나 능력 無缺性 무결성 : 데이터의 정보가 변경되거나 오염되지 .. 2023. 8. 19.
[알고리즘] SAT(Satisfiability Problem) N개의 불리언 값 변수로 구성된 논리식을 참으로 만드는 변수 값들의 조합을 찾는 문제이다. 들어가기 앞서 P문제 : 문제의 해답을 다항 시간 내에 도출할 수 있는 문제의 집합 NP문제 : 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제의 집합 NP-hard : 다항 시간내에 해답을 구할 수 없는 문제 (대표적으로 P=NP 문제) NP-complete : NP-hard 이면서 NP인 문제 SAT-2 두 논리변수의 논리곱 및 논리합 연산식을 주어질 때, 식을 참으로 만드는 조합을 찾거나, 그런 조합이 없음을 찾는 것이 목표이다. SAT-2 문제에서 제시되는 식을 함의 그래프(implication graph)로 나타낼 수 있다. 각 논리변수(a, ~b, ~a 등등)는 그래프의 노드에 .. 2023. 6. 6.
[백준] 2261번: 가장 가까운 두 점 | C++ 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 브루트포스로 O(N^2) 시간에 해결할 수 있지만, O(NlogN)으로 푸는 방법을 알아보고자 한다. 정답코드 1. x좌표 기준으로 오름차순 정렬한다. 2. 0번째와 1번째 거리를 최소 거리(min_d)라고 가정한다. 3. 현재 살펴보는 좌표가 i번째 (x, y)라고 하면 [x - min_d, x] 범위에 해당하는 좌표를 "더 가까울 수 있는" 좌표 후보에 추가한다. 4. [y - min_d, y + min_d] 에 해당하는 좌표.. 2023. 6. 5.
[백준] 2150번: Strongly Connected Component (타잔 알고리즘) | C++ 2150번: Strongly Connected Component첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정www.acmicpc.net 정답코드타잔 알고리즘은 크게 세 가지 경우로 나뉜다. 1. 아직 방문하지 않은 노드 → 방문한다. 2. 방문했지만 SCC가 아직 아닌 노드 → id값이 더 작은 걸 저장한다. 3. 방문했고 SCC가 형성된 노드 → through 한다. 이런 경우를 거치고 현재 노드(id[cur]) id값과 저장된(remember) id 값이 같으면 스택에서 현재 노드를 만날 때까지 pop한다. 2번, 3번 경.. 2023. 6. 4.
[백준] 2150번: Strongly Connected Component (코사라주 알고리즘) | C++ 2150번: Strongly Connected Component첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정www.acmicpc.net 정답코드이론 공부한 거로 직접 구현해서 최적화된 코드가 아닐 수도 있습니다. 1. 정방향 그래프와 역방향 그래프 입력 받기 2. 첫 번째 정방향 DFS 수행 3. 노드 리스트 얻음 4. 두 번째 역방향 DFS 수행 5. SCC 출력 #include #include #include #include #include #define MAX 10001 #define fse(A,B,C) for(int i.. 2023. 6. 4.
[알고리즘] 강한 연결 요소 Strongly Connected Component | 코사라주 알고리즘, 타잔 알고리즘 강한 결합 방향 그래프의 모든 노드에서 다른 모든 노드로 가는 경로가 있는 경우, 이 그래프가 강하게 연결되어 있다고 한다. [1,2,5], [3,4,8], [6,7]이 강하게 결합된 컴포넌트(이하 SCC)이다. 1에서 출발해 2, 5에 도달할 수 있고, 2에서 출발해도 1, 5에 도착할 수 있고, 5에서 출발해도 1, 2에 도달할 수 있다. 하지만 강결합되지 않은 1과 3을 보자. 1에서 출발하면 3에 도달할 수 있다. 하지만 3에서 출발하면 1에 갈 수 없다. SCC를 찾는 알고리즘 SCC를 구하는 알고리즘은 크게 두 가지가 있다. 코사라주 알고리즘 강결합 컴포넌트를 찾는 유용한 방법이다.이 알고리즘에선 두 번의 DFS를 거친다. 첫 번째 탐색에서 그래프에 따라 노드 리스트를 만들고, 두 번째 탐색에.. 2023. 6. 3.
[기하] 스윕 라인 알고리즘(교차점, 가까운 점, 볼록껍질) | 모르면 절대 못 품 먼저 2차원 거리 측정 함수로 맨해튼거리(택시거리), 유클리드 거리 두 가지가 있다는 것을 알아두자. 교차점의 개수 세기선분이 N개 있을 때, 교차점의 개수를 세는 문제이다. 이때 각각의 선분은 수평 선분이거나 수직 선분이다. O(N^2)으로 쉽게 풀 수 있지만 스윕 라인 알고리즘과 구간 질의 자료 구조를 사용하면 O(NlogN) 시간에 풀 수 있다. 선분이 시작하는 점과 끝나는 점을 가지고 이벤트 처리하는 것이라고 생각하면 된다. 가장 가까운 점 쌍 찾기점 N개가 있을 때 유클리드 거리가 최소인 두 점을 찾는 문제이다. 이 문제도 스윕 라인 알고리즘으로 O(NlogN) 시간에 해결할 수 있다. 점들을 왼쪽에서 오른쪽 순서로 살펴보면서 d라는 값을 관리해 나간다.d는 현재까지 구한 두 점 사이의 최소 거.. 2023. 6. 2.

티스토리툴바