직대딩 블로그

오늘은 알고리즘 문제를 풀 때 정말 흔히 보이는 에 대하여 알아보겠습니다. DFS, BFS, 다익스트라, 스패닝 트리 등 정말 다양한 문제에서 등장하는 것이 그래프죠. ​ 1. 그래프란 ? 가장 기본적인 정의는 정점(Vertex)와 간선(Edge)의 집합입니다. 여기서 간선은, 두 정점을 이어주는 역할을 합니다. 자기자신을 이을 수도 있고, 간선에 방향이 있기도 하고 없기도 하며, 가중치가 있기도 하고 없기도 하는 등 아주 다양한 형태의 그래프가 있습니다. 위의 그래프는 1,2,3,4,5,6의 총 6개의 정점으로 이루어져 있고, {(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)} 의 총 7개의 간선으로 이루어져 있다고 불 수 있겠습니다. V(정점의 집합)..

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net #include #include #include using namespace std; queue que; int n, k; string str; int main() { cin >> n; for (int i = 0; i > str; if (str == "push") { cin >> k; que.push(k); } else if (str == "pop")..

https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net #include using namespace std; int main() { int n; long long ans=0; cin >> n; for(int i=1;i

https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 정렬 후 투포인터를 이용한다. #include #include #include using namespace std; int main() { int n; int ans = 1e9; cin >> n; vector vec(n); for(int i = 0; i > vec[i]; sort(vec.begin(), vec.end()); for(int i..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong." 을 출력하라고 문제에 나와있는데 그럴 필요없다. 왜냐면 문제에서 주어진 n의 범위는 6 ≤ n ≤ 1000000 이고, 골드바흐의 추측은 이미 10의 18제곱 까지 증명되었기 때문이다. ​ 그러므로 그냥 에라토네스의 체를 이용하여 ~n 까지의 소수의 개수를 미리..

문제 링크 : https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 회전 초밥의 범위를 나타내는 배열을 하나 만들어주고, 어떤걸 먹었는지 반복문을 통해 표시해주면 된다. #include #include int n, d, k, c, cnt; int a[33005], vst[33005]; void ins(int go) { if (!vst[go]) cnt++; vst[go]++; } void del(int go) {..