1. 다차원 공간 화일 1) 특징 - 여러 개의 필드를 동시에 키로 사용한 화일 2) 종류 - PAM(Point Access Method) : 다차원의 점 데이터를 저장, 검색 - SAM(Spatial Access Method) : 선, 면과 같은 다차원 도형 데이터를 저장, 검색 2. k-d 트리 1) 개념 - 이원 탐색 트리를 다차원 공간으로 활장한 것 - 기본 구조와 알고리즘은 이원 탐색 트리와 유사 - 트리의 레벨에 따라 차원을 번갈아 가며 비교 2) 특징 - 주기억 장치 상에서 동작 - 소규모의 다차원 점데이터를 인덱싱 할 때 적합 - 균형 트리가 아님 3) 삽입 - 4사분면에서 루트 점 저장하고 x값과 y값을 번갈아가며 비교하며 자식 노드에 삽입한다. 4) 단점 : 균형트리가 아니므로 검색 성..

01 다중 키 화일 1. 다중 키 화일의 개념 1) 단일 키화일 - 지금까지 살펴 본 화일들로 기본 키를 사용하는 화일 - 순차 화일, 직접화일, 인덱스된 순차화일 2) 다중 키 화일 - 하나의 데이터 화일에 대해 여러 다른 탐색키를 이용한 여러 개의 접근 경로를 제공 3) 구현 방법 - 데이터를 중복 이용하여 각 응용에 맞는 화일을 각각 구성 - 한 화일에 대한 다수의 접근 경로 구축 : 다중 키 화일 역 화일 : 인덱스 이용 다중리스트 화일 : 레코드 사이의 리스트 이용 02 역 화일 1. 역 화일 구조 - 역 인덱스를 이용하는 구조 - 역 : 인덱스와 데이터 레코드 화일을 연결 2. 역 인덱스 1) 특징 - 데이터 화일에 있는 키 필드 값을 인덱스 키로 포함 - 인덱스 엔트리 = (키 값, 레코드 ..

14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 난이도 : 골드5 풀이과정 : 완전 탐색 문제이다. 모든 경우의 수.. 회전.. 대칭 에 대한 모든 경우의 수를 따져주면된다. 기존 좌표가 (x,y) 라 할때 나올수 있는 회전, 대칭에 대한 경우의 수는 8개 (x,y), (x,-y), (-x,y), (-x,-y), (y,x), (y,-x), (-y,x), (-y,-x) 다음과 같다..!!! 중딩때 배우던가... 이거 rx배열은 부호곱해줘야되서 선언해줬다. 이 걸 ..

1. 리팩토링 1) 클래스 추출 - 기존 클래스에서 필드와 메서드를 추출하여 새로운 클래스로 옮기는 것 2) 리팩토링 카탈로그 이름 클래스 추출(Extract Class) 상황 클래스를 작성함 문제 한 클래스가 너무 많은 책임을 지고 있음 해법 묶을 수 있는 필드와 메서드를 찾아 새로운 클래스로 추출 결과 o 클래스가 작아짐 o 클래스의 책임이 명확해짐 x 클래스의 개수가 늘어남 2. 예제 프로그램 클래스명 역할 Book 책 클래스 Author 저자 클래스(리팩토링으로 작성) Main Book 사용법 예제 클래스 1) 리팩토링 전 public class Book { private String _title; private String _isbn; private String _price; private St..

01. 직접 화일의 개념 1. 직접화일 1) 임의 접근 화일 = 직접 화일 - 다른 레코드를 참조하지 않고도 개개 레코드에 접근 가능 - 인덱스된 화일, 인덱스된 순차 화일, 상대 화일, 해시 화일 2) 상대 화일 - 레코드의 키와 레코드의 위치 사이에 설정된 관계를 통해 레코드에 접근 - 상대 레코드 번호 : 화일이 시작되는 첫 번째 레코드를 1번으로 지정, 기준으로 번호 지정 > 사상 함수 - A : 키 값 => 주소 - 레코드 기록 시 : 키 값 => 레코드가 저장될 주소 - 레코드 검색 시 : 키 값 => 레코드가 저장되어있는 주소 - 모든 레코드에 직접 접근 가능(메인 메모리, 디스크등 직접 저장 장치에 저장하는 것이 효율적) - 사상함수 구현방법 : 디렉터리 검사, 계산을 이용한 방법 3) 디..

