민규의 흔적

2023년 11월 21일 문제 링크 : 백준 2493번 - 탑 문제 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 ..

물리적 데이터베이스 설계는 끊임없이 이루어지는 작업으로, 성능을 향상시키기 위한 고민을 지속적으로 해야 한다. 인덱스 선정 지침 1. 어떤 릴레이션에 인덱스를 생성해야 하는가 2. 어떤 애트리뷰트를 탐색 키로 선정해야 하는가 3. 몇 개의 인덱스를 생성해야 하는가 4. 각 인덱스에 대해 클러스터링 인덱스, 밀집/희소 인덱스 중 어느 유형을 선택할 것인가 인덱스를 선정하는 한 가지 방법은 가장 중요한 질의들을 차례로 고려해보고, 현재의 인덱스가 최적의 계획에 적합한지 고려해보고, 인덱스를 추가하면 더 좋은 계획이 가능한지 알아보는 것이다. 인덱스를 결정하는데 도움이 되는 몇 가지 지침 지침 1 : 기본 키는 클러스터링 인덱스를 정의할 훌륭한 후보이다. 지침 2 : 외래 키도 인덱스를 정의할 중요한 후보이다..

SQL의 CREATE TABLE 문에서 PRIMARY KEY절로 명시한 애트리뷰트에 대해서는 DBMS가 자동적으로 기본 인덱스를 생성한다. UNIQUE로 명시한 애트리뷰트에 대해서는 DBMS가 자동적으로 보조 인덱스를 생성한다. (오버헤드는 증가함) 이는 값이 새로 들어오면, 중복된 값인지 아닌지 빠르게 체크하기 위해서이다. 다른 애트리뷰트에 추가로 인덱스를 정의하기 위해서는 DBMS마다 구문이 다소 다른 CREATE INDEX문을 사용해야 한다. 여기서는 오라클 기준으로 설명을 이어나가겠다. 다수의 애트리뷰트를 사용한 인덱스 정의 한 릴레이션에 속하는 두 개 이상의 애트리뷰트들의 조합에 대하여 하나의 인덱스를 다음과 같이 정의할 수 있다. CREATE INDEX EmpIndex ON EMPLOYEE (..

다단계 인덱스 인덱스 자체가 클 경우에는 인덱스를 탐색하는 시간조차 오래 걸릴 수 있다. ( 데이터 파일에 대한 인덱스 파일이 여타 다른 데이터 파일만큼 큰 경우 ) 이러한 경우 인덱스 엔트리를 탐색하는 시간을 줄이기 위해 단일 단계 인덱스를 디스크 상의 하나의 순서 파일로 간주하고, 단일 단계 인덱스에 대해 다시 인덱스를 정의할 수 있다. 다단계 인덱스는 가장 상위 단계의 모든 인덱스 엔트리들이 한 블록에 들어갈 수 있을 때까지 이런 과정을 반복하며, 최종 과정을 거쳐 가장 상위 단계의 인덱스가 만들어지면 해당 인덱스를 마스터 인덱스(Master Index)라고 부른다. 마스터 인덱스는 한 블록으로 이루어지기 때문에 주기억 장치에 상주할 수 있다. 대부분의 다단계 인덱스는 B+트리를 사용한다. 위 예시..

2023년 11월 16일 문제 링크 : 백준 9935번 - 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다. 입력 첫째..

2023년 11월 18일 문제 링크 : 백준 1181번 - 단어 정렬 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다. 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 알고리즘 분류 문자열 정렬 문제 접근 중복된 단어는 하나만 남기고 제거해야 한다는 부분에서, 나는 딕셔너리를 활용하면 되겠다라고 생각했다. 딕셔너리 선언 후, 이미 존재하는 문자..

File을 파일 또는 화일이라고 읽는데, 여기서는 파일로 읽겠다. 파일(File) 조직의 유형 히프 파일(Heap File) 순차 파일(Sequential File) 인덱스된 순차 파일(Indexed Sequential File) 직접 파일(Hash File) 인덱스된 순차 파일 인덱스를 통해서 임의의 레코드를 접근할 수 있는 파일을 인덱스된 순차 파일이라고 한다. 인덱스 기법으로는 단일 단계 인덱스와 다단계 인덱스로 구분된다. 단일 단계 인덱스 단일 단계 인덱스의 각 엔트리는 쌍 이다. 엔트리들은 탐색 키 값의 오름차순으로 정렬된다. 인덱스는 데이터 파일과는 별도의 파일에 저장된다. 기존 파일의 탐색 키와 각 탐색 키와 동일한 값이 위치한 기존 파일의 레코드들을 가리키는 포인터 값 2개의 쌍이 한 엔트..

File을 파일 또는 화일이라고 읽는데, 여기서는 파일로 읽겠다. 파일(File) 조직의 유형 히프 파일(Heap File) 순차 파일(Sequential File) 인덱스된 순차 파일(Indexed Sequential File) 직접 파일(Hash File) 히프 파일(비순서 파일) 가장 단순한 파일 조직으로, 레코드들이 삽입된 순서대로 파일에 저장된다. 정렬되어있지 않으며, 맨 마지막에 저장된 레코드는 맨 마지막에 저장되는 방식이다. 삽입 : 새로 삽입되는 레코드는 파일의 가장 끝에 첨부됨(빠름) 검색 : 원하는 레코드를 찾기 위해서는 모든 레코드들을 순차적으로 접근해야 함(모든 레코드를 검색하지 않는다면 느림) 삭제 : 원하는 레코드를 찾은 후에 그 레코드를 삭제하고, 삭제된 레코드가 차지하던 공간..