정규화

[이 글은 기존 github 블로그에서 작성해 티스토리로 옮긴 글입니다.] 정규화 normalization 이상현상이 발생하는 릴레이션을 분해하여 이를 없애는 과정. 이상현상을 일으키는 함수 종속성의 유형에 따라 등급을 구분할 수 있다. 제 1 정규형 A relation in which the intersection of each row and column contains one and only one value. 릴레이션의 모든 속성 값이 원자값을 가지면 제 1 정규형이라고 한다. 🛠 정규형 변환 제 2 정규형 A relation that is in first normal form and every non-primary key attribute is fully functionally dependent ..

• format_list_bulleted CS/데이터베이스
• · 2022. 11. 20.
• textsms

데이터베이스 이상현상

[이 글은 기존 github 블로그에서 작성해 티스토리로 옮긴 글입니다.] 이상현상 Anomaly 💡 잘못 설계된 테이블로 데이터 조작(삽입, 삭제, 수정)을 하면 일어난다. 😈 삭제이상 튜플 삭제 시 같이 저장된 다른 정보까지 연쇄적으로 삭제되는 현상 😈 삽입이상 튜플 삽입 시 특정 속성에 해당하는 값이 없어 NULL값을 입력해야하는 현상 😈 수정이상 튜플 수정 시 조건을 잘못 주어서 중복된 데이터의 일부만 수정되어 데이터의 불일치 문제가 일어나는 현상 함수 종속성 어떤 속성A의 값을 알면 다른 속성 B의 값이 유일하게 정해지는 의존 관계 A→B: A는 B의 결정자. ⚠️ 결정자는 단일 속성일 수도, 복합 속성일 수도 있다! 표현) x → y : y는 x의 함수 = y는 x에 함수적으로 종속 = y는 ..

• format_list_bulleted CS/데이터베이스
• · 2022. 11. 20.
• textsms

데이터베이스 개념, 데이터 무결성

데이터베이스 프로젝트에 필요한 정보를 얻기 위해 논리적으로 연관된 데이터를 모아 구조적으로 통합해 놓은 것 - 데이터베이스 개론 개념 integrated data: 중복을 최소화함으로써 데이터 불일치 현상을 없앤다 stored data: 컴퓨터 저장장치에 저장된 데이터 operationl data: 프로젝트의 목적을 위해 사용되는 데이터 shared data: 여러 사람이 동시에 사용할 수 있다 특징 real time accessibility: 사용자가 요청하는 순간에 실제 데이터를 서비스 continuous change: 삽입, 삭제, 수정등으로 바뀐 데이터값 저장 concurrent sharing: 동시에 여러 사용자가 데이터 요청가능 reference by content 데이터 구조 외부 단계- 외..

• format_list_bulleted CS/데이터베이스
• · 2022. 11. 20.
• textsms

2021년 회고

[이 글은 기존 github 블로그에서 작성해 티스토리로 옮긴 글입니다.] 😷 올해도 코로나 올해도 코로나는 끝나지 않았다… 이제는 ‘곧 끝나겠지’라는 생각도 들지 않지만 ‘언젠간 끝나겠지’라는 마음이다. 언젠가 끝날 때까지 모두 건강하길! 🖥 Mac mini M1 사용기 10년 동안 쓴 데스크탑을 보내주고 MacOS를 체험해 보고 싶어서 Mac mini M1을 선택했다. 일단 맥북보다 가격이 낮았고(옵션을 추가했더니 원래 가격보다 더 올라갔지만) 발열, 소음이 거의 없었다. 1년 동안 사용하면서 성능도 만족한다. 다만 아직 개발 생태계에서 지원해 주지 않는 곳이 아직 있을 수 있다. 가끔 개발환경 세팅하거나 이전에 썼던 툴이 설치가 안 되거나 실행이 안 된다면 ‘이걸 M1이 또..?‘라고 생각된다. 하..

• format_list_bulleted 회고
• · 2022. 11. 19.
• textsms

Floyd Warshall Algorithm

Floyd Warshall 그래프의 모든 노드 쌍에 대한 최단거리를 구하는 알고리즘 모든 지점끼리의 거리를 구한다. 다이니믹 프로그래밍 기반이다. A->B로 다이렉트로 가는 경로와 A->k->B 경유해서 가는 경로를 비교해서 더 비용이 작은 경로의 값으로 갱신한다. 시간복잡도: O(V^3) 구현 INF = int(1e9) def floyd(graph, n): for k in range(1, n+1): for i in range(1, n+1): for j in range(1, n+1): graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]) n, m = map(int, input().split()) # 노드, 간선 개수 graph = [[INF] * (n+1..

