당신의 이야기에 주목할께요

이 문제는 두개의 BFS를 이용하여 푸는 문제이다. 아무점이나 선택하여 BFS를 돌려 제일 먼 거리를 구한다. 그 다음 그 먼거리의 점에서 BFS를 돌려 제일 먼 거리를 구해주면 된다. 이것에 대한 증명을 고수들이 하던데, 나는 아직 증명까지는 잘 못하겠다. 여튼 BFS 두개를 돌려 해결한 문제이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include#include#include#includeusing namespace std;vector tr[100001];bool visited[100001];int sum[100001];int n, to, from, len, res, tota..

https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 간선으로 연결된 정점들의 집합이 몇 개 있는지 구하는 문제이다. DFS나 BFS로 풀 수 있다. 흔히 영역을 구하는 문제와 비슷한 것 같다. 오늘은 간단하게 코드만 올리겠다. 12345678910111213141516171819202122232425262728293031323334353637383940#include#incl..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net "그래프 이론에서, 이분그래프란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강 색과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다." - wiki 좀 더 설명하자면, 이 문제에서 위와 같은 그림은 이분 그래프이다. 한 정점이 빨간색이면 간선으로 연결된 정점은 다른 색을 가져야 한다. 같은 색을 가지게 되면 이분 그래프가 아니다. 위와 같은 그래프를 보면 이 그래프가 이..

이 문제에서 key는 모든 채널을 체크해보는 브루트포스 방식을 사용하는 것이다. 나는 시험칠 때 모든 채널을 체크해볼 것을 생각해보지 못했다. 모든 채널을 체크하고 그 채널이 가능하면 몇 번 클릭하는지 계산하고 최솟값을 찾아내면 되는 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include using namespace std; bool broken[10]; // 나올 수 있는 채널인지 확인하는 함수. // 만약 나올 수 없는 채널이면 0을 반환, // 나올 수 있는 채널이면 그 채널의 길이를 반환한다. int ch..

연결요소의 정의는 다음과 같다. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are also sometimes called connected components. 한 요소로 연결된 그래프는 전체 그래프를 구성하기 위한 요소로 있는데, 이 요소는 연결요소라고 불린다. 쉽게 말해 연결된 그래프는 각각 하나의 연결 요소이다. 즉 이 그림에서는 3개의 연결 요소가 있다. 중요한 것은 점 한 개도 하나의 연결 요소라고 할 수 있다. 나는 그 점들을 처리를 안해줘서 많은 실패를 하였다. 저 연결요소를 찾는 것은 BFS를 이용해서 찾을 수 있다. 시작점에 대해 고민이 있었는데, 처..

A진법을 10진법으로 바꾸고, 10진법을 B진법으로 바꾸어 해결하는 문제이다. 나같은 경우 조건이 A진법의 자릿수가 25이하라는 것을 보고 당연히 10진법으로 바꾸지 않고 해결하는 방법이 있는 줄 알았으나 문제 말미에 "A진법으로 나타낸 수를 10진법으로 변환하였을 때의 값은 양의 정수이며 220보다 작다." 이라는 말이 있었다. 그래서 그냥 일반적인 진법 변환 코드를 만들어 해결해주었다. 1 2 3 4 5 6 void convertDecToB(int n, int base){ if(n == 0) return; convertDecToB(n / base, base); cout b >> len; num = 0; for(int i = 0; i > val; num = num * a + val; } convertD..

소수 구하기 살짝 응용이 된 문제로, N^2의 방법으로는 이 문제를 풀 수 없다. 문제를 간단히 설명하자면, 4보다 큰 짝수는 모두 소수의 합으로 표현 될 수 있다는 골드바흐의 추측을 근거로 짝수를 소수의 값으로 표현해보는 것이이다. 이 때 짝수 n의 범위는 6 ≤ n ≤ 1000000 이다. 그러므로 시간초과를 피하기 위해서는 O(n)으로 해결해야 한다. 우선, 에라토스테네스를 통해 1000000까지의 소수값을 한 번에 구한다. 나는 모르고 n을 할 때마다 소수값을 구해서 굉장히 오랜 시간이 걸렸는데 미리 소수값을 구해놓으면 시간이 더 이상 들지 않는다. 그럼 이제 에라토스테네스의 시간복잡도를 고려했야 하는데 에라토스테네스의 시간 복잡도는 O(n log log n) 이라고 한다. (https://en...

이 문제는 2진법에서 10진법으로 10진법에서 8진법으로 변환하는 문제가 아니라, 2진법에서 8진법으로 바로 바꾸는 방법이다. 왜냐하면 이진법의 길이가 1,000,000이기 될 수 있기 때문에 10진법으로 변환하면 큰일난다. 바로 바꾸는 방법은 진법 만큼 2^n 진법 만큼의 개수로 이동해주면 된다. 1234567891011121314151617181920212223242526272829#include#include#include#include using namespace std; int main(void){ vector nums; vector res; string n; int ans, i; cin >> n; for(char c : n) nums.push_back(c); reverse(nums.begin(..

www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 진법 변환 된 것을 10진법 수로 바꾸는 것이다. 정말 간단한 문제이지만 (기존 진법)^n으로 바꾸지 못해서 어려움을 겪었다. 123456789101112131415161718192021#include#include using namespace std; int main(void){ string s; int b, ans, len, i; cin >> s >> b; ans = 0; i = 0;len = 0; for(c..

www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net '(', ')' 를 이용하여 스택을 쌓는 문제이다. 정석은 스택을 이용하는 것이기에 스택을 이용하여 해주었다. 나는 스택 라이브러리를 사용하였는데 사람들이 해놓은 것을 보니 배열로 count 만 해주면 되기에 배열로 해줘도 되어보였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include #include using namesp..