목록ALGORITHM (123)
MY MEMO
풀이방법은... 결국 카드가 움직이는 곳은 규칙이 있게 된다. 먼저 그 규칙을 모두 저장하고 돌리면 매우 느려지니 구하면서 저장하고 반복된다면 저장한 것으로 돌린다. board를 sorting하여 binary search를 이용하였고 시간을 줄일 수 있었다. #include #include #include #include #include #include using namespace std; #define PAIR pair vector A_card, B_card; vector A_multiple_card, B_multiple_card, board; int binary_search(int front, int rear, int result) { while (front + 1 < rear) { int mid =..
#include #include #include #include #include #include using namespace std; #define INT_MAX 2147483647 int result, goal_num; vectornum_arr; int main() { int for_count, num_count, goal_num; cin >> for_count; for (int i = 1; i > num_count >> goal_num; result = INT_MAX; num_arr = vector(num_count); queue cal_num; for (int j = 0; j > num_arr[j]; int sum = 0, index = 0, result =..
DFS로 문제를 풀었다.DFS는 역시 queue이다!! queue에 아직 visit되지 않은 node를 넣고 돌린다. 하지만 여기서는 한 가지의 조건이 더 붙는다.바로 A와 A, B와 B가 함께 살지 않는 조건이다. 따라서 문제는 아주 직관적으로 풀었다. people이라는 곳에 first에 visit를 체크하고second에 A와 B를 구별했다. 만약 people에 방문한 적이 있다면 A와 B중 무엇인지 결정이 되어있기 때문에방문한 마을의 people type과 현재 마을의 people type을 비교해서 같으면 함께 살수 없다. #include #include #include #include #include #include using namespace std; #define A 0 #define B 1 ..
목표의 수에 얼마나 가까이 도달 할 수 있는지 확인해보는 문제이다. 가장 큰 수부터 비교해보고 점점 작게 간다. 가장 작은 수를 0개를 두고 가장 큰 수까지 간 후가장 큰 수를 1씩 더하며 비교해 보는 식으로 짰다. 즉 DP이다. 하지만 DP의 목적은 역시 memorization이지 않을까 싶다. 곰곰히 어디에다가 쓸수 있을 까 생각해보다가 내가 이미 계산해서 가능하다고 나왔던 숫자에 표시를 해놓으면 어떨까 하고 생각했다. 따라서 목표값 - 남은값의 index에 표시를 해놓고 이후 또다시 이 숫자에 접근을 한다면 이 값은 계산할 수 있다고 바로 표시해 놓는다. 뿐만 아니라 이 뜻은 숫자를 이용해서 목표한 숫자를 만들수 있다는 뜻이므로 가장 가까운 수를 더 찾아볼 필요도 없이 return 해준다. +) 문..
다익스트라 알고리즘을 활용하는 문제이다. source부터 destination까지의 최단 거리를 구한 후 세일하는 티켓의 가격과 비교해서 작은 지 큰지를 비교한다. 만약 source부터 destination까지 바로 가는 구간이 있다면 바로 티켓과 비교하면 된다. 다익스트라를 처음 구현해본다면 시간이 걸릴 문제이지만 간단하게 구할 수 있는 문제이다. #include #include #include #include #include using namespace std; #define PAIR pair #define INT_MAX 2147483647 int sale_ticket, ticket_count, station_count; vector > statio..
#include #include #include #include #include using namespace std; #define PAIR pair //pair> int node_count; vector graph; vector result_path; void dikstra(int start, int end) { priority_queue cache; //거리가 최소인 것부터 정렬 vector visited = vector(node_count + 1, 0); //visited vector road = vector(node_count + 1, INT_MAX); //최소 경로 - 최대 값으로 저장해놓음 vector way; //경로 임시 저장 visited[start] = 1; way.push_back(s..
피보나치 #include #include using namespace std; vector dp; int fibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; // 이미 값을 계산한 적이 있다면 그 값을 바로 리턴 if (dp[n] != -1) return dp[n]; // 아니라면 계산해서 dp 리스트에 넣어 보존 dp[n] = fibonacci(n - 2) + fibonacci(n - 1); return dp[n]; } int main() { int N; scanf("%d", &N); dp.resize(N + 1, -1); // 초기값 -1은 fibonacci 결과로 절대 나올 수 없는 값 printf("%d\n", fibonacci(N));..
바이러스가 걸린 곳에 백신을 뿌린다. 백신의 값이 바이러스의 값보다 크거나 같으면 바이러스는 사라지고 백신의 값이 바이러스보다 작으면 멈춘다. 백신을 놓는 곳에서 백신이 퍼지는 데 바이러스의 절반 이상이 사라질 수 있는 최소의 백신의 값이 얼마인가? #include #include #include #include #include using namespace std; #define PAIR pair > vector > virus, visit; int vaccine_count, row_count, column_count; void check_virus(int index1, int index2, int vaccine_) { if (vi..
숫자를 받은 후 소수의 개수를 새어 기약분수로 나타내는 코드이다. 에라토스테네스의 체 참고 : http://marobiana.tistory.com/91 #include #include #include #include #include using namespace std; vector Prime_Number = vector (100001, 1); void check_Prime() { Prime_Number[1] = 0; for (int i = 2; i for_count; check_Prime(); for (int i = 1; i > number_count; vector number = vector (number_count); for (int k = 0; ..
분할 정복은 말 그대로 문제를 두 단계, ①분할과 ②정복으로 나눠서 해결하는 것을 말합니다. 분할하는 단계에서는 말 그대로 주어진 문제를 여러 개의 부분 문제들로 나누는데, 문제가 작아지면 작아질수록 풀기 쉬워지는 성질을 이용한 겁니다. 또한 문제의 크기가 엄청나게 줄어든다면(N=1 또는 N=2 정도) 그야말로 바로 답을 구할 수 있는 수준이 되고, 이게 재귀호출로 문제를 풀 때의 기저 사례(base case)와 같습니다. 그렇습니다. 대체로 분할 정복은 재귀 호출과 아주 죽이 잘 맞습니다. 그리고 기저 사례들로 각 문제의 답을 풀고, 그 문제들을 불렀던 조금 더 큰 문제는 이 답들을 통해 비교적 간단한 연산처리만 해주면 자신의 답도 구할 수 있습니다. 이런 식으로 첫 문제까지 쌓아올려가며 답을 풀어내는..