C++7 C++) 백준 10816 숫자 카드 2 입력받은 N개의 수 중에서 또 다른 입력받은 M개의 수가 각각 몇개 존재하는지 찾는 문제이다. 입력 개수와 찾는 수 50만 개에 대해 선형탐색을 사용하면 시간초과가 난다. C++에서 Map은 O(log n)의 레드블랙트리로 구현되어있으므로, 이를 이용하면 시간 내로 문제를 해결 할 수 있다. 물론 다른 방법, 이분탐색을 사용할 수 있지만 여기선 Map을 이용한 방법을 다루겠다. 실제 사용함으로 STL 자료구조에 더 친숙해지기 위함이다. map 로 key는 각 수(중복X), value값으론 그 개수를 기록한다 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,inp.. 2024. 3. 13. C++ STL의 자료구조 자주 쓰는 라이브러리를 한번 싹 정리할 필요가 느껴졌다. 까먹으면 참고도 하고 STL Standard Template Library 다양한 컨테이너, 반복자, 알고리즘 함수 제공하는 C++ 표준 라이브러리 컨테이너 자료구조랑 같은 의미 1. 시퀀스 컨테이너 선형적인 자료구조. 단순히 순서대로 자료 저장하는 것이 주 목적 vector, list, deque 2. 연관 컨테이너(Associative) 일정한 규칙에 따라 자료를 조직화하여 저장, 관리 정렬이나 해시 등이 그 규칙이 될 수 있다. set, map 3. 어댑터 컨테이너 시퀀스 컨테이너를 변형하여 자료를 일정 방식에 따라 관리 반복자를 지원하지 않음 - STL 알고리즘에서는 사용할 수 없다. stack,queue vector 동적배열. 요소 개수 .. 2024. 3. 3. IS-A 관계와 HAS-A 관계 1. IS-A 'A is B' 와 같이 'A는 B 이다' 라는 관계. 클래스간 관계에서, 한 클래스가 다른 클래스의 파생 클래스, 즉 부모-자식 관계 ex) 사람은 동물이다. 개는 동물이다. 사람과 개 모두 상위 카테고리로 동물을 갖는다. 반대는 성립하지 않음. 동물은 사람이다(x) 동물은 개이다(x) 상속은 두 클래스가 IS-A 관계일때만 하는게 좋다. class Animal { public: int gender; ... } class Human : public Animal { public: int race; ... } 2. HAS-A 어떤 기능을 포함하고 싶은 경우 사용한다 IS-A에는 명백한 상위 - 하위 카테고리가 존재하지만, HAS-A는 그렇지 않다. HAS-A는 하나의 포함관계 ex) 컴퓨터-.. 2023. 11. 5. 이전 1 2 다음
