깊은 밤을 날아서

논리 스키마 (Logical Schema): 논리 스키마는 데이터베이스의 구조와 관계를 정의하는 개념적인 수준의 스키마입니다. 이는 사용자와 응용 프로그램이 데이터를 이해하고 접근하는 방식을 정의합니다. 논리 스키마는 테이블, 열, 관계, 제약 조건 등의 논리적인 개념을 포함합니다. 앞서 제시한 예제가 논리 스키마에 해당합니다. 1. 테이블 (Tables): 테이블은 데이터의 집합을 나타내며 각 테이블은 열(칼럼)과 행(레코드)으로 구성됩니다. 예를 들어, 온라인 상점의 데이터베이스에는 다음과 같은 테이블이 있을 수 있습니다. 테이블명: Products ProductID ProductName Price CategoryID 1 Laptop 800 1 2 Smartphone 600 2 3 Tablet 400..

이번 포스팅에선 데이터베이스 시스템의 추상화 계층에 대해서 알아보겠습니다. 물리 계층(Physical Level) 디스크에 record가 어떻게 저장되어 있는지 표현합니다. 논리 계층(Logical Level) 데이터가 데이터베이스에 어떻게 저장되어있는지, 관계와 함께 표현합니다. type instructor = record ID : string; name : string; dept_name : string; salary : integer; end; 뷰 계층(View Level) 사용자가 보는 계층입니다. 데이터 타입의 세부 사항이 가려집니다. 보안 필요에 따라 정보를 추가로 가리기도 합니다(EX: 사원의 월급 등)

이번 포스팅에서는 databse 시스템이 왜 생겨났는지 그 이유를 알아보겠습니다. 초기 database system의 문제점 아주 이전에는 database 애플리케이션이 file 시스템으로 이루어졌고 이는 다음과 같은 문제들을 야기하였습니다. 데이터 중복(redundancy)과 불일치(inconsistency): 데이터들이 각기 다른 파일 포맷에 저장되어야 했기 때문에 정보의 중복을 만들었습니다. 데이터 접근의 어려움: 각기 다른 작업에 대해 새로운 프로그램을 작성해야 했습니다. 데이터 고립(isolation): 데이터가 다수의 파일과 포맷에 종속되어 재사용되기 힘든 문제입니다. 무결성(integrity) 문제: 무결성 제약조건은 독립적으로 존재하지 못하고 프로그램 코드에 의해 관리되어야 했고 이로 인해..

입출력 시간복잡도 줄이기 import sys # 입력값이 많을 경우 입력시간 줄이기 input = sys.stdin.readline # 출력값이 많을 경우 출력시간 줄이기, 단 아래 사용 시 개행 문자 사용하여 직접 컨트롤 해야 함. print = sys.stdout.write 재귀함수 호출 시 깊이 제한 늘리기 import sys sys.setrecursionlimit(10**6) 주요 라이브러리 중요도순으로 정리하였습니다. # deque from collections import deque dq = deque()# 선언하기 dq.append()# 오른쪽에 넣기 dq.popleft()# 왼쪽에서 꺼내기 dq# 비어있는지 확인하기 # 우선순위 큐 from queue import PriorityQueue ..

개요 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조입니다. 일반적으로 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행합니다. 특징은 아래와 같습니다. N진 트리: 문자 종류의 개수에 따라 N이 결정됩니다. 예를 들어 알파벳은 26개의 문자로 이뤄져 있으므로 26진 트리로 구성됩니다. 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지합니다. 구현 방법 루트 노드는 공백을 유지한 채 첫 단어에 해당하는 노드를 생성합니다. 아래 과정을 각 단어에 대해 반복하여 단어들을 모두 트리에 입력합니다. 현재 위치한 글자에 대해 루트 자식노드 중 해당 글자가 공백 상태가 아니면 해당 글자로 이동합니다. 공백 상태라면 글자를 추가하고 그곳으로 이동합니다. 백준..

파이썬 코딩테스트 정복기 3탄입니다. 파이썬 코딩에 대해 기본적인 지식이 필요합니다. 각 단원마다 개념을 모두 포함하는 예제 한 문제만 풀이할 예정이니 참고해주세요. 1. 스택 + DFS + 이분 그래프 2. 큐 + BFS + 트리의 지름 3. 우선순위 큐와 그리디 4. 유니온 파인드 + 최소 신장 트리 5-1. 최단 거리 찾기[1] - 다익스트라 알고리즘 5-2. 최단 거리 찾기[2] - K번째 최단 거리 5-3. 최단 거리 찾기[3] - 벨만 포드 5-4. 최단 거리 찾기[4] - 플로이드 워 셜 6. 이진 탐색 + 트라이 7. 투포인터 + 슬라이딩 윈도우 8. 구간 합 + 세그먼트 트리 9. 에라토스 테네스의 체 + 오일러 피 함수 10. 유클리드 호제법 + 확장 유클리드 호제법 11. 조합 + 다..

