해나의 컴공생존기

해당 게시물은 건국대학교 김욱희 교수님의 데이터베이스 강의와DATABASE SYSTEM CONCEPTS 7th 원서를 참고하여 작성하였습니다. 1. Join Expressions join은 두개의 relation을 합쳐 하나의 relation을 만들어 주는 연산자이다. 이는 from에 서브쿼리로도 많이 쓰인다.Natural Joinnatural join은 relational algebra에서 나온 의미와 동일하다. 같은 attribute의 튜플 값이 같은 attribute끼리만 곱셈연산을 취한다. 아래의 두 쿼리는 같은 결과를 도출한다. 이는 두 테이블 외에도 여러 테이블에 적용할 수 있다. 하지만 이는 오답률이 높다. 두개의 테이블이 이름은 같고 의미는 다른 attribute를 가지고 있다면 충돌이 될..

해당 게시물은 건국대학교 김욱희 교수님의 데이터베이스 강의와DATABASE SYSTEM CONCEPTS 7th 원서를 참고하여 작성하였습니다.  1. Data Definition Language (DDL) DDL은 컴퓨터 사용자 또는 응용 프로그램 소프트웨어가 컴퓨터의 데이터를 정의할 수 있는 언어이다. 그중에서도 SQL은 관계형 DB의 구조를 정의한다. SQL에 의해 정의되는 관계형 데이터베이스의 구조는 튜플, attribute, relation, index파일 위치 등 데이터베이스 고유의 특성을 포함하고 있다.또, relation의 스키마와 보안 및 권한, 디스크에 있는 물리적 sorage 구조도 담고 있다.  2. SQL Data Definition Basic TypeSQL에는 기본적으로 탑재되어있..

해당 게시글은 건국대학교 컴퓨터공학부 박능수 교수님의 강의와 교재를 참고하여 작성하였습니다. Perfomance 사용자의 목적에 따라 중요하다고 생각하는 컴퓨터의 성능이 다르다. 그래서 기기의 특성마다 다른 성능 척도를 사용한다. 그 중에서도 시간은 컴퓨터 성능의 가장 기본적인 척도이다. 같은 작업을 최단시간에 실행하는 컴퓨터가 가장 빠른 컴퓨터이다. 하지만 무작정 시작시간과 끝시간을 재서 구하면 OS의 오버헤드, 메모리접근 등의 시간이 같이 더해질 것이다. 순수하게 프로그램을 실행하기 위해 걸린 시간을 CPU time이라고 한다. 이는 우리가 실제 느끼는 시간과는 다르다. 성능측정을 위해 여러 용어를 알아보자. clock : 하드웨어 이벤트가 발생하는 시점. clock cycle : 이 클럭의 시간 간..

해당 게시물은 건국대학교 김욱희 교수님의 데이터베이스 강의와 DATABASE SYSTEM CONCEPTS 7th 원서를 참고하여 작성하였습니다. 1. Structure of Relational DB ralational database는 unique 한 이름을 가진 table의 모음으로 이루어져있다. 이는 instruct라는 relation이다. 나와있는대로 각 행을 attributes혹은 columns라고 부르고 각 열을 tuples혹은 rows라고 부른다. relation의 domain이란 attribute와 대응하는 열에 대한 데이터 타입(Data Type)과 길이를 의미한다. 이는 atomic 해야한다. 즉, 값을 둘로 나누거나 할 수 없다는 의미이다. 모든 도메인은 null값을 포함 하고 있다. ..

해당 게시물은 건국대학교 김욱희 교수님의 데이터베이스 강의와 DATABASE SYSTEM CONCEPTS 7th 원서를 참고하여 작성하였습니다. 1. Purpose of DB Systems Data reduncy and inconsistency DB 시스템은 데이터의 중복과 모순을 막아준다. 데이터를 다루다보면 데이터가 중복되는 경우가 있다. 하지만 이는 storage 낭비와 access cost를 증가 시킬수 있다. 또 이는 데이터 모순을 불러올 수 있다. 중복된 데이터들 중 하나의 데이터만 바꿨을 때 중복된 모든 데이터를 수정하기 힘들기 때문이다. Difficulty accessing data 기존 시스템으로는 효율적으로 데이터를 검색하고 분류하기 힘들다. 일반적인 사용을 위해서는 응답성이 높은 데이..

