겜돌이의 개발일지

문제 백준 2667 단지번호붙이기 (C++) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 일반적인 BFS / DFS 문제입니다. 이차원배열을 탐색하면서, 방문하지 않았다면 bfs를 시행합니다. 근처에 1인 지역들을 모두 탐색해 cnt로 반환합니다. cnt를 result vector에 넣어주고 정렬합니다. 그 후 result vector의 원소들을 하나씩 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27..

문제 백준 1260 DFS와 BFS (C++) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 탐색의 가장 기본 of 기본 문제입니다. 주어진 조건에 따라 V부터 DFS 및 BFS를 실행하고, node를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 4..

제 1정규형 한 릴레이션 R이 제 1정규형을 만족할 필요충분조건은 릴레이션 R의 모든 애트리뷰트가 원자값만을 갖는다는 것이다. 릴레이션의 모든 애트리뷰트에 반복 그룹이 나타나지 않으면 제 1정규형을 만족한다. 제 1정규형을 만족하지 않은 릴레이션을 제 1정규형으로 변환하는 방법 반복 그룹 애트리뷰트에 나타나는 집합에 속한 값마다 하나의 튜플로 표현한다. 또는 모든 반복 그룹 애트리뷰트들을 분리해서 새로운 릴레이션에 넣는다. 원래 릴레이션의 기본 키를 새로운 릴레이션에 애트리뷰트로 추가한다. 제 1정규형에 존재하는 갱신 이상 밑의 릴레이션은 모든 애트리뷰트가 원자값을 가지므로 제 1정규형을 만족한다. 이 릴레이션의 키는 (학번, 과목번호)이다. 수정 이상 한 학과에 소속된 학생 수만큼 그 학과의 전화번호가..

학교 수업 시간에 게임 예시로 할로우 나이트를 참고한 적이 있었다. 보스 전투 영상은 짧았지만 시선을 끌기에는 충분했다. 깔끔하면서도 매력 있는 게임 분위기에 매료되었고, 시험이 끝나자마자 플레이했었다. 원래 새 게임을 시작하면 재미를 붙이기 힘들다. 적응을 좀 하고나서야 그 게임 본연의 재미를 느낄 수 있는데, 할로우 나이트는 처음부터 그 재미를 느낄 수가 있었다. 전투 시스템도 괜찮았지만, 탐험 요소가 아주 잘 짜여있고 계속해서 흥미를 유발했었다. 새로 진입하는 지역에는 지도가 없기 때문에, 위치를 가늠할 수 없고 이리 저리 구석구석을 탐방해야 한다. 그러다가 보면 코니퍼의 콧노래 소리가 어디선가 들리고, 지도를 입수하고 나면 "아 여기가 거기였구나~" 하게 되면서 편한 탐색을 진행할 수 있다. 일반..

릴레이션 분해 개요 릴레이션 분해란, 하나의 릴레이션을 두 개 이상의 릴레이션으로 나누는 것이다. 릴레이션을 분해하면 중복이 감소되고 갱신 이상이 줄어드는 장점이 있는 반면에, 바람직하지 않은 문제들을 포함하여 몇 가지 잠재적인 문제들을 야기할 수 있다. 첫 번째, 릴레이션이 분해되기 전에는 조인이 필요 없던 질의가 분해 후에는 조인을 필요로 하는 질의로 바뀔 수 있다. 두 번째, 분해된 릴레이션들을 사용하여 원래 릴레이션을 재구성하지 못할 수 있다. 무손실 분해(Lossless decomposition) 분해된 두 릴레이션을 조인하면, 원래의 릴레이션에 들어 있는 정보를 완전하게 얻을 수 있다. 여기서 손실이란 정보의 손실을 말한다. 정보의 손실은 원래의 릴레이션을 분해한 후에 생성된 릴레이션들을 조인..