• format_list_bulleted 카테고리 없음
• · 2022. 11. 19.
• textsms

Dijkstra Algorithm

Dijkstra {{}} 특정 시작점에서 다른 모든 정점으로 가는 최단 거리를 각각 구해주는 알고리즘 {{}} A도시에서 D도시로 가는 최단 비용(거리, 시간, 돈)을 구하는 문제에 적합한 알고리즘. ⚠️ 음수 가중치 간선이 있는 그래프에서는 쓸 수 없다. 시간복잡도 우선순위 큐⭕️ O(ElogV) 우선순위 큐❌ O(V^2) 구현 import heapq INF = int(1e9) def dijkstra(start): queue = [] heapq.heappush(queue, (0, start)) distance[start] = 0 while queue: dist, node = heapq.heappop(queue) for v, c in graph[node]: cost = dist + c if cost < ..

• format_list_bulleted 카테고리 없음
• · 2022. 11. 19.
• textsms

Kruskal Algorithm

MST Spanning Tree: 최소한 간선을 사용하여 그래프 내 모든 정점을 이은 트리(트리는 사이클이 없다는거 주의) n개의 정점에 n-1개의 간선이 존재하는 그래프는 트리 가중치가 있는 그래프에서 최소 비용을 사용하면 Minimum Spanning Tree Union-Find 특정 원소들을 합칠때 이들이 같은 집합에 포함되어 있는지 확인하거나 두 집합을 합칠때 사용한다. Kruskal Algorithm 최소비용 간선을 선택해나간다. 이때 사이클이 발생하지 않도록 하는데 그 과정에서 Union-Find를 사용하면 사이클이 발생하는지 체크할 수 있다. 간선의 가중치가 작은 것부터 순서대로 보면서 해당 간선 양 끝에 있는 두 노드 x, y에 대해 find(x), find(y)값을 비교하여 일치하지 않는..

• format_list_bulleted 카테고리 없음
• · 2022. 11. 19.
• textsms

Prim Algorithm

Prim Algorithm 크루스칼이 최소비용 간선을 선택해 나간다면, 프림 알고리즘은 최소비용 간선이 있는 정점을 선택해 나간다. 시간복잡도 우선순위 큐 O(ElogV) 인접행렬 O(V^2) 구현 import heapq INF = int(1e9) def prime(start): queue = [] heapq.heappush(queue, (0, start)) distance[start] = 0 while queue: dist, u = heapq.heappop(queue) for v, c in graph[u]: if c < distance[v]: distance[v] = c n, m = map(int, input().split()) # 노드, 간선 개수 start = int(input()) # 출발 노드 ..

• format_list_bulleted 카테고리 없음
• · 2022. 11. 19.
• textsms

Heap

🎄 특별한 이진 트리 완전 이진 트리에서 부모 노드가 자식 노드 값보다 같거나 작은(MinHeap)/큰(MaxHeap) 경우를 만족한다. 현재 남아있는 원소들 중 최대값 or 최솟값을 빠르게 계속 얻고 싶은 경우에 유용 heap만드는 데 O(NlogN) 소요 이후 삽입, 삭제 O(logN) 최소값 or 최대값 탐색 O(1)

• format_list_bulleted 카테고리 없음
• · 2022. 11. 19.
• textsms

Tree

트리 🌲 정점끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프 ⬆️위와 같은 가계도 모양을 생각하면 노드는 가문의 각 구성원이며 왜 상위 노드를 부모 노드, 하위 노드가 자식 노드라고 불리는지 쉽게 이해할 수 있다. 이 예시로 트리 용어들을 일상적으로 비유해 본다면 루트 노드는 가문의 선조, 차수는 각 구성원에서 뻗어나간 가지 수로 몇 명의 자식이 있는지, 깊이는 현재 구성원이 선조로부터 몇 세대 내려왔는지, 높이는 마지막 후손의 깊이이다. 이진 트리 🌲 자식 수가 최대 2개인 트리 이진트리 탐색 전위 탐색: 부모 - 좌 - 우 중위 탐색: 좌 - 부모 - 우 후위 탐색: 좌 - 우 - 부모 이진탐색트리 왼쪽 방향에 있는 노드들은 전부 부모 보다 값이 작아야 함 우측 방향에 있는 노드들은 전부 ..

• format_list_bulleted 카테고리 없음
• · 2022. 11. 19.
• textsms