알고리즘/백준 & swacademy108 BOJ 1199 - 오일러 회로 https://www.acmicpc.net/problem/1199 양방향그래프 오일러서킷 코드기록용 오일러서킷 존재하면 출력, 없으면 -1출력 오일러트레일은 무시해야 함. ->차수가 홀수인 정점이 없으면 오일러서킷 존재함 int adj[MAX][MAX], n, deg[MAX]; bool odd; vector ans; void euler(int u) { for (int v = 0; v 0) { adj[u][v]--; adj[v][u]--; euler(v); } } ans.push_back(u); } int main() { FAST; cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++).. 2020. 2. 13. 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. 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 ··· 9 10 11 12 13 14 15 ··· 27 다음
