알고리즘225 BOJ 1967 - 트리의 지름 https://www.acmicpc.net/problem/1967 제목이 곧 내용인 문제 트리의 지름을 구하라 https://suuntree.tistory.com/171아이디어에 대한 추가설명 임의의 점에서 제일 먼 점 u와 u에서 제일 먼 점 v사이의 길이를 구하면 된다. 어떤 점에서 제일 긴 곳까지의 길이는 어떻게 구할까? 가중치가 없는 트리에선 dfs의 깊이가 곧 길이가 된다. 이 문제는 가중치가 있는 그래프이므로 1대신 w 더해주면 된다. 모든 정점에서 이 길이의 최대를 찾으면 된다. dfs 깊이를 효과적으로 유지하려면 함수에 깊이를 의미하는 파라미터를 추가해주면 된다. dfs(u, prv, d)꼴로 한 번의 dfs로 가장 먼 점과 그때의 거리를 구할 수 있다. int n, dst, st; vec.. 2020. 2. 8. 트리 struct treeNode { int element; treeNode * parent; vector children; } * 이진 트리: 자식을 최대 두 개 갖는 트리 * 이진 탐색 트리: 이진트리. 어떤 노드에서 left엔 자기보다 작은 값, right엔 자기보다 큰 값을 유지하는 식 * 힙: 포화 이진트리. 노드가 들어갈 수 있는 자리가 비어있는 경우가 없으므로 일반적으로 배열로 구현. * 구간트리: * 상호 배타적 집합 구조(disjoint set) : 각 노드는 부모를 가리키는 포인터는 있지만 자식에 대한 정보는 없다. 2020. 2. 8. BOJ 11994 - Circular Barn Revisited (dp) https://www.acmicpc.net/problem/11994 dp식은 대충짜지 말자고 다짐한 문제 최대 100개의 칸으로 나뉜 원형 헛간이 있다. 각 칸마다 외부로 통하는 문이 있고 양 옆 칸으로 이동하는 문이 있다. 외부에서 내부로 통하는 문을 지나는데는 비용이 들지 않는다. 옆 칸으로 이동할 때 반드시 시계방향으로 움직여야 하고 지나간 문의 수의 제곱만큼의 비용이 든다. 현재는 소들이 모두 외부에 있고, 최대 k개의 외부 문을 열어서 각 칸에 소가 정확히 ri마리씩 들어가도록 하고 싶다. 이 때 최소 비용을 구해라. ... (구간합 때문에 1base로 구현함) 당연히 시계방향 기준으로 뒤에 있는 소가 앞에 있는 소를 추월하는 것은 최적이 아니다. 0번 문을 처음으로 열어 줄 때~ n-1번 문을.. 2020. 2. 7. BOJ 12003 - Diamond Collector (전처리) https://www.acmicpc.net/problem/12003 유사코엔 전처리문제가 많이나온다 보석의 크기가 최대 5e4개 주어진다. 이 보석들을 두 개의 케이스에 나눠 담고 싶은데, 같은 케이스에 있는 보석의 크기 차이가 최대 K가 되도록 나누고 싶다. 최대한 보석을 전시한다면 몇개를 전시할 수 있을까? p[i] : 보석들중 크기가 a[i]~a[i]+k인 것들의 개수 pmx[i] = i~n-1번 보석 중 p[i]값의 최대 i번 보석을을 1번 케이스에 넣을 때 최대 전시 보석 수 = p[i] + pmx[i+p[i]] #include #include #define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); u.. 2020. 2. 7. 이전 1 ··· 18 19 20 21 22 23 24 ··· 57 다음
