반응형 hash table8 BOJ 7785 : 회사에 있는 사람 (vector) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/7785 Hash Table + Merge Sort로 풀었던 회사에 있는 사람을 vector, string을 이용해서 풀어보자. 아래의 코드는 vector로 대체 가능하다. /* before */ typedef struct st { char name[6]; int in; }DB; DB dbList[1001000]; /* 전체 사람을 관리하는 list */ DB enterList[1001000]; /* 회사에 남은 사람을 저장할 list */ typedef struct st2 { DB *db; struct st2 *next; }HASH; HASH Hash[MAX_TABLE]; HASH POOL[MAX_TABLE]; int pcn.. 2021. 6. 22. BOJ 1764 : 듣보잡 (vector, sort) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/1764 Hash/Merge를 이용했던 듣보잡 문제를 vector, algorithm(sort)를 이용해서 풀어보자. vector를 이용해 메모리 풀을 대체할 수 있다. /* before */ typedef struct st { char name[21]; struct st *next; }HASH; HASH Hash[MAX_TABLE]; HASH POOL[500000 + 50000]; int pcnt; 아래와 같이 필요한 만큼의 배열로 선언하면 된다. /* after */ vector Hash[MAX_TABLE]; 이 문제는 tc가 단독이지만, 실제 B형에서는 아래의 코드로 초기화해야 할 수도 있다. /* tc가 여러 개인 경우.. 2021. 6. 18. BOJ 9612 : Maximum Word Frequency 삼성 B형 전체 링크 www.acmicpc.net/problem/9612 해시 테이블을 이용하여 가장 빈도수가 높은 단어와 개수를 세보자. 같은 수의 단어가 있는 경우 사전 순으로 뒤에 있는 단어를 출력한다. 구조체에는 단어의 수와 실제 단어, 그리고 링크드 리스트를 위한 struct pointer가 필요하다. 메모리 풀 방식으로 연결하기 위해 POOL 메모리와 pcnt를 선언한다. typedef unsigned long ul; #define MAX_TABLE (1007) #define MAX_WORD (20 + 5) int N; typedef struct st { int count; char word[MAX_WORD]; struct st *next; }HASHTABLE; HASHTABLE hashTab.. 2021. 5. 9. 데이터의 추가, 삭제, 수정, 검색 - 해시 테이블 응용 삼성 B형 전체 링크 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 해시 테이블의 기본을 응용하여, 추가/삭제/수정에 대해 알아보자. 어떤 게임의 DB에 아래와 같은 데이터가 있다고 가정해보자. 이 게임은 ID가 중복으로 있을 수 있다. 운영자는 이 DB를 관리해야하는데, 다음과 같은 기능이 필요하다. 1) 새로운 DB를 추가. 2) 현재 DB 중 특정 DB 삭제. (ID가 xxx인 DB 삭제, JOB이 wizard인 DB 삭제 등) 3) 현재 DB 중 특정 DB 수정. (JOB이 yyy인 DB에서 SERVER를 nova로 변경 등.. 2021. 2. 28. BOJ 7785 : 회사에 있는 사람 (Hash Table + Merge Sort) 삼성 B형 전체 링크 www.acmicpc.net/problem/7785 이름을 입력받으면, 아래의 DB 배열에 저장하고 in = 1로 두자. typedef struct st { char name[6]; int in; }DB; DB에 저장하고 이름을 hashing하여 HashTable에 저장하는데, 이때, DB를 포인터로 가르키도록 하자. typedef struct st2 { DB *db; struct st2 *next; }HASH; 즉, Hash에서 db를 보고 있으므로, 포인터로 접근하여 in = 0으로 바꿀 수 있게 된다. DB 자체는 배열로 유지하되, in을 Hash를 통해 포인터로 값을 바꾼다. input = 'enter'면 Hash 저장 및 in = 1, input = 'leave'면 Hash.. 2021. 2. 18. BOJ 1764 : 듣보잡 (Hash Table + Merge Sort) 삼성 B형 전체 링크 www.acmicpc.net/problem/1764 듣도 못한 사람의 수 N명, 보도 못한 사람의 수 M명 중 두 명단에 모두 포함되는 사람의 수를 찾고, 사전순으로 출력해야 한다. 두 명단에 포함 → Hash Table 사전순 출력 → Merge Sort 꼭 이렇게 풀 필요는 없지만, B형 연습을 위해 Hash Table + Merge Sort로 풀어보자. B형에서는 string 라이브러리를 사용할 수 없으므로, strcmp와 strcpy는 직접 만들어야 된다. (가끔 코드로 제공) void mystrcpy(char *a, char *b) { while (*a++ = *b++); } int mystrcmp(const char *a, const char *b) { while (*a .. 2021. 2. 17. 해시 테이블 성능 비교 및 소수 찾기 (BOJ 1620) 삼성 B형 전체 링크 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 BOJ 1620의 MAX_TABLE을 바꿔가면서 성능을 비교해보자. BOJ 1620의 N = 100,000이다. 순서대로 MAX_TABLE = 100 (작은 값이고 소수가 아님) MAX_TABLE = 107 (작은 값이고 소수) MAX_TABLE = 100,000 (N과 비슷한 값이지만 소수가 아님) MAX_TABLE = 100,003 (N과 비슷한 값이지만 소수) MAX_TABLE = 200,000 (N의 2배, 소수가 아님) MAX_TABLE = 200,009 .. 2021. 2. 16. BOJ 1620 : 나는야 포켓몬 마스터 이다솜 (Hash Table) 삼성 B형 전체 링크 www.acmicpc.net/problem/1620 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 BOJ 1620은 실제 삼성 B형에서도 자주 나오는 문자열 해싱과 비슷해서 Hash Table 연습 문제로 풀이를 만들어 보았다. 실제 B형에서 제공하는 hashing 함수를 이용해서 문제를 풀어보자. unsigned long hash(const char *str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = (((hash 숫자 */ POKETM.. 2021. 2. 16. 이전 1 다음 반응형
