초보개발자

입력: 조규현 좌표와 류재명과의 거리(x1, x2, r1), 백승환의 좌표와 류재명과의 거리(x2, y2, r2) (-10,000 ≤ x1,y1,x2,y2 ≤ 10,000 정수, r1,r2 ≤ 10,000 자연수)출력: 류재명의 좌표가 될 수 있는 좌표의 경우의 수. 만약 무한대라면 -1소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int main() { int t; scanf("%d", &t); while (t--) { int x1, y1, x2, y2, r1, r2; scanf("%d%d%d%d%d%d", &x1, &y1, &r1, &x2, &y2, &r2); double d = sqrt((x1 - x2)*(x1..

입력: 테스트 케이스 T 구하고자 하는 숫자 N출력: 1, 2, 3으로 이용하여 표현할 수 있는 경우의 수 예: 4를 표현한다고 하면 아래와 같은 경우의 수가 있다1+1+1+1 / 1+1+2 / 1+2+1 / 2+1+1 / 2+2 / 1+3 / 3+1알고리즘: 동적계획법, 피보나치 수열소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int main() { int n, t; scanf("%d", &t); vector dp(12, -1); dp[1] = 1; dp[2] = 2; dp[3] = 4; for (int i = 4; i

입력: 수빈이 위치 N 수빈이 동생 위치 K 100,000이하의 자연수출력: 수빈이가 동생을 찾기 위해 걸리는 최소 시간조건: 수빈이는 현재 자리에서 한 칸 앞으로 가거나 뒤로 갈 수 있으며 두 배로 이동할 수 있다.알고리즘: BFS소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; #define MAX 100000 #define min(a, b) (a < b ? a : b) int main() { int n, k; scanf("%d%d", &n, &k); vector step(MAX + 1, MAX + 1); step[n] = 0; queue time; time.push(n); while (!time.e..

입력: 나무 개수 N, 총 자르려는 나무의 합 M, N개의 나무 길이출력: 적어도 M 길이의 나무를 자를 수 있는 최댓값알고리즘: 이분법, 이분탐색소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; typedef long long ll; int main() { int N, M; scanf("%d%d", &N, &M); vector tree(N); for (int i = 0; i 1) { mid =..

입력: 세로N 가로M 미로지도(1: 갈 수 있는 곳 0: 갈 수 없는 곳)출력: (1, 1)에서 (N, M)까지 가는 최소 칸 수알고리즘: BFS소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int main() { int n, m; scanf("%d%d", &n, &m); int maze[100][100]; bool visited[100][100]; for (int i = 0; i < n; i++) for(int j=0; j 0 && (maze[x - 1][y] == 1)) { maze[x - 1][y] = maze[x][y] + 1; road.push((x - 1) * 100 + y); } if (..

[알고리즘] Floyd-Warshall 이 알고리즘은 Transitive closure나 다대다 최단 거리를 구할 때 사용하는 알고리즘이다. 동적계획법(Dynamic Programming) 기법이 포함되어 있다. Transitive closure란 간접적으로 연결되어 있는 간선을 직접갈 수 있는 간선을 추가한 그래프이다.즉, 이 그래프는 원하는 정점이 서로 직접 혹은 간접적으로 연결되어 있냐를 확인할 수 있다. pseudo code는 아래와 같다. D: 주어진 인접행렬 for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| D[i][j] := D[i][j] | (D[i][k] & D[k][j]) return D D[i][j] := D[i][j] | (D..

입력: 테스트케이스 C(C≤50), 판자의 수(1≤N≤20,000), hi(0≤hi≤10,000)출력: 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기알고리즘: 세그먼트 트리, 분할정복소스코드#define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; #define MAX 20 * 1000 + 1 int N; vector wood, tree; void init(int, int, int); int retIndex(int, int, int, int, int); int maxS(int, int); int max(int a, int b) { return (a > b ? a : b); } int main() { int C; ..

[알고리즘] 위상정렬(topological sorting) 위상정렬은 그래프를 자료구조로 가지는 알고리즘으로 유향 그래프의 정점들을 한 방향으로 나열하는 것을 말한다. 예를 들어 김치찌개를 만드는 방법을 입력받았을 때 그것을 하나의 순서로 만드는 것이다. 여러 가지 순서를 가질 수 있으며, 특정 조건에 따라 우선순위 큐(priority queue)를 사용할 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 하며 이러한 그래프를 비순환 유향 그래프라고 한다. 위상정렬을 구현하는데 여러 방법을 쓰일 수 있는데, 나는 여기서 큐와 진입 차수(indegree)를 이용한 방법을 설명하려고 한다. 알고리즘 순서는 다음과 같다.1. 간선 정보를 초기화한다. 이 때, 문제에 따라 인접행렬..

분류: 구현, 그래프입력: 테스트 케이스 C( N >> M; adj = vector(N, vector(N, false)); indegree = vector(N, 0); string str; for (int i = 0; i > str; adj[str[0] - 'A'][str[1] - 'A'] = true; indegree[str[1] - 'A']++; } vector ret = topological(N); for (int i = 0; i < N; i++) cout

[알고리즘] 최소 스패닝 트리 - kruskal 알고리즘최소 스패닝 트리정의: 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리를 찾는 문제종류: kruskal 알고리즘, prime 알고리즘이 존재한다.kruskal 알고리즘정의: 최소 스패닝 트리를 구현하는 하나의 방법으로 가중치가 가장 작은 간선이 최소 스패닝 트리에 포함될 가능성이 높다는 생각에 착안되어서 만들어진 알고리즘 구현 방법: 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가를 한다. 단, 추가를 했을 경우 사이클이 발생하면 안되기 때문에 이 간선은 제외해야 한다.참고 문제: [LAN] 근거리 네트워크 http://yejin0730.tistory.com/10출처: 알고리즘 문제 해결 전략2