겜돌이의 개발일지

개요 0-1 배낭 문제는 n개의 물건에 대해 최대 가치가 되도록 담는 알고리즘이다. 시간복잡도 분석 각각의 물건은 넣는다 / 넣지 않는다의 2개의 경우가 있으므로 단순히 시간 복잡도를 계산하면 O(2^n)이다. Dynamic Programming으로 해결 i > 0이고 w > 0일 때, 전체 무게가 w를 넘지 않도록 i번째까지의 항목 중에서 얻어진 최고 이익을 P[i][W]라고 하면 P[i][W]는 다음과 같이 구할 수 있다. 이 알고리즘의 시간복잡도는 이다. W = 10이고, 품목이 다음과 같을 때의 0-1 배낭 문제 예시 문제점 불필요한 항을 계산한다. (위 그림에서 P[3][8]과 P[3][9]를 구할 필요는 없다.) 위 그림의 경우 총 n(4) * W(10)의 40번의 비교가 필요하다. 아래와 같..

개요 허프만 코드란 최적 이진 코드를 만드는 알고리즘 중 하나이다. Fixed-length binary code 코드의 길이가 고정적이다. ex) a : 00, b : 01, c : 11 등 문제점 : 자주 나타나는 코드의 길이도 고정이므로 낭비가 생긴다. Variable-length binary code 코드의 길이가 가변적이다. ex) a : 10, b: 0, c : 11 등 자주 나타나는 코드의 길이를 줄일 수 있다. 문제점 : 위의 예시에서 d를 00으로 표기하는 방법을 추가하면 00이 d인지, bb인지 구별할 수 없어진다. optimal binary code (최적 이진 코드) 주어진 파일에 있는 문자들을 이진코드로 표현하는데 필요한 비트의 개수가 최소가 되는 코드이다. Prefix code 한..

개요 다익스트라 알고리즘은 가중치가 있는 방향성 그래프에서, 한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 문제이다. 알고리즘의 단계는 다음과 같다. 1. F는 공집합으로 둔다. 2. Y(최단 경로가 확정된 집합)에는 시작 정점 v1을 포함해 {v1}으로 둔다. 3. 최종해답을 얻을 때까지 다음 과정을 반복한다. (a) 선정 절차 / 적정성 점검 : V-Y에 속한 정점 중에서, v1에서 Y에 속한 정점만을 거쳐서 최단 경로가 되는 v를 선정한다. (b) v를 F에 추가한다. (c) v에서 F로 이어지는 최단경로 상의 이음선을 F에 추가한다. (d) 해답 점검 : Y = V가 되면 T = (V, F)가 최단경로를 나타내는 그래프가 된다. 예시 초기화 : v1에서 v2~v5까지의 최단 거리를..

시스템 카탈로그 개요 데이터베이스의 객체(사용자, 릴레이션, 뷰, 인덱스, 권한 등)와 구조들에 대한 모든 데이터를 포함한다. 메타데이터라고도 한다. 메타데이터는 데이터에 대한 데이터라는 의미이다. 시스템 카탈로그는 사용자 및 질의 최적화 모듈 등 DBMS 자신의 구성요소에 의해서 결정된다. 시스템 카탈로그는 관계 DBMS마다 표준화되어 있지 않아서 관계 DBMS마다 서로 다른 형태로 시스템 카탈로그 기능을 제공한다. 시스템 카탈로그는 데이터 사전(data dictionary) 또는 시스템 테이블이라고도 부른다. 질의 처리에서의 시스템 카탈로그 SELECT 문이 문법적으로 정확한가를 검사한다. SELECT 문에서 참조하는 EMPLOYEE 릴레이션이 데이터베이스에 존재하는가를 검사한다. EMPLOYEE 릴..

뷰의 개요 ANSI/SPARC 3단계 아키텍처에서 외뷰 뷰는 특정 사용자가 보는 데이터베이스 구조를 의미했다. 관계 데이터베이스에서의 뷰는 한 사용자의 전체 외뷰 뷰 대신에 하나의 가상 릴레이션을 의미한다. 뷰는 기존의 기본 릴레이션에 대한 SELECT문의 형태로 정의된다. 사용자는 여러 개의 릴레이션과 뷰를 사용할 수 있다. 뷰는 릴레이션으로부터 데이터를 검색하거나 갱신할 수 있는 동적인 창의 역할을 한다. 스냅샷 스냅샷이란, 어느 시점에 SELECT문의 결과를 기본 릴레이션의 형태로 저장해 놓은 것이다. 스냅샷은 사진을 찍은 것과 같아서 스냅샷을 정의하는 시점의 기본 릴레이션의 내용이 스냅샷에 반영된다. 어떤 시점의 조직체의 현황, 예를 들어 몇년 몇월 시점에 근무하던 사원들의 정보, 재고 정보 등이..

문제 백준 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정규형을 만족한다. 이 릴레이션의 키는 (학번, 과목번호)이다. 수정 이상 한 학과에 소속된 학생 수만큼 그 학과의 전화번호가..

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