1. 사전 개념 1) 릴레이션 스키마의 설계 1. 애트리뷰트, 엔티티, 관계성(relationship)을 파악 2. 관련된 애트리뷰트들을 릴레이션으로 묶음 다음을 고려해야 한다 1) 애트리뷰트들간의 관계성(relationship): 데이터 종속성 → 연관있는 애트리뷰트들끼리 하나의 릴레이션에 들어가야 한다 2) 효율적인 데이터 처리 3) 데이터의 일관성 3. 변칙적 성질의 예방 데이터 변경 시의 이상현상(삽입·삭제·변경을 할 수 없는 상황)을 예방하는 방향으로 설계 2) 이상 데이터 변경 시 발생하는 문제 1. 삭제 이상: 한 튜플을 삭제함으로써 유지해야 될 정보까지도 삭제되는 연쇄 삭제 현상이 일어나게 되어 정보 손실이 발생하는 현상 2. 삽입 이상: 어떤 데이터를 삽입하려고 할 때 불필요하고 원하지 ..
문제 www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 풀이 재밌어 보이는 문제라서 풀어보았다. 3중 for문을 이용해서 땅의 최소 높이(0)부터 최대 높이(256)까지 모두 검사해본다. 이때, B + sum(g[i][j]) // m*n을 X라 하면, 땅의 최대 높이는 min(256, X)이 된다. → B가 최대 6.4 × 10^7가 될 수 있기 때문에 X가 기하급수적으로 커질 수 있다! B: 인벤토리에서 가지고 있는 블록의 개수 sum(g[i][j]): 각..
문제 www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 풀이 연결 요소의 개수 문제와 상당히 유사한 문제였다. DFS로 풀 수 있는 기본적인 그래프 문제로, 인덱싱할 때만 주의하면 된다. 코드 import sys, collections sys.setrecursionlimit(10**6) def make_graph(n, p): g = collections.defaultdict(int) fo..
문제 www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 음수 가중치가 주어졌기 때문에 벨만 포드 알고리즘을 사용했다. 나무위키에 나와있는 슈도 코드를 그대로 구현하면 된다. '시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다.'라는 조건이 있는데, 말이 너무 어렵다. 쉽게 말해서 음수 사이클을 찾으라는 이야기다. 음수 사이클을 체크하는 부분만 넣어주면 문제없이 해결할 수 있..
1. 최단 경로의 이해 먼저 최단 경로의 기본 성질에 대해 파악해보자. u → v : 노드 u에서 노드 v로의 하나의 엣지로 구성된 경로 s ⇝ v : 노드 s에서 v로의 경로를 표 시하고, 중간에 여러 노드가 존재 가능 s ⇝ u → v 인 경우, 이 경로에서 u는 v의 predecessor 또는 parent이다 만약 s ⇝ u → v 가 s에서 v로의 최단 경로 중 하나라면, s ⇝ u 역시 s에서 u까지의 최단 경로 중 하나이다. s에서 v까지의 여러 경로 중에서 u를 통해 v에 도달하는 경로중에 최단 경로가 있다는 의미이고, s ⇝ u를 먼저 계 산하여 알고 있다면, s ⇝ u → v는 쉽게 계산할 수 있다. dist[v] = "s에서 v까지의 최단 경로의 길이"라고 정의하면 다음과 같은 식이 성..
