프로그래밍/Baekjoon

[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++]백준 11659. 구간 합 구하기 4

문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 구상 매번 각 구간의 합을 계산하면 1억 회 이상의 연산을 수행할 가능성이 있다. 구간 합을 저장하는 배열을 만들어 놓고 필요할 때마다 꺼내 쓰면 된다. 구간 합의 개념을 간단하게 살펴보자. 입력받은 수 5 4 3 2 1 구간 합 5 9 12 14 15 표만 봐도 감이 올 것이다. 주어진 수열을 차례대로 더해서..

[C++] 백준 11651. 좌표 정렬하기2

문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 구상 11650번 문제인 '좌표 정렬하기'를 해결할 때 mutiset과 pair를 활용했다. #include #include using namespace std; int main() { ios::sync_with_stdio(false); c..

[C++] 백준 11866. 요세푸스 문제 0

문제요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) 출력예제와 같이 요세푸스 순열을 출력한다. 구상 1가장 처음 문제를 해결했던 방식이다.  입력하는 개수만큼만 저장할..