전체 글 (8) 썸네일형 리스트형 Tree[DFS] - 1967 C++ 문제 1967번 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다. 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세.. Graph [Adjacency List] - 4803 C++ 문제 4803번 트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다. 그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오. https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 개요 유니온 파인드라는 알고리즘을 이용하면 쉽게 답이 나온다는데... 필자는 이런 알고리즘의 존재를 문제 다 풀고 나서 알았다 .. Graph [concept] - DataStructure 그래프(Graph) 개념 그래프란, 노드들과 그 노드들을 연결한 간선을 나타낸 자료구조이다. 각각의 노드들은 정점(Vertex)이라고 표현한다. 그럼 트리와는 뭐가 다른가요? 그래프 트리 노드와 노드를 연결하는 간선들의 집합 Cycle이 없는 Connected Graph Cycle 존재 가능 Cycle 존재 불가능 두 정점 사이의 여러개의 경로 존재 가능 두 정점 사이 반드시 1개의 경로 존재 간선의 수는 그래프의 종류에 따라 다름 간선의 수 = 정점의 수 -1 그래프 ⊃ 트리 표현방식 그래프 자료구조의 표현 방식에는 두 가지가 있다. 1. 인접 행렬 2. 인접 리스트 • 인접행렬 (Adjency Matrix) 정의 : 그래프의 연결 관계를 이차원 배열로 나타낸 방식,, ex) adMa[i][j] -> .. Graph (DFS,BFS)(basic) - 1260 C++ 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 개요 문제를 보면 제일 먼저 그래프 문제인 척하는 트리문제라는 생각이 든다. 단지, 자식노드와.. Brute Force -10881 C++ 문제 프로도는 네오에게 줄 생일 선물을 세 개 샀다. 이 세 개의 선물은 직사각형 모양의 선물 상자에 각각 하나씩 담겨 있다. 프로도는 이 선물들을 적당한 크기의 직사각형 포장 상자에 넣어 포장하려 한다. 큰 포장 상자를 주문할수록 돈을 더 많이 써야 하기 때문에, 프로도는 최대한 작은 상자에 세 개의 선물을 모두 담으려고 한다. (중략) 구매한 선물 상자들의 크기가 주어졌을 때, 선물들을 안전하게 포장하는 데 필요한 포장 상자의 최소 크기 (즉, 포장 상자의 넓이가 최소가 되는 경우)를 구하시오 https://www.acmicpc.net/problem/10881 10881번: 프로도의 선물 포장 프로도는 네오에게 줄 생일 선물을 세 개 샀다. 이 세 개의 선물은 직사각형 모양의 선물 상자에 각각 하나씩.. Brute Force, Greedy - 2590 C++ 문제 백준 2590번 정사각형 모양을 한 여섯 종류의 색종이가 있다. 1번 색종이는 한 변의 길이가 1cm이고, 차례대로 그 길이가 1cm씩 커져, 6번 색종이의 한 변의 길이는 6cm가 된다. 주어진 색종이를 가로, 세로의 길이가 각각 6cm인 판 위에 붙이려고 한다. 색종이를 붙일 때는 색종이가 판의 경계 밖으로 삐져 나가서는 안되며, 색종이가 서로 겹쳐서도 안 된다. 또한 하나의 색종이는 하나의 판에만 붙여야 한다. https://www.acmicpc.net/problem/2590 2590번: 색종이 과 같이 정사각형 모양을 한 여섯 종류의 색종이가 있다. 1번 색종이는 한 변의 길이가 1cm이고, 차례대로 그 길이가 1cm씩 커져, 6번 색종이의 한 변의 길이는 6cm가 된다. 주어진 색 www... 2 Dimentional array - 2563 C++ 문제 백준 2563번 관련문제 (2669번) 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오. https://www.acmicpc.net/problem/2563 2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 개요 기본적으로 좌표가 나오고 좌표의 특정.. Merge Sort (build) - 2751 C++ 문제 백준 2751번 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 개요 기본적인 정렬 문제이나 범위가 상당하다. 만약 O(n2) 시간복잡도의 코드를 짜게된다면 반드시 시간 초과가 뜰 것이다. 이런 경우 복잡한 문제가 아니기 때문에 많은 사람들은 헤더의 sorted 함수를 이용할 것 이다. 허나 나는 기본제공되는 함수를 이용하는 것이 아니라 직접 코드를 짤 것이다. 먼저 , 어떤 정렬 알고리즘을 이용할지 정해야한다. 떠오르는 건 1.선택정렬 2.삽입정렬 3.버블정렬 4.병합정렬.. 이전 1 다음
