Algorithm/그래프, 트리8 트리의 순회 www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 문제 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력 첫째 줄에 프리오더를 출력한다. #include using namespace std;.. 2021. 3. 30. 트리의 지름 www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정.. 2021. 3. 11. 사이클 크기 구하기 (텀 프로젝트) www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS(Depth First Search) 알고리즘을 사용하여 사이클을 이루지 않는 사람의 수를 구하는 문제. 기존의 vist 배열과 함께, 해당원소 탐색이 완료되었다는 done 배열을 이용하여 사이클 크기를 구하는문제. #include using namespace std; int point[100001]; bool vist[100001]; bool done[100001]; int TC , N , sum ; void.. 2021. 3. 10. 이분 그래프 (Bipartite Graph) 이분 그래프 (Bipartite Graph) 이분그래프는 인접한 정점끼리 서로 다른 두가지 집합으로만 나눈 그래프를 뜻한다. 다시 말해, 그래프의 모든 정점이 두그룹으로 나뉘어져있고 같은 그룹끼리는 인접하지 않은 그래프이다. 이분그래프를 확인하는 방법은 BFS 나 DFS를 이용한다. 1. BFS , DFS 를 수행하며 각 정점을 방문할때 마다 인접한 그룹과 다른 색을 칠한다. 2. 각 정점을 방문 중, 자신과 인접한 정점의 색이 자신과 같다면 그 그래프는 이분 그래프가 아니다. (발견과 동시에 BFS 종료) 3. 모든 정점을 방문하고 인접한 정점끼리 같은색이 없다면 이분그래프이다. 특징) 모든 정점을 방문하기 때문에 시간 복잡도는 O (V+E) 이다. 아래의 코드는 백준사이트의 이분그래프를 풀면서 BFS.. 2021. 3. 6. 위상정렬 위상정렬은 정렬 알고리즘의 종류이다. 위상정렬이란 '방향그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열' 하는 것이다. 쉽게 비유를 하자면 '대학교 커리큘럼'을 예로들수있다. 예를들어 모 대학교의 컴공과는 인공지능과목을 자료구조를 선수강한 뒤에 신청할수있도록 하였다. 이처럼 그래프상에서 선후관계가있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 순서를 계산할수있다. 위상정렬의 알고리즘 순서는 다음과 같다. 1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐가 빌때 까지 다음의 과정을 반복한다. 1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 여기서 진입 차수란, 특정노드로 들어오는 간선의 개수와 같다. #.. 2021. 2. 26. 신장트리, 크루스칼 알고리즘 신장트리는 그래프에서 자주보이는 유형이다. 신장트리란, 하나의 그래프가있을때 모든 노드를 포함하면서 사이클을 발생 시키지 않는 부분그래프를 뜻한다. 이처럼 신장트리에서 최소 비용으로 만들어진 신장트리를 '최소비용 신장트리' 리고하는데 이 신장트리를 구하는 대표적인 방법은 크루스칼 알고리즘이 있다. 크루스칼 알고리즘의 동작순서는 다음과 같다. 1. 간선데이터의 비용을 크기에 따라 오름 차순 정렬한다. 2. 간선을 하나씩확인하며 사이클을 발생 시키는지 확인한다. 1. 사이클이 발생하지 않는다면 최소비용 신장트리에 포함시킨다. 2. 사이클이 발생하는 경우 포함하지 않는다. 3. 모든 간선에 대하여 2 번의 과정을 반복한다. 다음은 크루스칼 알고리즘의 코드이다. #include #include #include .. 2021. 2. 26. 이전 1 2 다음
