민규의 흔적

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) 히프 파일(비순서 파일) 가장 단순한 파일 조직으로, 레코드들이 삽입된 순서대로 파일에 저장된다. 정렬되어있지 않으며, 맨 마지막에 저장된 레코드는 맨 마지막에 저장되는 방식이다. 삽입 : 새로 삽입되는 레코드는 파일의 가장 끝에 첨부됨(빠름) 검색 : 원하는 레코드를 찾기 위해서는 모든 레코드들을 순차적으로 접근해야 함(모든 레코드를 검색하지 않는다면 느림) 삭제 : 원하는 레코드를 찾은 후에 그 레코드를 삭제하고, 삭제된 레코드가 차지하던 공간..

다음 예시 릴레이션을 보자. 학번 이름 이메일 과목번호 학점 11002 이홍근 lee@naver.com CS310 A0 11002 이홍근 lee@naver.com CS313 B+ 24036 김순미 kim@gmail.com CS345 B0 24036 김순미 kim@gmail.com CS310 A+ 위의 릴레이션은 중복과 갱신 이상을 모두 일으키고 있다. 기본 키 쌍인 (학번, 과목번호) 모두에 종속된 학점 애트리뷰트는 완전 함수적 종속성을 띄고 있지만, 기본 키 쌍 중 학번 애트리뷰트가 이름, 이메일을 결정하고(부분 함수적 종속성), 이메일이 학번과 이름을 결정하고 있으며(이행적 함수적 종속성) , 이름이 학번을 결정하고 있다(부분 함수적 종속성). 릴레이션 분해를 통해 부분 함수적 종속성과 이행적 함수적..

릴레이션 분해 하나의 릴레이션을 두 개 이상의 릴레이션으로 나누는 것으로, 릴레이션의 분해는 필요한 필요한 경우에는 분해된 릴레이션들로부터 원래의 릴레이션을 다시 구할 수 있음을 보장해야 한다는 원칙을 기반으로 한다. 릴레이션 분해 후의 잠재적인 문제 릴레이션이 분해되기 전에는 조인이 필요 없는 질의가 분해 후에는 조인을 필요로 하는 질의로 바뀔 수 있다. 즉, 분해를 했을 때 성능상에 문제가 있는지(테이블 수 증가에 따른 성능 저하) 체크하고 분해를 결정해야 한다. 분해를 잘못하면 두 개의 릴레이션으로부터 얻을 수 있는 정보가 원래의 릴레이션이 나타내던 정보보다 적을 수도 있다. 즉, 정보의 손실을 의미하며 이런 경우에는 분해된 릴레이션들을 사용하여 원래 릴레이션을 재구성하지 못할 수도 있다. 무손실 ..

릴레이션 정규화(Normalization) 정규화의 정의는 다음과 같다. 원래의 릴레이션을 무손실 분해함으로써 중복과 갱신 이상을 최소화하여 일관성과 정확성을 유지하는 과정으로, 주어진 릴레이션 스키마를 함수적 종속성과 기본 키를 기반으로 분석한다. 릴레이션 정규화가 필요한 이유는 다음과 같다. 부주의한 데이터베이스 설계로 인해, 제어할 수 없는 데이터 중복을 야기하여 여러 가지 갱신 이상(update anomaly)을 유발함. 정규화에 대해 자세히 설명하기 전, 갱신 이상에 대한 개념을 숙지할 필요가 있다. 갱신 이상(Update Anomaly) 데이터베이스의 데이터를 수정, 삽입, 삭제하는 과정에서 발생하는 문제로, 각각 수정 이상, 삽입 이상, 삭제 이상이 존재한다. 수정 이상(modificatio..

(개념적 설계 단계) 데이터베이스 설계 사례에 알고리즘 적용 아래는 개념적 설계 단계의 산출물인 개념 스키마 예시이다. 해당 개념 스키마 예시를 이용해 논리적 설계를 진행하여보자. 1단계 : 정규 엔티티 타입과 단일 값 애트리뷰트 정규(강한) 엔티티 타입과 해당 엔티티 타입의 각 단일 속성들을 릴레이션으로 사상한다. EMPLOYEE 엔티티 타입의 복합 애트리뷰트인 ADDRESS 애트리뷰트 대신, 해당 애트리뷰트를 구성하는 City, Ku, Dong 애트리뷰트 각각을 사상한다. 또한 각 엔티티 타입의 기본 키는 릴레이션의 기본 키로 그대로 사상한다. EMPLOYEE(Empno, Empname, Title, City, Ku, Dong, Salary) PROJECT(Projno, Projname, Budget..