1. 인덱스된 순차화일의 구조 1) 구조 - 순차적으로 정렬된 순차데이터 화일과 이 데이터 화일에 대한 포인터를 가지는 인덱스로 구성 - 각 화일은 블록으로 구성 : 인덱스 블록(트리 구조), 데이터 블록(데이터 레코드와 자유공간) ⓐ 마스터 인덱스 : 최상위 레벨의 인덱스 블록 ⓑ 인덱스 엔트리의 구성 : ⓒ 자유 공간 : 레코드의 추가를 위해 남겨둔 여분의 공간, 화일 생성 시 각 블록에 만듦 > 인덱스된 순차 화일 - 키 값에 따라 정렬된 레코드를 순차적으로 접근 or 직접 접근하는 경우 사용 - 사전 검색 시 사전 옆면의 색인이 인덱스랑 같은 역할 * 일괄처리와 대화식 처리가 적합한 경우 2) 삽입 - 최대 키값에 따라 삽입, 만약 블록이 꽉찼다면 반으로 분할한다. - 분할됐으면 포인터 되는 키 ..

1. 리팩토링 1) 메서드 추출 - 한 메서드에 세세한 처리가 많을 때 그런 처리를 묶어서 나누고 독립된 메서드로 추출하는 것 2) 리팩토링 카탈로그 이름 메서드 추출(Extract Method) 상황 메서드를 작성함 문제 메서드 하나가 너무 김 해법 기존 메서드에서 묶을 수 있는 코드를 추출해 새로운 메서드를 작성함 결과 O 각 메서드가 짧아짐 X 메서드 개수가 늘어남 2. 예제 프로그램 클래스명 역할 Banner 테두리 안에 문자열을 출력하는 클래스 Main 동작 확인용 클래스 1) 리팩토링 전 public class Banner { private final String _content; public Banner(String content) { _content = content; } public vo..

1. m-원 탐색 트리 1) 특징 : 이원 탐색 트리보다 분기율을 높여 m개 서브트리로 만든 것 ① 장점 : 트리의 높이가 감소(특정 노드 탐색시간 감소) ② 단점 : 삽입, 삭제 시 트리의 균형 유지를 위해 복잡한 연산이 필요함 ③ 노드 구조 : ex) 3-원 탐색 트리 2) m-원 탐색 트리의 검색 - 루트부터 시작하여 찾으려는 노드의 키 인덱스를 증가시키면서 키 값과 찾으려는 키 값이 동일하면 탐색을 멈춘다. ⓐ 탐색 시간 : 탐색 경로 길이(높이)에 비례 ⓑ 한 노드에는 m-1개 키 값을 저장 ⓒ 높이가 h일 때 - 최대 키 값의 개수: m^h-1 개 - 최소 높이 : logm(n+1) - 최대 탐색 시간 : O(logm(n+1)) 2. B-트리 1) 특징 : 균형된 m-원 탐색트리 ⓐ 루프와 리..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 난이도 : 골드 4 풀이과정 : 다익스트라를 이용한 문제 2차원 배열에서 다익스트라 알고리즘을 활용하면 되는 문제였다. 도둑루피 값은 2차원 배열에 저장하고, 우선순위 큐는 다중 페어를 이용하여 pair (pair 형태로 넣어주도록 했다. 가중치 dist 배열은 2차원 벡터 형태로 선언하였다. 다익스트라를 안다면 2차원 형태를 어떻게 구현하느냐가 주요 문제였음 코드 : #incl..