본문 바로가기
반응형

Hash5

BOJ 18139 : Rush Hour Puzzle (map) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/18139 Hash, 2차원 배열 탐색을 이용하였던 Rush Hour Puzzle을 map으로 풀어보자. 문제의 핵심은 2차원 배열 탐색을 이용하여 hash한 값이 너무 커서, 다시 hash를 한 것이었다. map을 이용하면 기존의 int hashMap[PRIME];으로 hash할 필요 없이 그대로 hash값을 저장할 수 있다. typedef unsigned long long int ull; map hashMap; /* key : 2차원 배열 hash 값, value : Level */ main에서 hashMap을 큰 값으로 초기화해줬으나, 이 코드는 더 이상 필요가 없다. //for (int i = 0; i < PRIME; .. 2021. 6. 19.
최적화) 삼성 C형 샘플 문제 : 블록 부품 맞추기 삼성 B형 전체 링크 삼성 C형 전체 링크 블록 부품 맞추기 문제를 더 최적화 해보자. 아래의 makeBlock에서 코드를 하나씩 지워보며 시간을 재보면 sort에서 비용이 많이 드는 것을 알 수 있다. int makeBlock(int module[][4][4]) { register int i, sum; bcnt1 = bcnt2 = mcnt1 = mcnt2 = 0; for (i = 0; i < 30000; i++) check1[i] = check2[i] = 0; makeHash(module); sort(match1, 0, mcnt1 - 1, isMinForMatch); sort(block1, 0, bcnt1 - 1, isMinForBlock); sort(match2, 0, mcnt2 - 1, isMinF.. 2021. 4. 3.
삼성 C형 샘플 문제 : 블록 부품 맞추기 삼성 B형 전체 링크 삼성 C형 전체 링크 참고 - 삼성 C형 샘플 문제 : 블록 부품 맞추기 최적화 swexpertacademy.com/main/sst/intro.do SW Expert Academy에서 C형 샘플 문제 블록 부품 맞추기를 풀어보자. 블록 부품 맞추기는 C형 샘플 문제지만 B형 유형으로 풀 수 있다. 여기서 필요한 개념은 2차원 배열의 해싱과 정렬(merge sort), 그리고 이분 탐색이다. 보통 어떤 데이터를 빠르게 찾고 싶은 경우, 정렬을 한 후에 이분 탐색을 하는 경우가 많다. 문제의 예시를 보자. 오른쪽의 블럭을 뒤집어서 맞춰 끼우면 모두 높이가 8인 완벽한 육면체가 된다. 총 30,000개의 블럭 중에 완성품의 합이 최대가 되도록 블럭을 맞춰야한다. 먼저 블럭 배열에 번호를 .. 2021. 3. 30.
BOJ 18139 : Rush Hour Puzzle (해시, 2차원 배열 탐색) 삼성 B형 전체 링크 www.acmicpc.net/problem/18139 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 내용을 번역해서 요약하면 아래와 같다. 1) 6 x 6 board에서 자동차가 최대 10개 존재한다. 2) 자동차는 1칸씩 움직이며, 길이가 2 또는 3이다. 3) 1번 자동차가 exit로 탈출해야 한다. 4) exit는 항상 3번째 줄의 오른쪽 끝이다. 따라서 1번 자동차는 항상 3번째 줄에 가로로 존재한다. 5) 최대 10칸까지 움직인다. 그 이상 움직여도 1번 자동차가 exit로 탈출 못하면 -1을 출력한다.. 2021. 3. 18.
해시 응용 : 2차원 배열 탐색 삼성 B형 전체 링크 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 아래와 같은 15x15 2차원 배열에서 오른쪽의 4x4 조각이 총 몇 개 있는지 찾아보자. 실제 B형 문제라면, 아래의 코드에서 findPiece 함수를 만들면 된다. #include int N = 15; int M = 4; char MAP[15][15] = { { 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, }, { 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, }, { 0, 0, 1, 0, 0.. 2021. 3. 9.
반응형

티스토리툴바