C++

[C++] 백준 2606. 바이러스

문제 설명1번 노드와 연결되어 있는 노드가 몇 개인지 세면 된다.문제 접근단순한 그래프 순회 문제이므로 BFS를 이용한다.1번 노드와 연결된 노드의 개수만 세면 되므로, BFS는 1번 노드를 출발점으로 한 번만 돌아도 된다. 전체 코드#include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int numOfCom, numOfPair; cin >> numOfCom >> numOfPair; vector g[numOfCom + 1]; //인접 리스트 vector visited(101, false); /..

[C++] 백준 1927. 최소 힙

문제 설명자연수가 입력되면 배열에 추가하고, 0이 입력되면 가장 작은 수를 출력하고 배열에서 제거한다.배열이 비어 있을 때 0이 입력되면 0을 출력한다.문제 접근문제에서도 최소 힙을 사용하라고 되어 있고, 최소 힙은 가장 작은 수가 root에 있도록 정렬되기 때문에 문제에서 요구하는대로 배열이 구성된다. C++에서는 STL인 우선순위 큐를 이용하면 된다.priority_queue는 기본적으로 최대 힙이기 때문에, 옵션을 주어 최소 힙으로 동작하게 수정한다. 전체 코드#include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N,..

[C++] 백준 1764. 듣보잡

문제 설명들어본 적 없는 사람 목록과 본 적 없는 사람 목록을 받아 두 목록에 중복된 사람, 즉 '듣도 보도 못한 사람'을 찾는 문제이다.접근집합을 사용하면 사전순으로 자동 정렬된다.두 리스트에서 중복을 찾아내는 방법은 집합이 중복을 허용하지 않는 성질을 이용했다. 먼저 듣도 못한 사람 목록을 집합에 저장한다. 보도 못한 사람 역시 같은 집합에 저장한다. 이때 듣도 보도 못한 사람은 집합에 추가되지 않고, 집합의 크기가 변하지 않는다.보도 못한 사람을 추가했을 때 집합의 크기가 달라지지 않았다면 듣도 보도 못한 사람이다. 전체 코드#include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin...

[C++] 백준 1620. 나는야 포켓몬 마스터 이다솜

문제 설명먼저 포켓몬 도감'에 입력할 포켓몬 이름 리스트를 입력받는다,이후 숫자를 입력하면 해당 도감 번호의 포켓몬 이름을 출력하고, 포켓몬 이름을 입력하면 도감 번호를 출력하는 문제이다.접근vector를 이용해서 도감을 구성하고, 이름을 입력받아 도감 번호를 출력할 때 find함수를 이용하면 시간 초과로 문제를 해결할 수 없다.자료 검색에 걸리는 시간을 줄이기 위해 해시 테이블 자료 구조를 사용한다.C++에서는 unnordered_map이라는 STL을 이용하면 된다. 자료 검색에 걸리는 시간복잡도가 O(1)이다. unordered_map m; for(int i = 1; i > s; m.insert({i, s}); } 1번부터 N번까지 해시 테이블로 도감을 만든다.  unorder..

[C++] 백준 1012. 유기농 배추

문제 설명직사각형 형태의 밭의 각 좌표마다 배추가 심어질 수 있다. 배추가 심어지면 1로 표현한다. 1로 이어진 구역이 몇 개인지 세는 문제다. 접근직사각형 형태의 밭은 2차원 배열로 표현할 수 있다.2차원 배열 상에서 이어진 1은 DFS나 BFS를 이용해 탐색할 수 있다.DFS나 BFS로 구역을 탐색하고, 한 구역의 탐색이 끝나면 벌레 개수를 증가시킨다.모든 구역이 탐색될 때까지 반복한다. 구현DFS를 이용하기로 한다.static int dx[] = { 0, 1, 0, -1 };static int dy[] = { 1, 0, -1, 0 };void DFS(int x, int y) { visited[x][y] = true; // 상하좌우 네 방향으로 이동 for (int i = 0; i = 0 && nx ..

포르잔 C++ 바이블 ch12 연습문제 & 프로그래밍 문제

연습 문제 1번 Base 클래스와 Base 클래스를 상속받는 Derived1과 Derived2 클래스가 있다고 합시다. 이 클래스를 다형성 관계로 활용하려고 합니다. 각 클래스에 가상 print 함수와 가상 소멸자가 있는 경우의 가상 테이블을 그림으로 표현하세요. 2번 다음과 같은 두 클래스가 있다고 합시다. 두 클래스가 다형성을 갖게 스택 메모리 위에 인스턴스화하는 코드를 작성하세요. 다형성을 활용한다는 것은 부모 클래스에 대한 포인터를 사용한다는 것입니다. 다만 객체의 실체를 스택 메모리에 만들어서 활용하라는 것이 문제의 포인트입니다. class First { private: int fr; public: First(int fr); virtual ~First(); virtual void print() ..

포르잔 C++ 바이블 Ch.11 연습문제 & 프로그래밍 문제

연습문제 1번 다음과 같이 2개의 클래스를 정의했을 떄, 위임(delegation)을 사용해서 두 클래스의 set 함수와 print 함수를 정의해주세요. //First 클래스 선언 class First { private: int a; public: void set(int a); void print() const; }; //Second 클래스 선언 class Second :public First { private: int b; public: void set(int a, int b); void print() const; }; 풀이. //First 클래스의 메소드 정의 void First::set(int a2) { First::a = a2; } void First::print() const { cout

[C++] 생성자와 소멸자

객체에는 특별한 멤버 함수인 생성자와 소멸자가 있다. 생성자가 호출되면 객체가 생성되고, 소멸자가 호출되면 객체가 정리된다. 생성자 생성자는 객체를 생성하는 멤버 함수이다. 생성자 내부에서 객체의 데이터 멤버를 초기화한다. 클래스를 정의할 때 멤버를 선언한다고 초기화가 이루어지는 것은 아니다. 선언 과정에서는 멤버의 이름과 자료형만 지정한다. 생성자는 1. 객체를 생성하고 데이터 멤버를 초기화하는 역할을 수행하므로 리턴값을 가질 수 없다. 2. 이름이 클래스의 이름과 같다. 3. 멤버를 초기화하려면 값을 변경해야 하므로 const 한정자를 붙일 수 없다. 4. 멤버 함수이므로 클래스 정의에서 선언해야 한다. class Circle { public: /*생성자*/ Circle(double radius);/..