반응형 STL14 [코드트리] 산타의 선물 공장 (삼성 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. 삼성 B형 링크 SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 - Advanced, 신입사원 입사 기출문제삼성 B형 - Professional삼성 C형 - Expert개념 설명 메모리 풀 Memory Pool메모리 풀 vs malloc 속도 비교링크드 리스트 Linked List링크드 리스트 Linked List Tail ver링크드 리스트 삭제 (삼성 B형 샘플 문제 : 숫자야구게임) 해시 테이블 Hash Table해시 테이블 추가, 삭제, 수정, 검색해시 응용 - 2차원 배열 탐색해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용)해시 테이블 성능 비교 머지 소트 Merge Sort 우선순위 큐 Priority Queue우선순위 큐 응용 (1) - 두 개의 heap을 이.. 2024. 1. 24. BOJ 10866 : 덱 (deque) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/10866 vector로 동적 배열, 링크드 리스트를 이용할 수 있다. 그러나 vector는 끝에만 원소를 추가할 수 있으므로, 앞에도 원소를 추가해야할 경우에는 덱(deque)을 사용해보자. 스택(stack), 큐(queue)는 배열로 만드는 것이 쉽고 충분하지만, 덱(deque)의 경우는 pure하게 만들 때, 메모리 관리에 이슈가 있을 수 있다. deque에서 자주 사용하는 메서드는 아래와 같다. clear() deque를 초기화 한다. push_front() 앞에 원소를 넣는다. push_back() 뒤에 원소를 넣는다. vector와 동일하다. pop_front() 앞의 원소를 뺀다. pop_back() 뒤의 원소를 .. 2021. 6. 23. BOJ 7785 : 회사에 있는 사람 (map) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/7785 Hash Table / vector를 이용할 필요없이 이름을 key, 회사에 들어있는 상태를 value로 보는 map으로 문제를 풀 수 있다. map enterMap; 하지만 map을 iterator를 이용하여 출력하면, 오름차순 정렬(사전순 정렬)이 된다. 따라서 map의 key가 정렬되는 기준을 변경해줘야 한다. algorithm의 sort에서 정렬 기준을 변경한 것처럼 map도 compare를 만들고 넘겨주면 된다. struct compare { bool operator()(const string& a, const string& b) const { return a > b; } }; map enterMap; 이제 .. 2021. 6. 22. BOJ 7785 : 회사에 있는 사람 (vector, erase) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/7785 vector를 이용한 방법에서 erase도 사용해보자. vector.erase(pointer)를 이용하면 해당 원소를 삭제할 수 있다. leave 구현 부분을 아래의 코드로 바꾸면 된다. else /* leave 입력 */ { ull h = getHash(name.c_str()); int size = Hash[h].size(); for (int i = 0; i name == name) { Hash[h][i]->in = 0; /* in = 0 으로 변경 */ Hash[h].erase(Hash[h].begin() + i); break; /* 동명이인이 없으므로 종료 .. 2021. 6. 22. 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 10825 : 국영수 (priority_queue, compare) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/10825 이번에는 BOJ 10825 : 국영수 문제를 STL로 풀어보자. 즉, 구조체에 대한 우선순위를 compare에 적용시켜보자. 먼저 HEAP의 char name[15]; 는 string으로 변경하였다. typedef struct st { string name; // char name[15]; int kr; int en; int math; }HEAP; 국영수 문제에서 국어, 영어, 수학 점수에 대한 우선순위는 아래와 같이 판단하였다. int isMin(HEAP a, HEAP b) { if (a.kr > b.kr) return 1; if (a.kr == b.kr) { if (a.en < b.en) return 1; if .. 2021. 6. 21. BOJ 11286 : 절댓값 힙 (priority_queue, compare) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/11286 절댓값 힙 문제를 STL을 적용해서 풀어보자. 위 링크에서 절댓값에 대한 우선순위를 아래와 같이 정의하였다. int isMin(int a, int b) { if (abs(a) chil.. 2021. 6. 21. BOJ 1927 : 최소 힙 (priority_queue, compare) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/1927 STL을 이용해서 최대 힙을 풀었다. 이제 우선순위를 변경하는 방법을 알아보자. 기본적으로 정의된 priority_queue가 최대 힙이었으므로, compare를 만들어서 우선순위를 변경한다. operator를 오버로딩하여 최소 힙이 되도록 변경한다. 우선순위 큐의 operator는 parent와 child를 비교하여 true인 경우 swap한다. 따라서 parent > child → parent가 크면 swap → parent가 가장 작아질 때 까지 swap 이 되어 최소 힙이 된다. struct compare { bool operator()(const int& parent, const int& child) cons.. 2021. 6. 19. 이전 1 2 다음 반응형
