알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 중간에서 만나기 방법을 사용하는 문제입니다. 배열 A, B, C, D에서 수를 한 개씩 뽑아 합이 0이 되게 만드는 문제입니다. 배열의 크기가 크기 때문에 모든 경우를 탐색하기에는 무리가 있습니다. 따라서, (A+B) / (C+D)로 나눠서 합을 구한 뒤, 둘을 합치는 방법을 사용합니다. 두 배열에 있는 수를 더하는 것이기에 합이 같은 경우가 있을 수 있습니다...

문제 링크입니다. https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net MAP을 사용하면 쉽게 풀 수 있는 문제였습니다. 숫자 카드 중, 가장 많은 카드를 구하는 문제입니다. 카드를 입력 받으면서 map을 통해 해당 카드의 갯수를 증가합니다. 마지막에 map을 통해 for문을 이용하면서 가장 많으면서 작은 수를 구해주면 됐습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #incl..

문제 링크입니다. https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 투포인터를 이용하는 문제였습니다. https://junseok.tistory.com/314 -> 이 문제에서 조건이 하나 추가된 문제입니다. 두 용액이 아닌, 3개의 용액을 선택해 값이 최소가 되는 것을 구하는 문제입니다. 두용액이였다면, 간단한 투포인터를 이용해 풀 수 있겠지만, 용액이 3개이기에 일반적인 방법으로 풀 수는 없었습니다. 가장 간단하게 생각할..

문제 링크입니다. https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 투포인터를 사용하는 문제입니다. 투포인터는 조건에 따라 양쪽 끝을 하나씩 줄여가면서 원하는 값을 찾는 방법입니다. 2개의 용액을 선택해 두 수의 차의 최솟값(절댓값)을 구하는 문제입니다. 그렇다면 크기 순으로 정렬한 뒤, 가장 큰 수와 가장 작은 수를 선택하면서 시작합니다. 그 후, 조건에 따라 자신보다 큰 수 혹은 작은 수를 선택해가면 답이 나올 것입니다. 문제 예시를 통..

문제 링크입니다. https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 투 포인터를 이용하는 문제입니다. 두 개의 용액을 선택해서 최대한 0에 가까운 값을 만드는 문제입니다. 백트래킹으로도 풀 수 있겠지만, N값이 100,000이기에 시간초과가 생깁니다. 따라서 이분탐색 중 투 포인터를 통해서 풀어야됨을 알 수 있습니다. 투 포인터는 양 끝의 범위를 잡아놓고, 조건에 따라 범위를 좁혀나가는 것을 의미합니다. 해당 문..

문제 링크입니다. https://www.acmicpc.net/problem/27112 27112번: 시간 외 근무 멈춰! 오늘도 여러 체계의 개발 임무를 열심히 수행 중인 준민이에게 갑자기 새로운 개발 프로젝트가 들어왔다. 해당 개발 프로젝트는 총 $N$개의 작업으로 이루어져 있으며, 각 작업은 $t_i$의 근무일 www.acmicpc.net 정렬을 이용한 문제입니다. 일의 마감시한과 걸리는 시간이 주어졌을 때, 이를 끝낼 수 있는지를 구하는 문제입니다. 일을 끝내긴 위해선 먼저 마감기한이 빠른 일부터 끝내야합니다. 따라서 정렬을 해야하는데, 데이터 값이 2개가 있습니다. 마감기한과 걸리는 시간입니다. 마감기한이 우선이기에 마감기한 -> 걸리는 시간 순으로 우선순위를 정해서 정렬을 해주면 됩니다. 정렬을..

문제 링크입니다. https://www.acmicpc.net/problem/24447 24447번: 알고리즘 수업 - 너비 우선 탐색 4 정점 1번에서 정점 2번, 정점 4번을 순서대로 방문한다. 정점 2번에서 정점 3번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 2, 4, 3, 0이다. 너비 우선 탐색 www.acmicpc.net BFS 문제였습니다. BFS 탐색을 할 때, 탐색 깊이와 탐색 순서를 저장해주는게 중요했던 문제입니다. 탐색 순서는 다른 정점을 방문할 때마다 1씩 증가하지만, 탐색 깊이는 이전 정점에서 1를 더한 값입니다. 두개를 잘 구분해주는게 중요합니다. 두 값을 곱한 뒤 더할 때는 int의 범위를 넘어가니 long long int ..

문제 링크입니다. https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net BFS의 순서를 확인할 수 있는지를 물어보는 문제였습니다. 1번부터 BFS 탐색을 시작했을 때, 주어진 순서가 올바른 BFS 방문 순서인지를 확인하는 문제입니다. 부모가 같은 노드가 다수일 경우, 방문 순서가 여러개가 나올 수 있습니다. 문제 예시에서는 (1, 2, 3, 4) or (1, 3, 2, 4)가 나올 수 있습니다. 여러개가 나올 수 있는 방문 순서 중 하나가 입력에 주어졌는지를 찾아야합니다. 나올 수 있는 모든 경우를 확인하는 방법보다는 문제에서 나온 경우만을 맞는지 확인하는 것이 효..

문제 링크입니다. https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net https://junseok.tistory.com/268 백준 24444 - 알고리즘 수업 - 너비 우선 탐색 1 (C++) 문제 링크입니다. https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 10..

문제 링크입니다. https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 간단한 BFS 문제였습니다. 일반적인 그래프 문제와 같이 백터를 이용해 양방향 간선을 저장해줍니다. 해당 문제에서는 방문하는 노드는 항상 오름차순이라고 정해졌으니, 백터에 저장된 값들을 전부 정렬해줘야 합니다. 정렬을 해준 뒤, 시작점부터 BFS 탐색을 해주면 됩니다. 이때 방문한 순서를 기억해줘야하니, ..

문제 링크입니다. https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net Union-Find로 풀 수 있는 문제입니다. BFS를 사용해서 풀 수 있는 문제이기도 합니다. 저는 BFS를 이용해 푸는 방법을 설명해드리겠습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #incl..

문제 링크입니다. https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 정렬을 이용한 그리디 문제입니다. 최소 강의실을 구해야하는 문제입니다. 강의를 최대로 이어서 할 수 있도록 만들어야합니다. 따라서 한 강의를 시작으로 최대한 다른 강의로 이어봅니다. 다른 강의를 시작할 수 없는 때가 온다면 강의실을 하나 추가하고 해당 강의를 시작합니다. 이러한 과정을 반복하면 강의실의 갯수를 구할 수 있습니다. 이를 우선순위 큐를 통해서 풀면 됩니다. 자세한 것은 코드를 참고해주세요 #define _CRT_S..