MY MEMO

그래프 원소와 원소사이를 다:다 연결을 해 놓는 것 정점과 간선으로 구성되어있으며 (1. 이차원 배열 2. 연결 리스트) 로 구현할 수 있다. 탐색 방법 그래프의 모든 노드를 탐색하고 싶을 때 = 그래프 순회 / 그래프 탐색이라고 한다 DFS (깊이 우선 탐색) : Stack으로 구현 BFS (넓이 우선 탐색) : Queue로 구현 신장 트리 정점이 n개 일때 n-1개의 간선을 가지는 트리 형태 DFS / BFS를 구하면 신장트리가 나옴 +) 트리와 그래프의 차이? 트리는 그래프의 일부분으로 Cycle이 없는 그래프를 의미 최소 비용 신장 트리 만약 간선들이 모두 가중치를 가지고 있다면? 신장트리를 만들때 어떻게 최소비용으로 만들 수 있을까? 크루스칼 알고리즘 간선들 사이의 가중치를 정렬한 후 정점들 사..

#include #include #include using namespace std; int eatCookie(vector cookies) { int answer = 0; int cookies_count = cookies.size(); vectorDP(cookies_count + 1, 0); for (int j = 0; j cookies[k]) if (Max < DP[k]) Max = DP[k]; } DP[j] = Max + 1; answer = max(answer, DP[j]); } return answer; } int main() { vector tes..

#include #include #include using namespace std; int change(int total, vector coin) { vectorcount(total + 1, 0); int coin_count = coin.size(); sort(coin.begin(), coin.end()); for (int j = 0; j < coin_count; j++) { count[coin[j]]++; for (int k = 1; coin[j] + k

#include #include #include #include using namespace std; //최대 공약수 long long gcd(long long A, long long B) { return (A%B == 0 ? B : gcd(B, A%B)); } //최소 공배수 long long lcm(long long A, long long B) { return A * B / gcd(A, B); } long long nlcm(vector num) { long long answer = 0; sort(num.begin(), num.end(), greater()); int num_count = num.size(); answer = num[0]; for (int j = 1; j < num_count; j++)..

출처 : http://suhak.tistory.com/77 #include #include using namespace std; /* 만약 ( 괄호가 나오면 반드시 ) 괄호가 나와야 함. ( 이 두 번 나오면 ) 도 반드시 두 번 나와야 함. 쌍을 이루는 것들을 나열하는 모든 경우의 수를 카탈란 수라고 한다. (1) 첫 번째는 2차원 배열에서 한 지점 A에서 B까지 가는 최단경로의 수다. 왜냐하면, A에서 B지점까지 최단경로로 도착하기 위해선 단 두 가지 방향의 쌍으로 이루어진다. 가장 간단히 다음과 같은 배열이 있다. 0 0 B 0 0 0 A 0 0 여기서 A에서 B로 최단경로로 도착하려면, 오른쪽아니면 위쪽 밖에 길이 없다. 그리고 반드시 이 방향은 대칭된다. 그렇기에 카탈란 수에 속한다. (2) n..

http://book.algospot.com/estimation.html

#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));..

분할 정복은 말 그대로 문제를 두 단계, ①분할과 ②정복으로 나눠서 해결하는 것을 말합니다. 분할하는 단계에서는 말 그대로 주어진 문제를 여러 개의 부분 문제들로 나누는데, 문제가 작아지면 작아질수록 풀기 쉬워지는 성질을 이용한 겁니다. 또한 문제의 크기가 엄청나게 줄어든다면(N=1 또는 N=2 정도) 그야말로 바로 답을 구할 수 있는 수준이 되고, 이게 재귀호출로 문제를 풀 때의 기저 사례(base case)와 같습니다. 그렇습니다. 대체로 분할 정복은 재귀 호출과 아주 죽이 잘 맞습니다. 그리고 기저 사례들로 각 문제의 답을 풀고, 그 문제들을 불렀던 조금 더 큰 문제는 이 답들을 통해 비교적 간단한 연산처리만 해주면 자신의 답도 구할 수 있습니다. 이런 식으로 첫 문제까지 쌓아올려가며 답을 풀어내는..

탐욕 알고리즘 이란? 이후의 과정을 생각하지 않고 지금 내가 고를 수 있는 값 중 나에게 가장 이익이 되도록 고르는 것이다. 탐욕 알고리즘 관련 문제는 회의실 정하기, 거스름돈 주기 등의 문제가 존재한다. 1) 회의실정하기 만약 일정한 시간에 여러 시간대의 예약이 들어왔다고 하자. 그 일정한 시간대 안에 최대한 많은 예약을 잡고 싶다. 그렇다면 어떻게 풀어야할까? 2) 거스름돈 주기 나에게 남은 동전이 X만큼 있다. 이를 이용하여 최소로 동전을 거슬러 줄 수 있는 경우를 출력하라. 위의 두 문제는 전형적인 탐욕 알고리즘이다. "회의실 정하기"에서는내가 예약을 많이 잡고 싶다면 끝나는 시간이 짧은 것부터 넣으면 된다.이는 priority queue를 이용하면 되고 문제해결기법 Week7의 Programal..