되면한다

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 1. 특징 1) 우선순위큐를 쓰는 다익스트라 알고리즘 2) 현재 정점 이전 정점을 배열에 저장 (코드에서 pre 배열) 2. 코드 #include #include #include using namespace std; int v, e; int st, en; int d[100002]; // 최단 거리 테이블 int pre[100002]; vector adj[100002..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 특징 다익스트라 알고리즘을 이용하는 전형적인 문제. - 우선순위큐로 구현 bfs처럼 암기해야될 코드일 것 같다. 2. 코드 #include #include using namespace std; int v, e, st; int d[20005]; // 최단 거리 테이블 vector adj[20005]; // 비용, 정점번호 const int INF = 1e9..

https://www.acmicpc.net/problem/3107 3107번: IPv6 첫째 줄에 올바른 IPv6 주소가 주어진다. 이 주소는 최대 39글자이다. 또한, 주소는 숫자 0-9, 알파벳 소문자 a-f, 콜론 :으로만 이루어져 있다. www.acmicpc.net 1. 특징 문자열 구현 2. 구현 방식 1) split()함수에서 입력값을 :기준으로 벡터에 string 형태로 저장. 2001:db8:85a3::8a2e:370:7334 이 들어오면, vector에는 {2001, db8, 85a3, 8a2e, 370, 7334}가 들어옴. 따라서 벡터의 사이즈는 6개 (::에 의해 생략된 묶음 2개) *::가 들어오면 -> int idx = 3 (::앞쪽에 있는 묶음의 개수를 저장) 3. 코드 #in..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 못풀어서 https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x18/solutions/1707.cpp 풀이법을 가져왔다. 1. 특징 그래프 2. 구현 방법 이분그래프란? - 인접한 정점끼리 서로 다른 색으로 칠하여 모든 정점을 두 그룹으로 나누고, 서로 다른 그룹의 정점을 간선으로 연결한 그래프 3. 코드 #include #inclu..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 트리의 전위 중위 후위 순회 #include #include #include #include using namespace std; int n; int lc[30]; int rc[30]; int p[30]; char _my, _left, _right; int _myi, _lefti, _righti; void dfs(int cur) { cout > _my >> _left >> _right;..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 재귀 dfs #include #include #include #include using namespace std; int n; int u, w; vector adj[100002]; int p[100002]; void dfs(int cur) { for(auto nxt : adj[cur]) { if(p[cur] == nxt) continue; // 부모 노드로 가는 것을 막음. p[nxt] = cur; dfs(nxt); } } int main() { ios:..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 1. 특징 그래프 2. 구현 방법 1) i번째 파티에 온 사람들을 무방향 그래프를 이용해서 연결한다. 2) 진실을 알고있는 사람들의 번호를 가진 배열을 순회하면서, 진실을 알 고 있는 사람과, 그 사람들과 연결된 사람들을 진실을 알고 있는 그룹(unordered_set trueGrp)에 넣는다. 3) 파티를 순회하면서, 해당 파티에 진실을 알고 있는 그룹(trueGrp)에 있는 사람이 파티에 왔는지 확인하고..

https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 문제 요약: 1) 한 배열에 대해 정렬을 수행한다. 배열을 정렬하려면, 각각의 수가 몇번 나왔는지 세고, 수의 등장횟수가 커지는 순서, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 순서는 수가 먼저이다. ex) [3, 1, 1] 1이 2번, 3이 1번 나옴 따라서 [3, 1, 1, 2] ex) 위 배열을 다시 정렬하면 [2, 1, 3, 1, 1, 2] 2) 정렬을 할 배열은 ..