본문 바로가기

운동하는 개발자/알고리즘, 코딩테스트

 (40)
Beakjoon] 줄 세우기(백준 2252코테) - 그래프 (C++) 🅰️문제주소 : https://www.acmicpc.net/problem/2252 🚩문제 🪡풀이 - 답이 여러 개인 경우가 존재할 수 있으면 위상정렬을 떠올려야 한다 (위상정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘) - 학생의 키 비교를 2차원 벡터로 map화 하여 저장하고 해당 학생 수만큼 진입차수 배열을 만든다 - 키 비교가 되었을 경우 비교된 학생의 배열값을 증가시킨다 - 진입차수가 0인 노드부터 queue에 넣은 뒤 출력시키고 해당 노드가 가리키는 노드의 진입차수 값을 1 감소시킨다 (이때 감소시킨 값이 0 이면 큐에 집어넣는다) - 큐 전체가 비어있을 때까지 반복 ☕코드는 아래 숨김 더보기 #include #include #include int main() { std::io..
Beakjoon] 여행 가자(백준 1976코테) - 그래프 (C++) 🅰️문제주소 : https://www.acmicpc.net/problem/1976 🚩문제 🪡풀이 - 이동하기 원하는 길이 모두 이어져있는지 union find를 통해 간단하게 찾을 수 있다 - 각 노드(도시)가 이어진 루트 노드를 별도의 배열에 저장해 둔다. - 이어진 길은 union find로 재귀 탐색하며 루트노드의 값으로 업데이트시킨다 - 트리구조에서 스타구조 모형으로 점점 변해가며 시간복잡도가 줄어든다. ☕코드는 아래 숨김 더보기 #include #include std::vector ROAD; int find(int a) { if (a == ROAD[a]) return a; return ROAD[a] = find(ROAD[a]); } void UnionFunc(int a, int b) { a = ..
Beakjoon] 물통 (백준 2251코테) - 그래프 (C++) 🅰️문제주소 : https://www.acmicpc.net/problem/2251 🚩문제 🪡풀이 - 그래프로 map을 그려놓고 BFS, DFS 하는 것이 아닌 역으로 그래프를 그리는 문제 - 2차원 길찾기와 유사하게 물의 이동의 케이스를 배열로 구성한다. (0->1, 0->2, 1->0, 1->2, 2->0, 2->1) - 방문여부는 A와 B의 물통 양으로 이차원 배열을 만들어서 체크한다. - A, B, C의 물통의 양을 입력받은 뒤 BFS탐색을 시작하되 이동할 노드를 큐에 추가하고(예:0에서 1) 방문한 경우는 제외시킨다. - 받는물통한테 보내는 물통의 모든 용량을 추가한 뒤 기존 물통의 크기를 초과한 경우 초과한 만큼 다시 보내는 물통으로 보낸다. 초과하지 않았을 경우 보내는 물통은 0을 저장한다. ..
Beakjoon] Ax+By=C (백준 21568코테) - 정수론 (C++) 🅰️문제주소 : https://www.acmicpc.net/problem/21568 21568번: Ax+By=C A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자. x, y는 정수 -1,000,000,000 ≤ x, y ≤ 1,000,000,000 www.acmicpc.net 🚩문제 🪡풀이 - ax+by = c 의 방정식의 해를 구하기 위해서는 확장 유클리드 호제법을 호제법을 사용해야 한다 - c % gcd(a,b) == 0 인 경우에만 정수해를 가지므로 먼저 체크 - 유클리드 호제법을 수행하되 x와 y의 이전값을 가지고 역순으로 계산하며 답을 찾아낼 수 있다 - x는 y', y는 x'-y'*q를 역순으로 계산한다. (이때 x' 는 x의 이전..
Beakjoon] 최소공배수 (백준 1934코테) - 정수론 (C++) 🅰️문제주소 : https://www.acmicpc.net/problem/1934 🚩문제 🪡풀이 - 우선 유클리드 호제법으로 최대공약수를 구해야한다 - 최소공배수 = 'A*B / 최대공약수' 공식에 대입한다 끝 ☕코드는 아래 숨김 더보기 #include int main() { std::ios::sync_with_stdio(false); std::cout.tie(0); std::cin.tie(0); int T, A, B; std::cin >> T; for (int i = 0; i > A >> B; int big, small; if (A
Beakjoon] GCD(n, k) = 1 aka.오일러의 피 (백준 11689 코테) - 정수론 (C++) 🅰️문제주소 : https://www.acmicpc.net/problem/11689 🚩문제 🪡풀이 - 주어진 수에서 그 수보다 작은 자연수 중 최대공약수가 1이 되는 수(서로소)의 개수를 구하는 것으로 오일러의 피 함수를 구현할 줄 아는지 묻는 문제 - 소수를 구하는 에라토스테네스의 체와 비슷하게 구현가능한데 배수를 0으로 지우는 부분 대신 P[i] = P[i] -[Pi]/K 로 변경해 주면 된다 - 해당문제는 한번의 입력만 주어지기에 따로 배열에 저장할 필요 없이 매번 새로 구하게 하면 된다 ☕코드는 아래 숨김 더보기 #include #include #include int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie..
Beakjoon] 제곱 ㄴㄴ 수 (백준 1016 코테) - 정수론 (C++) 🅰️문제주소 : https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 🚩문제 🪡풀이 - 에라토스테네스의 체를 응용해야 한다. 제곱수로 나누어 떨어지지 않는 수를 찾아야 하므로 반대로 제곱수를 계속 곱해가며 지워나가야 한다. - 값이 무엇인지가 중요한 게 아니라 개수만 체크하면 되기에 bool타입의 배열을 사용한다. - min과 max의 값이 엄청 크므로 overflow에 주의해야 한다. - 추가로 메모리 사용에도 주의해야 한다 ☕코드..
Beakjoon] 소수 구하기 (백준 1929 코테) - 정수론 (C++) 🅰️문제주소 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 🚩문제 🪡풀이 - 최대 범위가 1,000,000으로 주어졌으므로 에라토스테네스의 체를 사용해야 한다. O(Nlog(logN)) 의 시간복잡도를 가진다 - 연산하기 쉽게 0에서 N까지 모두 벡터에 넣은 뒤 에라토스테네스의 체를 돌리며 소수가 아닌 수는 0으로 변경시킨다. - M에서 N사이의 0이 아닌 값을 출력한다. ☕코드는 아래 숨김 더보기 #include #include #include int main() { ..

티스토리툴바