10000COW

BFS는 큐를 이용한 반복 구조로 구현한다. 먼저 큐를 이용한 BFS Pseudo code를 보면서 어떻게 구현해야할지 생각해보자. 1) 큐를 이용한 BFS Pseudo code BFS(G, start_v) let Q be a queue label start_v as discovered Q.enqueue(start_v) while Q is not empty do v := Q.dequeue() if v is the goal then return v for all edges from v to w in G.adjacentEdges(v) do if w is not labeled as discovered then label w as discovered w.parent := v Q.enqueue(w) 2) 큐를 이..

1) 재귀를 이용한 DFS 구현 Pseudo code G는 그래프, v는 정점(vertex)일 때, DFS(G,v) lable v as discovered for all directed edges from v to w that are in G.adjacentEdges(v) do if vertex w is not labeled as discovered then recursively call DFS(G,w) 재귀를 이용한 DFS 구현 Python code def recursive_dfs(v, discovered=[]): discovered.append(v) for w in graph[v]: if w not in discovered: discovered = recusrive_dfs(w, discovered) ..

정규화란? 이상 현상이 발생하지 않도록 Relation을 관련이 있는 애트리뷰트들로만 구성하기 위해 Relation을 분해하여 데이터베이스를 올바르게 설계해나가는 과정이다. 여기서 이상 현상이란? 데이터베이스를 잘못 설계하면 불필요한 데이터 중복이 발생해 Relation에 대한 데이터의 삽입, 수정, 삭제 연산을 수행할 때 부작용이 발생하는데, 이러한 부작용을 이상 현상(Anomaly라고 한다. 이상 현상을 조금 자세히 살펴 보면, 세 가지로 분류할 수 있다. 첫번째는 삽입 이상(Insertion Anomaly)으로, 새 데이터를 삽입하기 위해 불필요한 데이터도 함께 삽입해야 하는 문제가 발생할 때 생기는 이상 현상이다. 두번째는 갱신 이상(Update Anomaly)으로, 중복되는 튜플들 중에서 일부만..

데이터베이스를 공부하다보면, ANSI/SPARC architecture라고도 불리는 'The Three-Schema Architecture'를 마주칩니다. 상당히 개념적인 아키텍처로 느껴지기 때문에 처음 봤을 때는 이해가 잘 가지 않을 수 있습니다. 오늘 Three-Schema Architecture에 대해 큰 그림을 볼 수 있으면 좋겠습니다. Three-Schema Architecture는 다음과 같이 구성됩니다. 총 Three Level로 구성되어 있는 걸 알 수 있는데, External Level, Conceptual Level, Internal Level 총 세가지 Level로 구분합니다. 가장 먼저 Internal Level을 보면, Internal Level은 내부 스키마(internal sc..

동등 조인(일반적으로 말하는 조인) : 공통적인 조인 속성의 값이 같은 것끼리 조인. 조인 속성인 attribute를 모두 표현한다. SQL로 표현하면 다음과 같다. SELECT * FROM (EMPLOYEE JOIN DEPARTMENT ON Dno = Dnumber) 위의 동등 조인을 보다보면, 조인속성인 Dno와 Dnumber가 중복적으로 두 번 나타난다. 이 중복을 없애고 하나로 표현하고 싶다면, 아래의 자연 조인을 사용한다. 자연 조인(Natural Join) 자연 조인 결과를 보면 Dnumber가 사라지고, Dno만 남아있는 것을 볼 수 있다. SQL문으로 표현하면 다음과 같다. 조인 속성이 같은 이름의 Attribute인 경우 자연 조인되어 단 한 번만 표현되므로 SELECT Fname, Ln..