개요 그래프에서 최단거리를 구하는 알고리즘입니다. 특징은 아래와 같습니다. 모든 노드 간의 최단 거리 구하기 가능 음수 가중치 에지가 있어도 수행 가능 동적 계획법의 원리를 이용해 알고리즘을 구성 시간복잡도는 O(V^3) 구현 방법 시작 노드에서 도착 노드까지의 최단 경로를 구할 때 그 중간에 있는 노드 K가 존재한다면 시작 노드→K, K → 도착노드와 같은 부분 경로도 최단 경로라는 원리입니다. sp_list[S][E] = min(sp_list[S][E], sp_list[S][K] + sp_list[K][E]) 인접 행렬로 구현하는 방법입니다. 리스트 선언 및 초기화 sp_list[S][E]는 노드 S에서 E까지의 최단 거리를 저장하는 리스트 S와 E가 같은 칸은 0, 다른 칸은 무한으로 초기화 최단 ..

1. 벨만-포드 알고리즘 개요 그래프에서 최단 거리를 구하는 알고리즘. 다익스트라 알고리즘과 달리 에지의 가중치가 음수여도 사용할 수 있으며, 이로 인해 음수 사이클 존재 여부 확인 문제에서 많이 사용 다익스트라 알고리즘의 시간복잡도(O(ElogV))에 비해 표에 보이는 것과 같이 노드가 그대로 곱해지므로 음수 가중치 에지가 있거나 음수 사이클의 존재 여부를 판단할 때 사용하는 것이 좋음. 구현 방법 특징: 그래프를 에지 번호에 따라 출발 노드, 종료 노드, 가중치로 이루어진 에지 리스트로 구현함. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화 최단 경로 리스트의 경우 출발 노드를 0, 나머지 노드를 무한대로 초기화 정답 리스트 업데이트하기 모든 에지를 확인해 sp[src_node]가 무한이 ..

K번째 최단 거리 찾기 개요 다익스트라 알고리즘을 이용하여 K번째 최단 거리를 구합니다. 구현 방법 최단 경로 리스트를 2차원 리스트로 설정하여 내부를 K개의 최단 경로로 채웁니다. K번째 경로를 찾기 위해서 여러 번 노드가 쓰일 수도 있으므로 방문 리스트는 따로 적용하지 않습니다. 위의 내용을 기억하며 아래의 최단 거리 리스트 채우기 규칙을 따릅니다. 최단 경로 리스트 및 그래프 인접 리스트를 초기화합니다. 우선 순위 큐에서 연결된 노드와 가중치 데이터를 가져옵니다. 연결 노드의 K번째(마지막) 경로와 신규 경로를 비교해 신규 경로가 더 작을 때 K번째 경로에 값을 업데이트합니다. 이때 경로가 업데이트되는 경우 거리 배열을 오름차순으로 정렬하고 우선순위 큐에 연결 노드를 추가합니다. 큐가 비워질때까지 ..

1. 다익스트라 알고리즘 개요 그래프에서 최단 거리를 구하는 알고리즘 입니다. 특정 출발 노드에서 다른 노드로 가는 최단 거리를 모두 구하기 때문에 출발 노드가 고정되어 있을 때 사용 가능합니다. 추가적으로 에지들의 가중치 또한 항상 양수여야 합니다. 기능 특징 시간 복잡도(노드 수: V, 에지 수: E) 출발 노드와 모든 노드 간의 최단 거리 탐색 에지는 모두 양수 O(ElogV) 구현 방법 간단하게 말하자면 BFS로 탐색을 진행하되, 다음 탐색 지점을 방문하지 않은 노드 들 중 가장 가까운 곳부터 선택하도록 하는 방법입니다. 위와 같이 항상 갈 수 있는 가장 최솟값인 경로만 택함으로써 결과적으로 각 노드는 출발 노드로부터 최단 경로만에 도달하게 됩니다.(간선의 가중치가 모두 양수가 아니라면 돌아올수록..