본문 바로가기

Computer Science112

[알고리즘] ep4+++) 비활성화 방식 삭제 문제) 크기가 M인 해시테이블에 키 값을 입력받아 저장하고, 개방주소법 중 이중 해싱을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오. [프로그램 요구사항]1)  해시테이블의 사이즈 M = 23 으로 정의할 것. 2)  이중해싱에 기반해야 하며 h 및 h’은 각자 적절히 정의하여 사용할 것. 3)  저장 원소는 0에서 99 사이의 정수로 제한할 것. 4)  삽입(i) 명령시, 중복 키 또는 해시테이블이 만원일 경우 적절한 안내 메시지와 함께 명령수행을 거절할 것. 5)  탐색(f) 또는 삭제(r) 명령시, 함께 주어진 키가 존재하지 않을 경우 NoSuchKey를 반환 및 인쇄할 것.  [주의]인쇄(p) 명령시에만, 아래 예시처럼 현재 해시테이블의 내용을 두 개의 라인으로 보여줄 것. 윗 라인은.. 2024. 7. 19.
[알고리즘] ep4++) 개방주소법 구현(선형 조사, 이중 해싱) 문제1) 크기 M인 해시테이블에 n개의 키 값을 입력받아 저장하고, 개방주소법 중 선형조사법을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오. [구현 조건]- 해시테이블은 크기가 M인 배열로 동적 할당한다.- n은 M보다 작은 자연수로 최대 삽입 개수다.- 입력 키는 중복이 없는 6자리 또는 8자리의 임의의 자연수(학번)다. - 키 x에 대한 해시함수 h(x) = x % M 을 사용한다.- 저장된 키 값이 없는 빈 버켓은 0으로 처리한다.  [입력]- 해시테이블의 크기 M과 입력 데이터의 크기 n을 입력받는다.- 삽입(i), 탐색(s) 명령어를 순서에 상관없이 반복하여 입력받는다. i x> : 키 x를 해시테이블에 삽입s x> : 키 x가 해시테이블에 존재하는지 탐색 e : 프로그램 종료 [출.. 2024. 7. 19.
[알고리즘] ep4+) 연쇄법 구현 문제) 크기 M인 해시테이블에 여러 개의 키 값을 입력받아 저장하고, 연쇄법을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오 [구현 조건]- 해시테이블은 크기가 M인 배열로 동적 할당한다.- 입력 키는 중복이 없는 자연수다.- 키 x에 대한 해시함수 h(x) = x % M 을 사용한다.- 삽입 시 충돌이 발생하는 경우, 해당 버켓 리스트의 맨 앞에 삽입한다.  [입력]- 해시테이블의 크기 M을 입력받는다.- 삽입(i), 탐색(s), 삭제(d), 인쇄(p) 명령어를 순서에 상관없이 반복하여 입력받는다. i x> : 키 x를 해시테이블에 삽입s x> : 키 x가 해시테이블에 존재하는지 탐색d x> : 키 x가 해시테이블에 존재하면 삭제p : 해시테이블에 저장된 키들을 순서대로 인쇄(입출력 예시 참.. 2024. 7. 19.
[알고리즘] ep4) 해시테이블(hashtable) 선형검색에 반해 해시테이블의 검색시간은 평균적으로 상수시간이다 (사전에 삽입된 모든 키가 충돌하는 최악의 경우는 O(n))해시테이블의 상수시간이 가능한 이유는 "해시함수"를 통해 바로 접근하기 때문이다ㅁ해시테이블(hashtable): 버켓배열 + 해시함수(key, address) 맵핑에 의해 구현된 사전 ADT※ key-value는 키와 값을 직접 연결하는 방식이라면, key-address는 키가 실제 데이터의 위치(주소)를 가리키는 방식 e.g. 컴파일러의 심볼 테이블, 환경변수들의 레지스트리, 소규모 DB, 브라우저 캐시  ㅇ버켓배열(bucket array) = 테이블 버켓을 슬롯(slot)이라고도 한다  ㅇ해시함수(hash fucntion): 맵핑하는 역할e.g. h(x) = x % Mh(x)는 정.. 2024. 7. 18.
[알고리즘] ep3++) AVL 트리 구현 AVL 트리 구현종료(q) 명령 때까지 삽입(i), 탐색(s), 삭제(d), 인쇄(p), 명령을 반복 입력받아 수행i : 입력 에 대한 노드 생성 및 트리에 삽입d : 입력 가 트리에 존재하면 해당 노드 삭제 후 삭제된 키를 출력, 없으면 ‘X’를 출력s : 입력 가 트리에 존재하면 해당 키를 출력, 없으면 ‘X’를 출력 p: 현재 트리를 전위순회로 인쇄q: 프로그램 종료  주의: 중복 키가 없는 것으로 전제한다. 문제를 단순화하기 위해, 키만 존재하고 원소(element)는 없는 것으로 구현한다. main 함수는 반복적으로 명령을 입력받기 전에 빈(empty) 이진탐색트리를 초기화해야 한다 – 즉, 외부노드 1개로만 구성된 이진트리를 말한다. 힌트: 트리 노드 삭제 시, 삭제할 노드 w의 자식 중 하나.. 2024. 7. 17.
[알고리즘] ep3+) 이진탐색트리(BST) 구현 BST(이진탐색트리) 구현종료(q) 명령 때까지 삽입(i), 탐색(s), 삭제(d), 인쇄(p), 명령을 반복 입력받아 수행i : 입력 에 대한 노드 생성 및 트리에 삽입d : 입력 가 트리에 존재하면 해당 노드 삭제 후 삭제된 키를 출력, 없으면 ‘X’를 출력s : 입력 가 트리에 존재하면 해당 키를 출력, 없으면 ‘X’를 출력 p: 현재 트리를 전위순회로 인쇄q: 프로그램 종료  주의: 중복 키가 없는 것으로 전제한다. 문제를 단순화하기 위해, 키만 존재하고 원소(element)는 없는 것으로 구현한다. main 함수는 반복적으로 명령을 입력받기 전에 빈(empty) 이진탐색트리를 초기화해야 한다 – 즉, 외부노드 1개로만 구성된 이진트리를 말한다. 힌트: 트리 노드 삭제 시, 삭제할 노드 w의 자식.. 2024. 7. 17.
[알고리즘] ep3) 탐색트리 ㅇ이진탐색트리(BST, Binary Search Tree): 노드의 왼쪽 가지에는 노드보다 작은 값들만 있고, 노드의 오른쪽 가지에는 노드보다 큰 값들만 있도록 구성 내부노드에 (key, value)쌍을 저장하며 그림으로는 간단히 노드에 key만 표시한다(왼쪽 및 오른쪽 부트리 또한 각각 이진탐색트리이다) // 재귀버전int binarySearch(int* arr, int lowIdx, int highIdx, int key) { if (lowIdx > highIdx) { if (highIdx key) { // 중간값이 키값보다 큰 경우, 왼쪽 절반을 탐색 return binarySearch(arr, lowIdx, midIdx - 1, key); } else if (a.. 2024. 7. 11.
[알고리즘] ep2) 사전(dictionary) ㅇ사전(dictionary) ADT: 탐색 가능한 형태의 (key, value)쌍 항목들의 모음을 모델링주로 해시 테이블(hash table)과 이진 검색 트리(BST)로 구현하며, 이때 각 키는 유일해야 한다 -> 유일키 - 직접응용: 연락처, 카드 사용승인, 인터넷주소 맵핑 e.g. www.sejong.ac.kr을 128.148.34.101로 맵핑 - 간접응용: 알고리즘 구현, 자료구조 구현  유일키(unique key): 한 개의 키에 대해 하나의 데이터만 존재e.g. 학번, 계좌, ID중복키(duplicate key): 한 개의 키에 대해 여러 개의 데이터가 존재e.g. 이름, 나이, 계좌개설일자  [두 종류의 사전]- 무순사전 ADT- 순서사전 ADT [사전 구현에 따른 탐색 기법]    "컴퓨.. 2024. 7. 11.
[알고리즘] ep1-6+) 퀵정렬의 다양한 버전 (출력형식)Limit         결정적1           결정적3              무작위1           무작위31        X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX 100    X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX 500   X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX 1000  X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX(참고: X.XXXXXXXX는 측정된 cputime in milliseconds).   [주요 함수들의 설계 가이드라인]global integer n = 100000global array Limits = {1, 100, .. 2024. 7. 10.

티스토리툴바