반응형 STL14 BOJ 11279 : 최대 힙 (priority_queue) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/11279 우선순위 큐의 문제인 최대 힙을 STL - queue(priority_queue)로 풀어보자. 먼저 priority_queue의 메서드는 아래의 4개가 있다. push() pq에 원소를 넣는다. pop() pq에 원소를 뺀다. top() pq에서 가장 우선순위가 높은 값을 return 한다. (pure한 코드에서 heap[1]과 동일) size() pq의 크기를 return 한다. empty() pq가 비어있으면 true, 아니면 false를 return 한다. clear() clear가 없다. pure한 코드와 다른 점은, pq.pop()이 값을 리턴하지는 않는다. 원소를 빼기만 한다. pop이 void로 만들어져.. 2021. 6. 19. 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. 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 1707 : 이분 그래프 (vector) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/1707 메모리 풀을 이용하였던 이분 그래프 문제를 vector를 이용해 풀어보자. 메모리 풀을 위해 사용하였던 아래의 구조체와 HEAD, POOL, pcnt는 더이상 필요가 없다. /* before */ typedef struct st { int node; struct st *next; }NODE; NODE HEAD[20200]; NODE POOL[202000 * 2]; int pcnt; NODE 구조체에 필요한 것은 정수 node였으므로, 아래의 head에 대한 vector들만 선언하면 된다. /* after */ vector HEAD[20200]; 메모리 풀을 초기화하기 위해 pcnt는 0으로 만들었고, HEAD의 nex.. 2021. 6. 17. C++ - 컨테이너와 반복자 (Container and Iterator) C, C++ 전체 링크 C++의 표준 템플릿 라이브러리 (STL, Standard Template Library)는 아래와 같이 구성된다. - 컨테이너(Container) : 객체를 저장하는 객체, 컬렉션, 자료구조. - 반복자(Iterator) : 컨테이너의 원소에 접근하여 다음 원소를 가리킨다. - 알고리즘 : 연산, 검색, 삭제, 정렬 제공. - 함수 객체(Function Object) : operator의 오버로딩. - 어댑터(Adapter) : 인터페이스를 변경하여 새로운 인터페이스로 변경. - 할당기(Allocator) : 메모리 할당에 대한 클래스 객체 컨테이너는 같은 타입을 저장하고 관리할 수 있는 클래스이다. 각 컨테이너는 자신만의 삽입순서를 가진다. Sequence Container -.. 2021. 6. 11. 이전 1 2 다음 반응형
