문제 설명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); /..
문제 설명자연수가 입력되면 배열에 추가하고, 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,..
문제 설명들어본 적 없는 사람 목록과 본 적 없는 사람 목록을 받아 두 목록에 중복된 사람, 즉 '듣도 보도 못한 사람'을 찾는 문제이다.접근집합을 사용하면 사전순으로 자동 정렬된다.두 리스트에서 중복을 찾아내는 방법은 집합이 중복을 허용하지 않는 성질을 이용했다. 먼저 듣도 못한 사람 목록을 집합에 저장한다. 보도 못한 사람 역시 같은 집합에 저장한다. 이때 듣도 보도 못한 사람은 집합에 추가되지 않고, 집합의 크기가 변하지 않는다.보도 못한 사람을 추가했을 때 집합의 크기가 달라지지 않았다면 듣도 보도 못한 사람이다. 전체 코드#include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin...
문제 설명먼저 포켓몬 도감'에 입력할 포켓몬 이름 리스트를 입력받는다,이후 숫자를 입력하면 해당 도감 번호의 포켓몬 이름을 출력하고, 포켓몬 이름을 입력하면 도감 번호를 출력하는 문제이다.접근vector를 이용해서 도감을 구성하고, 이름을 입력받아 도감 번호를 출력할 때 find함수를 이용하면 시간 초과로 문제를 해결할 수 없다.자료 검색에 걸리는 시간을 줄이기 위해 해시 테이블 자료 구조를 사용한다.C++에서는 unnordered_map이라는 STL을 이용하면 된다. 자료 검색에 걸리는 시간복잡도가 O(1)이다. unordered_map m; for(int i = 1; i > s; m.insert({i, s}); } 1번부터 N번까지 해시 테이블로 도감을 만든다. unorder..
문제 설명직사각형 형태의 밭의 각 좌표마다 배추가 심어질 수 있다. 배추가 심어지면 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 ..
문제 수 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 표만 봐도 감이 올 것이다. 주어진 수열을 차례대로 더해서..
| 내 블로그 - 관리자 홈 전환 |
Q
Q
|
|---|---|
| 새 글 쓰기 |
W
W
|
| 글 수정 (권한 있는 경우) |
E
E
|
|---|---|
| 댓글 영역으로 이동 |
C
C
|
| 이 페이지의 URL 복사 |
S
S
|
|---|---|
| 맨 위로 이동 |
T
T
|
| 티스토리 홈 이동 |
H
H
|
| 단축키 안내 |
Shift + /
⇧ + /
|
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.
