https://www.acmicpc.net/problem/17825 잘안돼서 다시 풀어바야겠따 ㅠㅠ #include #include #include using namespace std; int dice[10]; int map[42]; int turn[42]; int score[42]; int which[4]; int check[42]; int ans; void dfs(int cnt, int sum){ if (cnt==10){ ans = max(ans, sum); return; } for (int i=0;idice[i]; } for (int i=0;i

위상 정렬은 2022년도 1학기 서울대학교 석사 시험에 나왔던 문제이다. 노드 i와 j 사이에 간선 (i, j)가 존재한다면 노드 i는 노드j보다 먼저 수행되어야한다. 모든 간선에 대해서 이 성질만 만족시킨다면 노드 간의 어떤 순서라도 좋다. 이런 성질을 만족하는 정렬을 위상 정렬, topological sort이라고 한다. 간선 (i, j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 위치해야한다 만약 그래프에 사이클이 있다면 이 성질은 결코 만족될 수 없으므로 위상 정렬은 할 수 없다. 동작 방식은 아래와 같다. 알고리즘 1. topologicalSort(G, v){ for i

1. dfs와 bfs의 시간 복잡도 dfs와 bfs 모두 인접리스트, 인접 행렬로 구현할 수 있다. N이 그래프의 노드의 수, E가 그래프의 간선의 수라고 하자. dfs와 bfs 모두 인접리스트로 그래프를 구현했을 때 O(N+E)의 시간 복잡도를 가지며 인접행렬로 구현했을 때 O(N^2)의 시간 복잡도를 갖는다. 2. bfs 소스코드 C++ BFS(G, s){ for each v ( s visited[v] = NO; } visited[s] = YES; enqueue(Q, s) while (Q!=0){ u

평균 선형 시간 선택 알고리즘 n개의 원소로된 집합에서 최소 원소를 찾기 위해서는 O(n)의 사긴이 필요로한다. 그런데 n개의 원소 중 i번째 작은 원소를 찾기 위해서는 O(n^2) 의 시간이 든다. 정렬을 사용하면 O(nlogn)의 시간으로 단축할 수 있으므로 시간은 O(n)과 O(nlogn) 사이의 시간이 들 것이다. 알고리즘을 사용하면 O(n)의 시간에 확인할 수 있다고 한다. 퀵정렬 알고리즘을 개선하면 평균적으로 선형시간에 i번째 작은 원소를 찾을 수 있게 한다. 알고리즘을 살펴보자. 소스코드 select(A, p, r, i) { if (p=r) then return A[p]; q

앞서 설명한 정렬 알고리즘들의 공통점은 원소끼리 비교하는 것으로만 정렬을 한다는 것이다. 이런 정렬을 '비교정렬'이라고 한다. 이러한 비교정렬은 최악의 경우 수행 시간이 절대 O(nlogn)을 밑돌 수 없다. 정렬하고자 하는 원소들이 특수한 성질을 만족하면 이 하한보다 더 빠른 정렬 알고리즘을 적용할 수 있다. 기수정렬 기수 정렬은 입력이 모두 k자릿수 이하의 자연수인 특수한 경우에 사용할 수 있는 방법으로 O(n)시간이 소요되는 정렬 알고리즘이다. 기수정렬은 우선 가장 낮은 자릿수만 가지고 모든 수를 정렬한다. 그런 다음 가장 낮은 자릿수는 잊어버린다. 그리고 앞과 같은 방법으로 더 이상 자릿수가 남지 않을 때까지 반복한다. 이렇게 하면 마지막에는 정렬된 배열을 갖게된다. 계수정렬 계수 정렬은 정렬하고..

퀵 정렬 수도코드 quickSort(A[], p, r){ if (p