함수적 종속성 개요 함수적 종속성은 정규화 이론의 핵심이다. 릴레이션의 애트리뷰트들의 의미로부터 결정된다. 릴레이션 스키마에 대한 주장이지, 릴레이션의 특정 인스턴스에 대한 주장이 아니다. 릴레이션의 가능한 모든 인스턴스들이 만족해야 한다. 실세계에 대한 지식과 응용의 의미를 기반으로 어떤 함수적 종속성들이 존재하는가를 파악해야 한다. 함수적 종속성은 제2정규형부터 BCNF까지 적용된다. 결정자 어떤 애트리뷰트의 값은 다른 애트리뷰트의 값을 고유하게 결정할 수 있다. 사원 릴레이션에서 사원번호는 사원 이름을 고유하게 결정한다. 주소는 사원 이름을 고유하게 결정하지 못한다. 결정자는 주어진 릴레이션에서 다른 애트리뷰트(또는 애트리뷰트들의 집합)를 고유하게 결정하는 하나 이상의 애트리뷰트를 의미한다. 결정자..

릴레이션 정규화 부주의한 데이터베이스 설계는 제어할 수 없는 데이터 중복을 야기하여 여러 가지 갱신 이상을 유발한다. 어떻게 좋은 데이터베이스를 설계할 것인지, 데이터베이스에 어떤 릴레이션들을 생성할 것인지, 각 릴레이션에 어떤 애트리뷰트들을 둘 것인지 고민해야 한다. 정규화(Normalization)는 주어진 릴레이션 스키마를 함수적 종속성과 기본 키를 기반으로 분석하여, 원래의 릴레이션을 분해함으로써 중복과 세 가지 갱신 이상을 최소화한다. 좋은 관계 데이터베이스 스키마를 설계하는 목적 1. 정보의 중복과 갱신 이상이 생기지 않도록 한다. 2. 정보의 손실을 막는다. 3. 실세계를 훌륭하게 나타낸다. 4. 애트리뷰트들 간의 관계가 잘 표현되는 것을 보장한다. 5. 어떤 무결성 제약조건의 시행을 간단하..

다단계 인덱스 인덱스 자체가 클 경우에는 인덱스를 탐색하는 시간도 오래 걸릴 수 있다. 인덱스 엔트리를 탐색하는 시간을 줄이기 위해서 단일 단계 인덱스를 디스크 상의 하나의 순서 화일로 간주하고, 단일 단계 인덱스에 대해서 다시 인덱스를 정의할 수 있다. 다단계 인덱스는 가장 상위 단계의 모든 인덱스 엔트리들이 한 블록에 들어갈 수 있을 때까지 이런 과정을 반복한다. 가장 상위 단계 인덱스를 마스터 인덱스 (master index)라고 부른다. 마스터 인덱스는 한 블록으로 이루어지기 때문에 주기억 장치에 상주할 수 있다. 대부분의 다단계 인덱스는 B+-트리를 사용한다 SQL의 인덱스 정의문 SQL의 CREATE TABLE문에서 PRIMARY KEY절로 명시한 애트리뷰트에 대해서는 DBMS가 자동적으로 기..

화일에는 다음과 같은 유형이 있다. 히프 화일 순차 화일 인덱스된 순차 화일 직접 화일 히프 화일 가장 단순한 화일 조직이다. 일반적으로 레코드들이 삽입된 순서대로 화일에 저장된다. 삽입 : 새로 삽입되는 레코드는 화일의 가장 끝에 첨부된다. 검색 : 원하는 레코드를 찾기 위해서는 모든 레코드들을 순차적으로 접근해야 함. 삭제 : 원하는 레코드를 찾은 후에 삭제한다. 삭제된 레코드가 차지하는 공간을 재사용하지는 않는다. 좋은 성능을 유지하기 위해 하프 화일을 주기적으로 재조직할 필요가 있다. 모든 레코드들을 참조하고, 레코드들을 접근하는 순서는 중요하지 않을 때 사용한다. (ex : SELECT 문) 특정 레코드를 검색할 때에는 비효율적 -> b개의 블록이 있다고 하면 평균적으로 b/2개의 블록을 읽어야..