개발윗미

C++로 구현한 2217번 로프 문제 풀이입니다. https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net #include #include using namespace std; int main() { int n, w[100001], max=0; scanf("%d", &n); for(int i=0; i

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/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net #include #include #include #define MAX 501 using namespace std; int n, inDegree[MAX], result[MAX], time[MAX]; vector a[MAX]; void topologySort() { queue q; for(int i=1; i

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

위상 정렬은 순서가 정해져있는 작업을 차례대로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 주의할 점은 위상 정렬은 사이클이 발생하지 않는 방향 그래프 즉, DAG(Directed Acyclic Graph)에만 수행이 가능하다. 왜냐하면 위상 정렬은 기본적으로 시작점이 존재해야 하는데 사이클 그래프에서는 시작점부터 찾을 수 없기 때문이다. 위상 정렬을 수행하는 과정은 아래와 같다. 정점 1 2 3 4 5 6 7 진입차수 0 1 1 1 1 2 1 여기서 진입차수는 해당 정점에 들어오는 간선의 수이다. 즉, 정점6은 정점4와 정점5에서 간선이 들어오기 때문에 진입차수가 2이다. 또한, 정점1은 들어오는 간선이 없기 때문에 진입차수는 0이다. (1) 진입차수가 0인 정점1을 큐에 삽입한다..