728x90 🥇Baekjoon Solutions73 [C++] 그리디 알고리즘 예시 코딩 문제 작업의 수 N(1~100,000), 제한시간 D(1~10,000,000) 작업을 다수의 컴퓨터로 수행할 시 작업을 최소의 컴퓨터로 수행하는 컴퓨터의 수를 구하시오. 예시 1 10 14 7 5 4 6 1 2 3 5 2 3 computer1 : 7 3 2 computer2 : 5 1 2 5 computer3 : 4 6 3 #include #include // 작업목록을 담을 work 벡터 #include // 가까운 시간대를 찾기위한 우선순위 큐 #include // 배열 초기화 memset사용 using namespace std; int main(void) { ios_base::sync_with_stdio(false); cout.tie(); cin.tie(); int TC, N, D, input; i.. 2021. 8. 21. [C++] 백준 4386번: 별자리 만들기 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 유니온-파인 알고리즘의 개념과 이미 연결되어 있는 그래프를 파악하여 그래프에 사이클이 존재하는지 여부를 지속적으로 확인하여 줍니다. 이러한 기법을 크루스칼 알고리즘 또는 최소 스패닝 트리라고 합니다. #include #include #include #include using namespace std; class edge { public: int node[2]; float distance; ed.. 2021. 8. 19. [C++] 백준 4195번: 친구 네트워크 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 유니온-파인 알고리즘과 해쉬맵을 활용하여 풀이를 진행하였습니다. 해쉬맵은 인덱스가 많을 시 효율성이 떨어지지만 이렇게 자료가 한정적인 문제에서는 사용에 유리합니다. #include #include #include using namespace std; int N, M, parent[200001], cnt[200001]; map m; int find(int index) { if (pa.. 2021. 8. 19. [C++] 백준 2638번: 치즈 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 깊이 우선 탐색(DFS) 그래프 탐색 방식과 너비 우선 탐색(BFS) 방식을 모두 사용하여 문제 풀이를 진행 하였습니다. #include #include using namespace std; queueq, p;//q:치즈 위치 저장, p:이번 턴에 녹을 치즈들 int N, M; int page[101][101]; //탐색 방향 위, 아래, 왼쪽, 오른쪽 int idx[4] = {.. 2021. 8. 19. [C++] 백준 2108번: 통계학 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 풀이 각각의 단어에 맞는 식을 구현하였습니다. #include #include #include #include using namespace std; int coordinate[500001]; int cnt[8001]; int main() { vectorv; int N, k, total = 0; cin >> N; for (int i = 0; i > k; total += k; v.pu.. 2021. 8. 19. [C++] 백준 1976번: 여행 가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 그래프 탐색 기법을 이용하여 풀이를 진행하였습니다. 활용된 알고리즘으로는 유니온-파인 알고리즘을 활용하여 그래프들의 연결 상태를 파악하며 그래프 탐색을 진행합니다. #include using namespace std; int city[201]; int node[1001]; //보통 union find 알고리즘을 사용할 때 갱신을 작은 수쪽으로 수정해줍니다. //parent 찾기 int get.. 2021. 8. 19. [C++] 백준 1774번: 우주신과의 교감 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 우선 최소 스패닝 트리 알고리즘이 사용되었고 이는 유니온-파인 알고리즘에 바탕을 둡니다. 다른 점으로는 클라스를 통해 트리 형태를 구현해 줍니다. 이와 함께 최소 스패닝 트리 구현을 진행해 줍니다. #include #include #include #include using namespace std; class edge { public: int node[2]; dou.. 2021. 8. 19. [C++] 백준 1717번: 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 풀이 유니온-파인 알고리즘의 기본문제로 배열을 정의하고 앞서 배운 유니온 파인 알고리즘의 함수를 가지고 풀이를 진행하였습니다. #include using namespace std; int parent[1000001]; //parent 찾기 int getParent(int parent[], int x) { if (parent[x] == x)return x; .. 2021. 8. 19. [C++] 백준 1431번: 시리얼 번호 https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루 www.acmicpc.net 풀이 기초적인 정렬 문제로 문자를 비교하여 정렬하는 방식을 사용합니다. 이전에 진행한 알고리즘 라이브러리의 sort 함수를 사용하여 풀이를 진행합니다. #include #include #include using namespace std; int num(char k) { if (k == '0') return 0; if (k == '1') return 1; if (k == '2') retur.. 2021. 8. 19. 이전 1 2 3 4 5 6 7 8 9 다음 728x90
