Algorithm/BOJ47 [boj] 2056 - 작업 C++ 풀이(DAG, BFS) www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 작업의 선행관계가 주어졌을 때, 모두 마치는 가장 빠른 시간을 구하는 문제이다. 전형적인 DAG문제이고, 위상정렬 로직을 bfs로 구현해서 모든 노드를 순서대로 순회했을 때의 최종 시간을 구하면 된다. #include #include #include #include using namespace std; int n; vector graph[10001]; vector ind(10001); // indegr.. 2021. 3. 28. [boj] 2252 - 줄 세우기 C++(DAG, topological sort) www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 간단하게 위상정렬에 대해서 배울 수 있는 문제이다. 사이클이 없는 유향그래프인 DAG를 통해서 선행관계를 구현할 수 있는 알고리즘이 위상정렬이다. 위상정렬은 출력 방법에 따라서 여러 개의 답이 나올 수 있고, DFS, BFS 방식으로 구현할 수 있는데 BFS가 좀 더 간단해보인다. 밑의 방식은 BFS방식이며, indegree가 0인 노드를 큐에 넣으면서 노드를 소거하는 식으로 다.. 2021. 3. 26. [boj] 1941 - 소문난 칠공주 C++ 풀이(완전탐색, 비트마스크, BFS) www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net - 순열 개념과 bfs개념만 알면 쉽게 풀 수 있는 문제이다. 다만 제한조건들을 잘 구현해야된다. 변수 스코프를 잘 잡으면 카운트하기 쉽다. - 이 문제에서 순열에 의해 픽된 칠공주 자리가 붙어있는지 여부를 체크할 때 DFS로 풀게 되면, 십자모양으로 붙어 있는 경우 왔던 자리를 되돌아오도록 짜던가 해야되서 많이 헤매게 된다. bfs로 붙어있는지 여부를 체크하는 것이 합당하다. #include #include #i.. 2021. 3. 25. [boj]20366 - 같이 눈사람 만들래? 풀이(투포인터, 정렬) www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net - 문제 유형 분류가 투포인터로 되어 있는데 눈사람을 만드는 모든 케이스를 만든 뒤 정렬하면서 중복되는지 여부만 체크해도 충분히 풀리는 문제였다. 투포인터로 된 스터디원 풀이도 봤는데 잘 이해가 가지 않았다. - sort에 쓸 compare 함수를 짤 때 등호가 들어간 부등호를 쓰면 채점 시에 시간초과가 난다. 주의하자 - 구조체 생성자를 따로 작성 안해도 눈사람 배열에 {원소1,.. 2021. 3. 25. 이전 1 ··· 7 8 9 10 11 12 다음
