개발윗미

C++로 구현한 11377번 열혈강호 3 구하기 문제 풀이입니다. https://www.acmicpc.net/problem/11377 11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있 www.acmicpc.net #include #include #define MAX 1001 using namespace std; vector a[MAX]; int d[MAX]; bool c[MAX]; int n, m, s, k, input=0; bool dfs(int x) { for(int i=0; i

C++로 구현한 11376번 열혈강호 2 구하기 문제 풀이입니다. https://www.acmicpc.net/problem/11376 11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, www.acmicpc.net #include #include #define MAX 1001 using namespace std; vector a[MAX]; int d[MAX]; bool c[MAX]; int n, m, s; bool dfs(int x) { for(int i=0; i

C++로 구현한 11375번 열혈강호 구하기 문제 풀이입니다. https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net #include #include #define MAX 1001 using namespace std; vector a[MAX]; int d[MAX]; bool c[MAX]; int n, m, s; bool dfs(int x) { for(int i=0; i

C++로 구현한 2188번 축사 배정 구하기 문제 풀이입니다. https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net #include #include #define MAX 201 using namespace std; vector a[MAX]; int d[MAX]; bool c[MAX]; int n, m, s; bool dfs(int x) { for(int i=0; i

문자열 매칭 알고리즘은 특정한 글이 존재할 때 그 글 내에서 하나의 문자열을 찾는 알고리즘이다. 특정한 글 H e l l o 위와 같이 특정한 글이 Hello 로 존재하고 문자열 ll을 찾는다고 가정할 때 (1) 먼저 찾을 문자열인 ll을 가장 앞에 위치시켜 해당 문자열이 동일한지 확인한다. 특정한 글 H e l l o 찾을 문자열 l l (2) 매칭이 이루어지지 않았으므로 다음 한 칸 이동시켜 해당 문자열이 동일한지 확인한다. 특정한 글 H e l l o 찾을 문자열 l l (3) 매칭이 이루어지지 않았으므로 다음 한 칸 더 이동시켜 해당 문자열이 동일한지 확인한다. 특정한 글 H e l l o 찾을 문자열 l l => 해당 문자열에 대하여 매칭이 이루어진 것을 확인할 수 있다. [예제] #includ..

이분 매칭은 집단이 존재할 때 A 집단이 B 집단을 선택하는 방법이다. 아래와 같이 숫자 집단과 알파벳 집단이 있다고 가정하고, 1번은 알파벳 A, B, C 를 선택하고 2번은 알파벳 A를, 3번은 알파벳 C를 선택했다고 할 때 이분 매칭은 모든 숫자가 각각의 알파벳을 선택하여 가장 많이 연결되는 경우를 탐색할 수 있도록 한다. (1) 먼저 알파벳 A가 아무 번호에도 연결되어 있지 않기 때문에 1번이 알파벳 A를 선택한다. (2) 2번이 A를 선택하는데 A는 1번에 연결되어 있기 때문에 A를 점유하고 있는 1번부터 다시 출발하여 A를 제외하고 다른 곳에 연결될 수 없는지 확인한다. (3) 1번은 알파벳 B에 연결될 수 있기 때문에 B에 연결하고 2번은 A에 연결한다. (4) 3번이 B를 선택하는데 B는 ..

C++로 구현한 2252번 줄 세우기 문제 풀이입니다. https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net #include #include #include #define MAX 32001 using namespace std; int n, inDegree[MAX], result[MAX]; vector a[MAX]; void topologySort() { queue q; for(int i=1; i

플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 탐색하는 알고리즘이다. 다음과 같은 그래프가 존재할 때, 각각의 정점이 다른 정점으로 가는 거리(비용)을 2차원 배열로 나타내면 아래와 같다. 0 5 INF(무한) 8 7 0 9 INF(무한) 2 INF(무한) 0 4 INF(무한) INF(무한) 3 0 위 표는 현재까지 계산된 최소 비용이며, 이러한 2차원 배열을 반복적으로 갱신하여 모든 최소 비용을 구하는 과정은 아래와 같다. (1) 노드 1을 거쳐가는 경우 [ 2->3 ] 노드 1을 거쳐가야 하기 때문에 1을 포함하지 않은 경우들만 계산해주면 된다. 0 5 INF(무한) 8 7 0 [ 2->3 ] [ 2->4 ] 2 [ 3->2 ] 0 [ 3->4 ] INF..

에라토스테네스의 체는 소수를 찾는 방법이다. 여기서 소수는 1과 자기자신을 약수로 가지는 모든 자연수이며, 대표적으로 2, 3, 5, 7, 11, 13, ... 등이 존재한다. 우선, 에라토스테네스의 체를 사용하지 않고 기본적인 소수 판별 코드는 다음과 같다. [소수 판별 기본 코드] #include bool isPrimeNumber(int x) { for(int i=2; i

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 즉, 크루스칼 알고리즘은 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이다. 그림과 같은 그래프에서 정점은 7개, 간선은 11개 이다. 가장 적은 비용으로 모든 노드를 연결하는 최소 비용 신장 트리를 만들 때 사용되는 간선의 개수는 6개 이다. 즉, 최소 비용 신장 트리를 만들 때 사용되는 간선의 개수는 노드 개수 -1 이다. 최소 비용 신장 트리는 거리를 기준으로 오름차순 정렬을 한 후 그래프를 연결함으로써 만들 수 있다. 주의할 점은 정렬된 순서에 맞게 그래프에 포함시키기 전에 사이클이 형성되면 안된다. 그렇기 때문에 사이클 테이블을 먼저 확인한 후, 만약 사이클을 형성하는 경우에는 간선을 포함하지 않도록..