개발윗미

파이썬에서 특정한 프로그램의 수행 시간을 측정하는 기본적인 코드는 다음과 같다. import time start = time.time() end = time.time() print("수행시간 :", end - start) time라이브러리를 활용하며, 측정을 종료한 시점 - 측정을 시작한 시점 연산으로 쉽게 구할 수 있다.

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

문자열 매칭 알고리즘은 특정한 글이 존재할 때 그 글 내에서 하나의 문자열을 찾는 알고리즘이다. 특정한 글 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는 ..

플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 탐색하는 알고리즘이다. 다음과 같은 그래프가 존재할 때, 각각의 정점이 다른 정점으로 가는 거리(비용)을 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

다이나믹 프로그래밍은 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. 다이나믹 프로그래밍으로 피보나치 수열의 문제 점을 해결할 수 있는데, 피보나치 수열은 특정한 숫자를 구하기 위해 특정한 숫자 바로 앞에 있는 수와 두 칸 앞에 있는 수의 합을 구하는 방식이다. 피보나치 수열은 동일한 문제를 다시 풀어 비효율적이라는 문제점이 있다. 다이나믹 프로그래밍은 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다는 가정 하에 사용이 가능하다. 다이나믹 프로그래밍을 통해 피보나치 수열의 문제점을 해결하기 위해서는 이미 계산한 결과를 배열에 저장함으로써 나중에 동일한 계산을 해야할 때 저장된 값을 단순히 반환하도록 한다. [예제] #include int d[..

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

유니온 파인드 알고리즘은 여러 개의 노드가 존재할 때 두 개의 노드를 선택하여 서로 같은 그래프에 속해 있는지 판별하는 그래프 알고리즘이다. 그림과 같이 부모를 합칠 때 일반적으로 더 작은 값 쪽으로 합친다. 그림에 대해 구체적으로 설명하자면, (1) 노드가 모두 연결되지 않은 상태에서의 각 노드의 부모노드는 자기 자신을 가리킨다. (2) 1과 2를 연결하면 2의 부모노드는 더 작은 값인 1 이다. (3) 2와 3을 연결하면 3의 부모노드는 더 작은 값인 2 이지만, 재귀 함수를 통해 결과적으로 1이 부모노드가 된다. [예제] #include int getParent(int parent[], int x) { if(parent[x] == x) return x; return parent[x] = getPar..