쾌락없는 책임 (공부)
-
백준 14567 - 선수과목, C++, 위상정렬쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 11. 20. 21:39
14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net #include #include #include using namespace std; int n, m, a, b; int enterance[1001]; int howmany[1001]; vector edge[1001]; void Topology(){ int cur_sem = 1; queue q; for(int i = 0; i < n; i++){ if(enterance[i] == 0){ q.push(make_pair(i, 1)); } } while (!q.empty()){ int cur = ..
-
백준 2251 - 줄 세우기, C++, 위상정렬쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 11. 18. 16:39
2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net #include #include #include #include using namespace std; int n, m; int from, to; int inCome[32001]; vector node[32001]; void TopologySort(){ queue q; // init queue for(int i = 1; i > m; for(int i = 0; i > from >> to; inC..
-
백준 6087 - C++, BFS쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 11. 15. 22:33
6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net #include #include #include using namespace std; int w, h; pair startP, endP; bool getStartPoint; char map[101][101]; int count[101][101]; int goX[4] = { 0, 0, 1, -1 }; int goY[4] = { 1, -1, 0, 0 }; // 0 = 위, 1 = 아래, 2 = 오른쪽, 3 = 왼쪽 void MirrorSearch(){ qu..
-
백준 6549 - 히스토그램에서 가장 큰 직사각형, C++, 스택쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 11. 13. 19:14
6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net #include #include #include using namespace std; long long n; long long hist[100010]; int main(){ ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); while(true){ cin >> n; if(n > hist[i]; hist[n] = -1; stack s; lo..
-
백준 1655 - 가운데를 말해요, C++, 우선순위 큐쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 11. 10. 20:44
1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net #include #include using namespace std; int n, input; // smallerQ.top() > n; for(int ..
-
백준 11049 - 행렬 곱셈 순서, C++, DP쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 11. 4. 00:04
11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net #include #include #include using namespace std; int n, r, c, res = 0; pair matrix[501]; int dp[501][501]; // left ~ right : 최소 연산 횟수 int MultiplyMatrix(int left, int right){ if(left == right) return 0; int minimum = 999999999; if(dp[left][right] != -1) r..
-
백준 2261 - 가장 가까운 두 점, C++, Closest Pair, 분할정복쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 10. 30. 15:26
2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net #include #include #include #include using namespace std; struct Point{ int x; int y; bool operator < (const Point &b) const{ if(x == b.x) return y < b.y; else return x < b.x; } }; int Distance(Point a, Point b){ return (a.x - b.x) * (a.x - b...