1. 문제정의 위 모양의 퍼즐을 1234 순서대로 만드는것이다. 빈칸의 상하좌우 숫자들은 빈칸과 자리를 바꿀 수 있다. 2. State Space 상태공간이란, 문제가 처할 수 있는 모든 상태를 모아놓은 것이다. 모든 상태가 다 solve가능한 상태일까? 아니다. 퍼즐 두개를 뽑아서 자리를 바꾸면 풀수 없는 상태가된다. 하지만 또 두개를 뽑아서 자리를 바꾸면 풀 수 있는 상태가 된다. state가 될 수 있는 모든 경우의수를 생각해보면 16!이다. 매우 큰 숫자이다..! 이 퍼즐에는 Invariant가 있다. Permutation과 빈칸과 코너의 거리를 더한 값이 유지된다는 것이다. 먼저 빈칸을 16으로 생각하고 배열을 만든다. 각 숫자에 자신보다 오른쪽 중 자신보다 작은수의 개수를 적는다(Permuta..

1. 문제 정의 N x N 크기의 체스판이 있을 때 N개의 퀸을 서로가 공격할 수 없도록 올려놓는 경우의 수를 구하는 문제이다. 2. idea N이 4일 때를 기준으로 생각해 보겠다. 2.1 다해본다 16C4 * 16 2.2 겹치는 경우는 뺀다. 한 열에 하나 씩 배치 4^4 2.3 cut off (1,1) 에 퀸을 배치하고 그 퀸이 갈 수 있는데를 다 표시한다. 표시되지 않은 칸들 중 하나에 퀸을 배치하고 또 그 퀸이 갈 수 있는데를 다 표시한다. 이런식으로 (1,1) 부터 (1,n)까지 시도해본다. 사실 오른쪽과 왼쪽은 대칭이기 때문에 왼쪽 반만하고 곱하기 2를 해줘도된다.

1. SCC (Strongly Connected Compnent) 방향 그래프에서 임의의 두 정점에 대해 양 방향으로 가는 경로가 모두 있을 때 두 점은 같은 SCC에 속해 있다고 한다. 즉 SCC는 모든 노드가 양방향으로 Reachable한 노드의 Maximal Subset 이다. 쉽게 말하자면 x→y가 있고 y→x가 있다면 strongly conneced하다고 한다. 사이클이 이의 가장 간단한 형태이다. 여기서 Maximal 과 Maximam의 차이를 조금 짚고 넘어갈 필요가 있응 것 같다. Maximal 은 한국어로 번역하면 극대라고 할 수 있다. 그 상황에서 가장 큰 값으로 이해하자. Maximam은 전체에서 가장 큰 것을 의미한다. DFS Tree에서 여러 트리가 있을 때 하나의 트리에는 여러가..

1. Topological Sort 번역하자면 위상정렬이다. *DAG: Directed Acyclic Graph (방향성이 있고 사이클이 없는 그래프) 위상 정렬은 DAG의 노드들을 왼쪽에서 오른쪽 방향(엣지 방향이 모두 오른쪽) 으로 정렬하는 것을 의미한다. DAG에 사이클이 존재하지 않으면 알고리즘은 항상 성공한다. 사이클이 없기 위해서는 indegree=0 인 노드가 최소 하나 이상 있어야한다. 이를 귀류법으로 증명해보겠다. indgree=0인 노드가 없다고 가정해보자. indgree=0인 노드를 안만들기 위해서는 계속 들어가는 노드를 만들어야하는데, 이 과정이 무한하게 흘러간다. 무한하지 않으려면 다른노드와 연결해야하는데 이렇게 되면 사이클이 생긴다. 1.1 algorithm DAG G에서 ind..

1. Cut Vertex Cut Vertex (절단점)는 제거할 경우 그래프가 끊어지게 되는 노드를 의미한다. 각 노드마다 노드를 지우고 그래프가 끊어졌는지를 확인하면 O(n (m+n))의 시간이 걸리게 된다. 하지만 DFS를 돌리고 DFS Tree를 생성하면 O(m+n)만에 절단점을 찾을 수 있다. 1.2. root Cut Vertex root 노드는 child가 2개 이상이라면 무조건 cut vertex이다. 증명해보자! 1) child가 0개인 경우 루트 노드밖에 없으므로 성립 2) child가 1개인 경우 사진과 같이 root노드가 없어도 자식노드들 끼리 다 연결되어있다. 3) child가 2개 이상일 경우 루트노드에 1번 서브트리와 2번 서브트리가 있다고 가정해보자. 1번 서브트리에는 어딘가에 ..