코딩성장스토리

https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 이 문제는 set을 이용해서 넣었다 뺏다 하면서 푸는 문제이다 다른 문제에 비해 비교적 쉬운 문제라 구현하는데 에 문제는 없었다. 근데 여기서 set과 반복자 역박향 반복자를 처음 알게 되었다. set에 begin 함수와 end함수는 그냥 반복자 iterate로 할 수 있지만 rebegin 와 rend 같이 역으로 가는 함수는 역방향 반복자 reverse_i..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름은 가중치가 들어간 그래프(트리)를 탐색해서 가장 큰 값을 구하는 거다. 그러기 위해선 가장 위에 있는 루트 값을 알아내야 한다. 그리고 그 루트에서 가장 큰 값을 구하면 그게 가장 큰 값이 된다. 즉 루트를 알아내기위한 탐색 1번과 루트를 기준으로 가장 큰 값을 구하는 탐색 2번이면 구해진다. #include #include #include #include #inclu..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 이번에는 노드의 부모노드 번호를 구하는 문제이다. 나는 이 문제를 DFS로 풀었고 탐색을 진행하면서 각 노드에 해당하는 부모를 부모노드 배열에 넣었다. 그래서 한번의 탐색으로 각 노드의 부모를 저장한 배열을 구할 수 있다. #include #include #include #include using namespace std; #pragma warning(disable : 4996) vector d[100020]; //각 인덱스 별로 연결된 노드 배열 bool c..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이 문제는 트리 순회를 정석 문제이다. 전위순회, 중위순회,후위순회 를 구하는 문제이고 나는 배열 A[i][0]을 i의 왼쪽노드 A[i][1]을 i의 오른쪽 노드로 정하고 시작하였다. #include #include #include using namespace std; #pragma warning(disable : 4996) char a[26][2]; void preorder(char ..