본문 바로가기
반응형

해시 테이블10

[코드트리] 코드트리 DB (삼성 SW 역량테스트 2024 하반기 오전 2번, B형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크삼성 B형 전체 링크 2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,A형 1문제 + B형 문제 1문제가 출제됩니다. 참고 - 산타의 선물 공장- 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree)- 구간 합 구하기 with 다이나믹 세그먼트 트리 (Dynamic Segment Tree)- BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 https://www.codetree.ai/training-field/frequent-problems/problems/codetree-db 문제를 요약하면 다음과 같다. init- 테이블을 초기화 한다.테이블은 unord.. 2024. 12. 20.
[코드트리] 산타의 선물 공장 (삼성 SW 역량테스트 2022 하반기 오전 2번, B형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크삼성 B형 전체 링크 2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,A형 1문제 + B형 문제 1문제가 출제됩니다. 참고- 해시 테이블 Hash Table- 더블 링크드 리스트 구현 (Double Linked List Tail ver) https://www.codetree.ai/training-field/frequent-problems/problems/santa-gift-factory 문제를 요약하면 다음과 같다. 공장 설립- 입력 값을 처리한다.ID의 범위가 1 ≤ ID ≤ 1,000,000,000이기 때문에,ID가 입력되는 순서(index)를 unordered_map에 저장한다. 물건 하차- 벨트 .. 2024. 7. 13.
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.
최적화) 삼성 C형 샘플 문제 : 블록 부품 맞추기 SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 B형 전체 링크삼성 C형 전체 링크 블록 부품 맞추기 문제를 더 최적화 해보자. 아래의 makeBlock에서 코드를 하나씩 지워보며 시간을 재보면 sort에서 비용이 많이 드는 것을 알 수 있다.int makeBlock(int module[][4][4]){ register int i, sum; bcnt1 = bcnt2 = mcnt1 = mcnt2 = 0; for (i = 0; i  따라서, 정렬 후 이분 탐색으로 hashing된 블럭을 찾지말고, hash table에 블럭을 저장하도록 하자.블럭의 hashing된 값의 최대 크기는 0x2222222222222222이므로 그래도 저장하기에는 너무 큰 값이다.따라서 PRIME으로 나눈 나머.. 2021. 4. 3.
BOJ 20920 : 영단어 암기는 괴로워 (우선순위 큐 갱신 + Hash Table) 삼성 B형 전체 링크 www.acmicpc.net/problem/20920 단어를 저장하기 위해 해시 테이블을 사용한다. 회사에 있는 사람에서는 해시 테이블을 이용해 단어를 저장하고, 정렬하였다. 마찬가지로 외워야할 단어를 저장하고, count한 다음에 정렬해도 된다. 하지만, 여기에서는 우선순위 큐를 갱신하는 방법으로 문제를 풀어보겠다. 먼저 위에서 요구하는 우선순위를 보자. 자주 나오는 단어일수록 앞에 배치한다. 해당 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 위의 우선순위에서 단어를 입력받을 때, heap에서 해당 단어의 횟수를 증가시킬 필요가 있다. 우선순위 큐를 이용하여 단어의 수를 update해보자. 단어를 저장하고, 저장된 단어의 있는지 체크.. 2021. 3. 21.
데이터의 추가, 삭제, 수정, 검색 - 해시 테이블 응용 삼성 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.
반응형

티스토리툴바