본문 바로가기
반응형

분류 전체보기1308

[BOJ] 백준 3665 최종 순위 출처: https://www.acmicpc.net/problem/3665 Input 3 5 5 4 3 2 1 2 2 4 3 4 3 2 3 1 0 4 1 2 3 4 3 1 2 3 4 2 3 Output 5 3 2 4 1 2 3 1 IMPOSSIBLE 위상정렬 (Topological sort) 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는 zoosso.tistory.com 변동된 정보를 이용하여 새로운 순위를 출력하는 문제입니다. ※ 작년 순위가 오류없이 명확하게 주어지기 때문에 (기.. 2021. 2. 24.
[SWEA] 3456 직사각형 길이 찾기 출처: SWEA Input 3 1 1 2 4 3 4 5 5 5 Output #1 2 #2 3 #3 5 직사각형 한 변을 기준으로 자기자신을 제외하고 동일한 값이 있는지 확인 모든 변이 일치하는 경우가 있으므로 answer 초기값을 임의의 한 변과 동일하게 처리 #include using namespace std; int side[3], answer; int main() { int testCase; cin >> testCase; for (int tc = 1; tc > side[i]; } bool isUnique; answer = side[0]; for (int pivot = 0; pivot < 3; pivot++) { isUnique = true; for (int target = 0; target < 3;.. 2021. 2. 24.
[SWEA] 3431 준환이의 운동관리 출처: SWEA Input 3 300 400 240 300 400 350 300 400 480 Output #1 60 #2 0 #3 -1 #include using namespace std; int X, L, U, answer; int main() { int testCase; cin >> testCase; for (int tc = 1; tc > L >> U >> X; if (X U) answer = -1; else answer = 0; cout 2021. 2. 24.
[SWEA] 1540 좋은 문자열 출처: SWEA Input 7 ZGBG X EE AAB AABA AABB BCBABCC Output GOOD GOOD GOOD GOOD GOOD BAD BAD ① 각 문자열로 D-쌍 구합니다. 쌍은 두 문자로 구성되어 있으므로 left, right 변수 이용 ② D-쌍에서 D-유일 여부를 판단합니다. 쌍과 마찬가지로 유일성 여부를 판단하기 위해서는 left와 right 변수 활용 #include using namespace std; string str; bool isUnique(int left, int right, int distance) { // 서로 같은 문자열이 있는지 확인 int l = 0, r; while (true) { r = l + distance; // D_pair[]의 모든 원소를 찾은 .. 2021. 2. 24.
[SWEA] 3499 퍼펙트 셔플 출처: SWEA Input 3 6 A B C D E F 4 JACK QUEEN KING ACE 5 ALAKIR ALEXSTRASZA DR-BOOM LORD-JARAXXUS AVIANA Output #1 A D B E C F #2 JACK KING QUEEN ACE #3 ALAKIR LORD-JARAXXUS ALEXSTRASZA AVIANA DR-BOOM 교대로 섞이는 규칙을 활용해서 수식을 세웁니다. #include using namespace std; char card[1001][81]; int main() { int testCase; cin >> testCase; for (int tc = 1; tc > N; for (int i = 0; i > card[i]; // 정답 출력.. 2021. 2. 24.
[SWEA] 3750 Digit sum 출처: SWEA Input 3 5 108 588432 Output #1 5 #2 9 #3 3 #include using namespace std; unsigned long int f(unsigned long int n) { // 10 미만인 경우 if (n 9) { sum += n % 10; n = n / 10; } // 각 자릿수의 합 재귀처리 return f(sum + n); } int main() { int testCase; cin >> testCase; for (int tc = 1; tc 2021. 2. 24.
[SWEA] 9092 마라톤 출처: SWEA Input 2 5 2 0 0 8 3 1 1 10 -5 2 2 5 3 0 0 8 3 1 1 10 -5 2 2 Output #1 4 #2 4 ▶ dp[cur][k] = min(dp[cur][k], solve(next, k - i) + distance(cur, next)); dp[현재위치][남은 점프 수] → 가능한 건너뛰기를 고려해서 갈수 있는 칸으로 뛰어본다. #include #include #include #define MAX 123456789 using namespace std; int dp[501][501]; vector v; int N, K, x, y; int abs(int x) { return x >= 0 ? x : -x; } int min(int x, int y) { return.. 2021. 2. 24.
[SWEA] 5684 운동 출처: SWEA Input 1 3 4 1 2 1 3 2 1 1 3 5 2 3 2 Output #1 3 N이 크지 않아 DFS 혹은 BFS로도 풀이 가능 다익스트라 알고리즘 이용 #include #include #include #include #define SIZE 401 #define INF 987654321 using namespace std; struct Pair { int v, w; Pair(int v, int w) : v(v), w(w) {} }; struct minHeap { bool operator()(Pair p1, Pair p2) { return p1.w > p2.w; } }; int n, m, answer; int dist[SIZE]; vector graph[SIZE]; int dijks.. 2021. 2. 24.
[BOJ] 백준 2056 작업 출처: www.acmicpc.net/problem/2056 Input 7 5 0 1 1 1 3 1 2 6 1 1 1 2 2 4 8 2 2 4 4 3 3 5 6 Output 23 위상정렬 (Topological sort 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는 zoosso.tistory.com 작업(정점)의 개수 N과 각 작업별 선행관계가 주어질 때, 모든 작업이 완료하기 까지 필요한 최소 시간 출력. 1번의 경우에는 항상 선행 작업이 존재하지 않습니다. ※ 해당 문제는 사이클.. 2021. 2. 24.
위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는데 많이 사용 ※의존성 그래프(dependency graph) 작업(정점)간의 의존 관계를 간선으로 표현한 방향 그래프 DAG에서 간선의 방향이 모두 한 방향으로 흘러가게 정점들을 정렬됩니다. 간선의 방향이 모두 한 방향으로 흐르며, 방향성을 거스르는 간선이 없게 정렬을 하기 위해서는 사이클이 없어야 합니다. * 작업의 순서(의존관계)만 위반하지 않으면 되므로 여러 순서(결과)가 나옵니다. (i) → (f) → (b) → (e) → (d) → (c) → (a) → (h) → (g.. 2021. 2. 24.
반응형

티스토리툴바