노는 게 제일 좋아

처음부터 생각하기는 힘들다. DP라는 것을 예상할 수 있지만 점화식을 바로 생각하기는 어렵다. https://www.acmicpc.net/problem/1699 #맞는 풀이 #include #include using namespace std; // 100000을 루트하면 대충 350 이하.. //또한 최소항의 수를 만들기 위해 큰 것부터 집어넣기로함, 그리드 // 그리드로 안풀림..ㅎ dp로 풀어야할 듯. int arr[100001]; int N; int main(){ cin >> N; //모든 N에 대해서 최소항의 개수를 찾아봄 for(int i = 1; i 어떤 제곱수 항을 가져야 최소 개수를 가질지 다 뒤져봄 // -> 그리디는 틀린 방식 18 = 4^2,1^2,1^2 지만 사실 3^2,3^2가 더..

실제로 MST, 최소 신장 트리를 구현하면 된다. 나는 Prim 알고리즘을 썼다. https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net #맞는 풀이 #include #include #include #define MAX 10005 using namespace std; using ti3 = tuple; int v,e; // 정점, 간선 개수 vector adj[MAX]; //인접 행렬 bool check[M..

문제에서 모든 컴퓨터가 연결되었다. 최소비용이다를 보고 최소신장트리가 생각나면 정답이다. https://www.acmicpc.net/problem/1922 #맞는 풀이 #include #include #include #include #define MAX 1001 using namespace std; using ti3 = tuple; int n,m; vector adj[MAX]; //1000개는 인접행렬로 부담스러움(뭐 1000개까진 괜찮다 사실) //cost, to가 들어갈 예정 bool check[MAX]; //이미 이어져있는지 확인 int Prim(){ int cnt = 0; int tot = 0; priority_queue heap; //1번부터 시작함 for(auto next : adj[1]){ ..

플로이드 문제를 하나 더 살펴봤다 이것이 더욱 플로이드 알고리즘의 핵심인 최단거리에 가까울 것이다. 역시 노드는 100개정도로 별로 없다. https://www.acmicpc.net/problem/11404 #맞는 풀이 #include #include #define MAX 105 #define INF 123456789 using namespace std; int n, m; int path[MAX][MAX]; int main() { cin >> n >> m; //테이블 초기화(처음엔 모두 INF) (1부터 n까지) for (int i = 1; i > from >> to >> cost; path[from][to] = min(cost, path[from][to]); //방향 그래프 } //자기 자신으로 돌아오..

플로이드 알고리즘으로 해결했다. 플로이드를 조금 더 풀어봐야겠다. https://www.acmicpc.net/problem/11403 #맞는 풀이 #include #define MAX 101 using namespace std; int N; int adj[MAX][MAX]; void floyd() { //i -> j는 바로 안가도 다른 노드를 거쳐서 가도 된다. //i -> k -> j 가능 for (int k = 1; k N; for (int i = 1; i adj[i][j]; //방향 그래프임. } } floyd(); for (int i = 1; i

한 번 갔던 간선에 대해 다시 갈 수 있으므로 연결해줄 때 양방향으로 연결해줘야 했다. 남들은 잘보이지만 나는 이것만 30분 넘게.. 걸렸다. 그리고 어차피 최단경로 = 최단경로 + 최단경로라고 생각해도 된다. https://www.acmicpc.net/problem/1504 #맞는 풀이 #include #include #include #include #include #include #define MAX 803 #define INF INT_MAX using namespace std; int N, E; vector adj[MAX]; //인접행렬 long long dist[MAX]; long long dist1[MAX]; //v1을 위한 long long dist2[MAX]; //v2를 위한 int v1, ..

다익스트라의 개념이 조금 더 나아간 것이다. 최단거리로 갱신했을 때는 해당 경로가 정해진다는 것을 기록하면 되는 문제다. https://www.acmicpc.net/problem/11779 #맞는 풀이 #include #include #include #include #include #include #define MAX 1002 #define INF 987654321 using namespace std; int st, ed; int N, M; int dist[MAX]; vector adj[MAX]; int path[MAX]; void dijkstra() { dist[st] = 0; priority_queue heap; heap.push({ dist[st], st }); while (!heap.empty()..

다익스트라 알고리즘 또 까먹었다. 오늘은 3문제 정도 풀어봐야겠다. https://www.acmicpc.net/problem/1916 #맞는 풀이 #include #include #include #include #include #define MAX 1001 // 1000개 정도면 인접행렬 만들만하다. #define INF 987654321 //적당히 큰 숫자여야한다. using namespace std; int N; //도시 수 int M; //버스 수 int st, ed; //시작노드, 목표노드 vector adj[MAX]; //벡터를 넣는 배열 {거리, 노드} int dist[MAX]; //최소거리 테이블 void dijkstra(){ dist[st] = 0; //전역으로 시작노드를 받음. prior..

CPU 스케줄링에서도 엄청 많이 나오는데.. 우리는 동적으로 사람이 들어오진 않으니까 starving에 대한 걱정은 말고 풀어보자. 저런 알고리즘을 적용하는 이유는 평균 대기시간을 줄이기 위해서다. 앞사람이 길수록 뒷사람이 오래기다리는 것과 같은 이치다. ??? 무슨상관이냐고..? 대기는 각각 한다. 즉, 기다리는 사람의 수만큼 한다. 일이 끝난 사람은 대기를 하지 않는다. 그렇다면...? 일을 빨리 끝내서 기다리는 사람을 줄여야 한다. 그것을 위한 알고리즘이 바로 Shortest job first algorithm 이다. 구현해보자 사실 구현할 것은.. 실제로 대기시간이 줄어들었느냐? 확인만하면 된다. 즉, 대기시간만 알아내면 끝이다...ㅎㅎ 당연히 입력으로는 작업시간이 주어져야 한다. #include..

병합 정렬이란 잘 알려진 정렬 알고리즘 중 하나다. 분할 정복이라는 간단한 아이디어이다. 많은 원소를 가지고 있더라도 작은 크기로 쪼개서 각각을 정렬한 다음 정렬된 부분집합을 정렬상태를 유지하면서 합치는 방식이다. 코드로 구현해보자 #include #include //벡터를 임의의 원소가 들어가도 괜찮게 템플릿 선언후 //벡터 2개의 참조변수를 이용한다. template std::vector merge(std::vector &arr1, std::vector& arr2) { std::vector merged; auto iter1 = arr1.begin(); auto iter2 = arr2.begin(); //차례대로 원소를 비교해나간다. -> 2개의 벡터를 받아서 가장 첫번째 원소부터 비교한다. //결국 ..