Algorithm/BOJ(백준)
-
백준 10845 큐Algorithm/BOJ(백준) 2019. 9. 8. 14:02
문제 링크 : **https://www.acmicpc.net/problem/10845** ※ 선행해야 할 알고리즘 : 큐 //kuklife.tistory.com #include #include #include using namespace std; int check(queue q) { if (q.empty()) return -1; else return 0; } int main() { int n; queue q; cin >> n; for (int i = 0; i > str; if (str == "push") { int in; cin >> in; q.push(in); } else if (str == "front") { if (check(q) == -1) cout
-
백준 2583 영역 구하기Algorithm/BOJ(백준) 2018. 10. 8. 21:47
문제 링크 : https://www.acmicpc.net/problem/2583※선행해야 할 알고리즘 : BFS/DFS Algorithm 요약 : M*N 직사각형에서 영역을 만든 직사각형 외의 영역 크기를 출력하시오. 1. 입력 예제를 통해 예를 본다면, 5 7 30 2 4 41 1 2 54 0 6 2 직사각형 공간 내에서 1) [2][0]부터 [3][3]까지2) [1][1]부터 [4][1]까지3) [0][4]부터 [1][5]까지 총 세 가지의 또다른 직사각형 영역을 띄게 된다. (여기서 후자의 영역을 -1을 한 이유는 칸을 기준으로 좌표가 작성된 것이 아니고, 도형의 선을 기준으로 좌표가 작성되어 후자의 영역은 -1하여 계산하였다.) 즉, 이 영역들은 0으로 초기화 된 M*N 직사각형에서 위의 좌표값만..
-
백준 1976 여행 가자Algorithm/BOJ(백준) 2018. 10. 4. 22:46
문제 링크 : https://www.acmicpc.net/problem/1976※선행해야 할 알고리즘 : Disjoint-set(Union-Find), BFS/DFS Algorithm : 그래프를 입력 후, 마지막에 입력한 여행 코스를 갈 수 있는지 없는지 확인하여 출력하는 것 방법은 두가지가 있다. 그래프 전체를 입력받아 우선탐색을 실시하는 방법과 그래프를 입력받았을 때 연결된 부분을 union한 후 find해나가는 방식(즉, BFS/DFS or Union-Find로 풀면된다.) 먼저 Union-Find이다.(DFS방식은 풀이를 따로 작성하지 않았으며 소스로 풀이를 참고바랍니다.) 1. 그래프를 입력받을 때, 연결된 부분에 대해서는 바로 Union을 해준다.2. 그래프 입력이 다 되면 m개의 여행 계획..
-
백준 4195 친구 네트워크Algorithm/BOJ(백준) 2018. 10. 4. 20:19
문제 링크 : https://www.acmicpc.net/problem/4195※선행해야 할 알고리즘 : Disjoint-set(Union-Find) Algorithm : 친구의 이름이 둘씩 입력될 때, 두사람의 친구가 몇 명씩 연결되어 있는지 출력1. 두 번째 입력 예시를 통해 예를 들어본다면 3Fred BarneyBetty WilmaBarney Betty 처음에 Fred Barney가 입력되면 하단과 같이 트리가 연결되고 두 사람의 네트워크는 2가 된다. 두 번째로 Betty Wilma가 입력되면 하단과 같은 새로운 트리가 생겨 두 사람의 네트워크는 2된다. 마지막으로 Barney Betty이 입력이 되는데 Barney Betty는 기존에 입력되어 있던 사람들이기에 트리가 생성되지 않고 Barney ..
-
백준 1717 집합의 표현Algorithm/BOJ(백준) 2018. 10. 3. 20:10
문제 링크 : https://www.acmicpc.net/problem/1717※선행해야 할 알고리즘 : Disjoint-set(Union-Find) * 다음 문제는 Disjoin-set 문제의 기초 문제입니다. 이해 후 하단의 문제들을 풀어보시기 바랍니다. - 4195 친구 네트워크 - 1976 여행가자 - 10775 공항 - 9938 방청소 - 3780 네트워크 연결 - 3430 용이산다 - 2843 마블* Cpp 사용자 분들은 Cin 사용 시, 시간초과가 날 수 있습니다. - 초과나는 원인 및 테스팅은 하단 그림과 같습니다. - 또한 cin의 endl은 강제로 fflush를 하여 시간을 더 잡아먹습니다. - 결론 : 백준에서는 cin보다 scanf를 사용하세요! 유니온 파인드(Union-Find)①..