728x90 전체 글240 [C++] 백준 20040번: 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 중요풀이 union-find 알고리즘을 활용하여 풀이를 진행한 대표적인 문제입니다. union-find 알고리즘을 적용한다면 무난하게 풀어지는 문제입니다. 소스코드 #include using namespace std; int parent[500001]; int find(int index) { if (parent[index] == index)return index; return parent[i.. 2021. 8. 23. [C++] 백준 17472번: 다리 만들기 2(좋은 문제) https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 중요풀이 이 문제는 삼성 코딩테스트에 출제되었던 기출문제입니다. 중요 알고리즘이 2개나 사용되는 아주 좋은 문제인 것 같습니다. 사용되는 알고리즘은 크루스칼 알고리즘(최소 스패닝 트리)와 BFS(너비 우선 탐색)이 있습니다. #include #include #include #include using namespace std; //좋은 문제 : 여러가지 알고리즘 혼합 int l.. 2021. 8. 23. [C++] 백준 13549번: 숨바꼭질 3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 중요풀이 그래프 탐색을 기반으로 너비 우선 탐색 기법을 활용하여 풀이를 진행하였습니다. #include #include using namespace std; bool check[150001]; int time[150001]; void bfs(int start,int end) { queueq; q.push(start); check[start] = true; whil.. 2021. 8. 23. [C++] 백준 11779번: 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 중요풀이 가장 유명한 알고리즘 중 하나인 다익스트라 알고리즘을 기반으로 풀이되는 문제입니다. 큐를 활용하여 풀이를 진행해 주어야 합니다. #include #include #include using namespace std; vector city[1001]; vectorv[1001]; int INF = 100000001;// 전체길이가 1억까지는 가능하기 때문에 그것.. 2021. 8. 23. [C++] 다익스트라(Dijkstra) 알고리즘 개념 다익스트라 알고리즘이란? 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘입니다. 대표적으로 인공위성 GPS 소프트웨어 등에서 많이 사용됩니다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다.(음의 간선은 포함 불가) 기본적으로 다익스트라 알고리즘은 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있습니다. 예시코드 void Dijkstra(int s, int e) { priority_queuepq; // {index, distance} for (int i = 1; i 2021. 8. 23. [C++] 크루스칼 알고리즘(Kruskal Algorithm, 최소 스패닝 트리-MST) 개념 크루스칼 알고리즘이란? 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 이는 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이라고 할 수 있습니다. 대표적으로 여러 개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하고자 할 때 실제로 적용되는 알고리즘입니다.(크루스칼 알고리즘을 구현할 때 기본적으로 유니온 파인드 개념을 사용합니다.) 예시코드 class edge { public: int node[2]; int distance; edge(int a, int b, int c) { this->node[0] = a; this->node[1] = b; this->distance = c; } bool operator distance .. 2021. 8. 23. [C++] Union-Find 알고리즘 개념 Union-Find 알고리즘이란? 대표적인 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가진 알고리즘입니다. 서로소 집합(Disjoint-Set) 알고리즘이라고도 부릅니다. 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 선택된 두 노드가 서로 같은 그래프 상에 속해 있는지 판별하는 알고리즘입니다. 구현된 함수로는 조상 노드를 찾는 getParent(재귀함수로 구현)함수와 합집합해주는 unionParent함수 그리고 두 노드가 같은 그래프에 있는지 확인해주는 findParent함수가 있습니다. //보통 union find 알고리즘을 사용할 때 갱신을 작은 수쪽으로 수정해줍니다. //parent 찾기 int getParent(int parent[], int x) { if (parent[x] == .. 2021. 8. 23. [C++] DFS(Depth First Search), BFS(Breath First Search) 개념 깊이 우선 탐색(Depth First Search) 루트 노드를 시작으로 다음 분기로 넘어가기 전에 해당 분기를 끝까지 탐색하는 탐색 방법 예시코드 void dfs(int x){ if(check[x]) return;//방문한 곳인지 체크 check[x] = true; for(int i = 0; i < a[x].size(); i++){ int nx = a[x][i]; dfs(nx); } } 장점 - 단지 현 경로상의 노드들만 기억하면 되기 때문에 저장 공간의 수요가 적습니다다. - 목표노드가 깊은 단계에 있는 경우에 빠르게 구할 수 있습니다. 단점 - 해가 없는 경로에 깊이 빠질 가능성이 있습니다. - 얻어진 해가 최단 경로를 통해 얻어진다는 보장이 없습니다. (위의 이미지에서 구해야 하는 해는 2번인.. 2021. 8. 23. [C++] 백준 8980번: 택배 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 중요풀이 그리디 알고리즘과 배열을 통해 각각의 인덱스를 마을을 의미하는 것으로 몇개의 박스가 배달되고 있는지를 체크합니다. 첫 번째 잘못된 정렬로 구현한 풀이입니다...틀렸습니다...ㅠㅠ #include #include #include #include using namespace std; struct info { int start; int end; int num; }; bool.. 2021. 8. 23. 이전 1 ··· 11 12 13 14 15 16 17 ··· 27 다음 728x90
