728x90

Coding Test/BaekJoon_C++ 28

백준 1717 <집합의 표현> C++

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net union-find 알고리즘의 기초 문제입니다. #include // #include #include // #include using namespace std; // 각 노드의 루트를 저장 vector root_vec; // find int find_func(int node) { // 자신의 루트가 자신이 아니면 if (root_vec[node] != node..

백준 11657 <타임머신> C++

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 백준 11657 Python https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B dev-diary-0717..

백준 9935 <문자열 폭발> C++

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 백준 9936 Python https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크 dev-diary-0717.tistory.com 전에 작성한 파이썬 코드를 C++ 코드로 변환했습니다. #in..

백준 2592 <대표값> C++

https://www.acmicpc.net/problem/2592 2592번: 대표값 어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 예를 들어 10, 40, 30, 60, 30, 20, 60, 30, 40, 50의 평균은 www.acmicpc.net 파이썬의 딕셔너리, C++ 에서의 map 을 이용하면 풀 수 있습니다. #include #include using namespace std; int main(void) { // 합 기록 int sum{}; // 파이썬의 딕셔너리와 비슷 map count_map; for (int i = 0; i > num; // 합 sum += num; // 딕셔너리에 기록, 이미..

백준 1967 <트리의 지름> C++

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net https://dev-diary-0717.tistory.com/114 백준 1967 Python https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 dev-diary-0717.t..

백준 1504 <특정한 최단 경로> C++

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라를 여러 번 사용해 풀 수 있습니다. #include #include #include #include #include using namespace std; /* 다익스트라를 세번 사용 */ // 다익스트라 int dijkstra(array tree, int N, int start, int end) { // 시스템상 최대 거리 int max_di..

백준 1753 <최단경로> C++

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 다익스트라 알고리즘을 사용해 풀 수 있습니다. #include #include #include #include #include using namespace std; /* 다익스트라 함수를 사용 */ array dijkstra(array tree, int K, int V) { // 시스템상 최대 수 한계 const int max_num = 3000001; // ..

백준 28278 <스택 2> C++

https://www.acmicpc.net/problem/28278 28278번: 스택 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net 일반 코드로 실행하면 시간초과가 걸립니다. endl 대신 "\n" 을 사용하고 ios_base::sync_with_stdio(false); cin.tie(NULL); 코드를 추가해줘야 합니다. #include #include #include #include #include using namespace std; vector split(string str, char Delimiter) { istringstream iss(str..

728x90