전공 검색 결과
27 개의 검색 결과가 있습니다.
전공/C++

알고리즘 : 완전 탐색 #2 (BFS, DFS)

그래프 탐색 마지막으로 그래프 탐색(Graph Traversal)이 있습니다. 그래프란, 어떠한 현상이나 사물을 아래 그림처럼 정점(vertex)과 간선(edge)로 표현한 것으로, 두 정점이 간선으로 연결되어 있으면 인접하다고 합니다. 그래프 또는 트리를 탐색하기 위해 BFS와 DFS라는 기법이 쓰이게 되는데, BFS(Breadth-First Search, 너비 우선 탐색)란 방문한 정점에 인접한 정점들을 우선 방문하는 방식이고, DFS(Depth-First Search, 깊이 우선 탐색)란 인접한 정점 중 하나를 방문하되 그 정점에 인접한 정점을 계속 방문하여, 더 이상 방문할 정점이 없을 때 다시 처음 방문했던 정점에 인접한 또 다른 정점을 방문하게 됩니다. 그림으로 나타내면 다음과 같습니다. 둘 ..

2023. 6. 29. 18:54
전공/C++

알고리즘 : 완전 탐색 #1 (Brute-Force, 순열, 재귀)

완전탐색(Exhaustive search)이란, 어떤 문제를 해결하기 위해 모든 경우의 수를 시도하며 정답을 찾아가는 방법입니다. 완전탐색은 일반적으로 모든 문제를 해결할 수 있지만, 아무리 컴퓨터의 성능이 뒷받침 한다 하여도 그 시간이 천문학적으로 걸릴 수 있습니다. 완전탐색 알고리즘으로는 다음의 다섯 가지가 쓰입니다. 1. Brute-Force : 노가다 2. 순열(Permutation) 3. 재귀(Recursive) 4. 비트마스크(Bitmask) 5. 그래프 탐색(Graph Traversal) : BFS, DFS Brute-Force Brute-Force 기법은 for, while, if ... 등의 반복문, 조건문을 활용하여, 가능한 모든 방법을 단순히 찾는 기법입니다. 예를 들어 숫자로만 이루..

2023. 6. 29. 12:20
전공/BAEKJOON

[C++] 백준 1927 : 최소 힙

문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다. 출력 입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이..

2023. 6. 23. 02:06
전공/BAEKJOON

[C++] 백준 9012 : 괄호

문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열..

2023. 6. 20. 02:55
전공/Database

데이터베이스 : 병행 제어(Concurrency Control) #2 (로킹, 2PLP, MVCC)

앞선 글에서 직렬 스케줄과 비직렬 스케줄에 대해 알아보면서 끝마쳤습니다. 그런데 모든 스케줄에 대하여 직렬 가능성 검사를 하는 것에는 한계가 있다고 했었죠? 이 때, 직렬 가능성을 검사하지 않고도 해당 스케줄의 직렬 가능성을 보장할 수 있는 방법을 바로 병행 제어(Concurrency Control)라고 합니다. 병행 제어에는 여러 가지 방법이 존재하는데, ① Locking, ② 2PL, ③ Timestamp, ④ MVCC, ⑤ 낙관적 검증 등 다섯가지 방법이 있습니다. 로킹(Locking)과 2PL(2 Phase Locking) 로킹은 트랜잭션을 잠궈서 접근을 막는 기법입니다. 로킹에는 다음과 같은 로킹 규약이 따라옵니다. 1. 트랜잭션 T가 read(x)나 write(x) 연산을 하려면 반드시 먼저 ..

2022. 12. 12. 07:54
전공/Database

데이터베이스 : 병행 제어(Concurrency Control) #1 (동시 공용의 문제점, Isolation Level, 직렬 가능성 검사)

데이터베이스 시스템은 두 가지 주요 목표를 갖고 있습니다. - 공용성 (sharability) : 여러 사용자가 DB를 이용 - 일관성 (consistency) : 그러면서도 일관성있는 데이터 유지 데이터베이스를 동시 공용(Concurrent Sharing)한다면, 공용성이 증가하고, 응답 시간이 줄어들며 시스템 활용도가 넓어집니다. 그런데, 동시에 접근하여 한명이 write 하는 동시에 다른 사람도 write한다면, 데이터의 모순이 발생하겠죠? 복수의 사용자가 데이터에 동시 접근하면서도, 일관성 있는 데이터를 유지할 때 필요한 것이 바로 병행 제어(Concurrency Control) 입니다. 이번 시간에는 동시 공용시 발생하는 문제점 Isolation Level MySQL에서의 트랜잭션과 Isolat..

2022. 12. 12. 05:20