쾌락없는 책임 (공부)/알고리즘 문제풀이
-
백준 15483 - 최소 편집 거리, C++, DP쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 12. 31. 16:07
15483번: 최소 편집 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. www.acmicpc.net #include #include #include using namespace std; int change_cost[1001][1001]; int main(){ string from_string, to_string; cin >> from_string >> to_string; for(int i = 0; i
-
백준 1167 - 트리의 지름, C++, DFS쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 11. 23. 17:44
1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net #include #include #include using namespace std; int v, trees_diameter = 0, far_point; bool visit_this_node[100001]; vector edge[100001]; void SearchDiameter(int node, int diameter){ if(visit_this_node[node]) return; visit_this_node[node] = true; if(tr..
-
백준 2623 - 음악프로그램, C++, 위상정렬쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 11. 23. 17:21
2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net #include #include #include using namespace std; int n, m; // 가수 수, 보조 pd 수 int entrance[1001]; vector singer[1001]; int main(){ //init ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // input cin >> n >> m; for(int i = 0; i < m; i++){ int num..
-
백준 16398 - 행성 연결, C++, 최소 스패닝 트리쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 11. 21. 00:44
16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net #include #include #include using namespace std; int n; int parent[1001]; int cost[1001][1001]; vector edge; int FindParent(int x){ if(x == parent[x]) return x; return parent[x] = FindParent(parent[x]); } bool SameParent(int x, int y){ x = FindParent(x); y = Fin..
-
백준 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..