분류 전체보기
-
[백준 15681] 트리와 쿼리C 프로그래밍/BOJ 2022. 9. 22. 00:24
https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net #include #include int N, R, Q; int query[100000 + 2]; int visited[100000 + 2]; using namespace std; list Tree[100000 + 2]; void input() { scanf("%d %d %d", &N, &R, &Q); for (int i = 0; i <..
-
[백준 5639] 이진 검색 트리C 프로그래밍/BOJ 2022. 9. 21. 21:37
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net #include #include #include int root = -1; struct _st { int l; int r; }; using namespace std; unordered_map Tree; vector V; void input() { int n = 0; while (scanf("%d", &n) != EOF) {// 파일이 끝날 때 까지 받는다. // c++의 경우 cin ..
-
[자료구조] TREEC 프로그래밍/BOJ 2022. 9. 21. 19:59
아.. 트리 어렵다 어려워 오늘은 어려워도 내일은 안어려웠으면 좋겠다는 마음을 담아 정리해본닷... 킁 [백준 11725] 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net #include #include int N; std::list Tree[100000 + 2]; int ans[100000 + 2]; bool visited[100000 + 2]; void input(void) { scanf("%d", &N); for (int i = 0; i < N - 1; i++) { int u = 0;..
-
[C++ STL] LISTC 프로그래밍/BOJ 2022. 9. 20. 22:45
아 .. 원래 나만보려고 했는데... ㅋㅋㅋㅋㅋㅋ^-^ 이론 시간에 딴짓하다가 어떤 애도 같이 본다고 해서 뒤늦게 집중한거 안비밀... 건방지다 나자신 암튼 내용 매우 러프함 주의 "Sequence List" 장점은 다음과 같다. - random access(데이터를 비 연속적으로 접근하는 것)가 용이하다. - 자료구조를 빠른 속도로 정렬할 수 있다. - 정렬이 가능하다면 binary search를 사용할 수 있고, 시간복잡도 O(NlogN)으로 데이터 탐색이 가능하다. - 연산 시간은 O(1) 이다. "List" - doubly linked list 이다(양방향으로 데이터를 접근하는 것이 가능). - 데이터를 빈번하게 추가, 삽입하거나 삭제하는 경우 유용하다. - 한편 이러한 동작을 벡터에서 하게 되면..
-
[백준 14867] 물통C 프로그래밍/BOJ 2022. 9. 20. 21:59
https://www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최 www.acmicpc.net #include #include #include int a, b, c, d; using namespace std; struct _st { int x; int y; int cnt; }; queue Q;// 상태 저장용 큐 set S;// set으로 방문 체크를 대신한다 void Fill_A(int x, int y, int cnt) { // Fill A ..
-
[백준 14502] 연구소C 프로그래밍/BOJ 2022. 9. 20. 19:45
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net #include #include #include int N, M; int map_virus[8 + 2][8 + 2]; int visited[8 + 2][8 + 2]; int choice[3 + 2]; struct _st { int x; int y; }; std::queue Virus; std::vector Blank; int dir_x[4] = { 0, 0, 1, -1 }; int dir_y[4] = { 1,..
-
[백준 10043] 택시C 프로그래밍/BOJ 2022. 9. 19. 23:49
https://www.acmicpc.net/problem/10043 10043번: タクシー (Taxis) IOI 国は町 1 から町 N までの N 個の町からなり，町と町とは道路で結ばれている．IOI 国には K 本の道路があり，すべての道路は異なる 2 つの町を結んでいる．車は道路を双方向に自由に移動 www.acmicpc.net // BFS로 해결 #include #include #include #include int N, K; int chk[5000 + 2][5000 + 2];// 상태발전을 위한 체크배열 struct _st { int n; int cnt; int cost; }; struct _tx { int cost; int cnt; }taxi[5000 + 2]; using namespace std; list adj..
-
[C++ STL] MAPC 프로그래밍/BOJ 2022. 9. 19. 20:41
이 또한 내가 보려고 정리... 매우 러프함 주의... "map" - 매핑된 정보를 관리하는 컨테이너 - key와 data를 매핑한다. - key를 기반으로 탐색한다. - 데이터를 저장하는데 걸리는시간 O(logN), 데이터를 탐색하는데 걸리는 시간 O(logN) - set 과 마찬가지로 순서가 중요할 때는 map, 순서가 중요하지 않고 빠른 성능이 중요할 때는 unordered_map #include #include #include // map header 추가 필요 #include // unordered_map 또한 header 추가 필요 using namespace std; struct _st { int x; int y; }; // map은 key와 data가 pair로 묶여 저장된다. unorde..