기록하지 않았다면 잃어버릴 시간들

새로운 것을 배우는게 즐거운 개발자입니다.

알고리즘/백준

https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 백준 온라인저지 2637번 문제입니다. 위상정렬을 이용해서 풀었습니다. #include #include #include #include #define MAX 101 using namespace std; int require_parts[MAX]; int degree[MAX]; vector v[MAX]; vector nomal_parts; int N,M; int X, Y, ..

2022. 1. 3.

알고리즘/백준

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 백준 온라인저지 1766번 문제입니다. 위상정렬을 이용해서 풀었습니다. #include #include #include #define MAX 32001 using namespace std; int num[MAX]; vector v[MAX]; bool visited[MAX]; int N, M; void Input() { int a, b; cin >> N >> M; fo..

2022. 1. 3.

알고리즘/백준

https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 백준 온라인저지 14567번 문제입니다. 위상정렬을 이용해서 풀었습니다. #include #include #include #define MAX 1001 using namespace std; int N, M; int PrerequisiteCnt[MAX]; int Prerequisite[MAX]; vector v[MAX]; int max(int a, int b) { return a > b ? a : b; } void Input..

2022. 1. 3.

알고리즘/백준

https://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 백준 온라인저지 2252번 문제입니다. 위상정렬을 이용해서 풀었습니다. #include #include #include using namespace std; int N, M; int num[32001]; vector v[32001]; void Input() { int a, b; cin >> N >> M; for (int i = 0; i < M; i++) ..

2022. 1. 3.

알고리즘/백준

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 백준 온라인저지 1516번 문제입니다. 위상정렬을 이용해서 풀었습니다. #include #include #include using namespace std; int n; int time[501]; int dp[501]; int buildingCnt[501]; vector building[501]; int max(int a, int b) { return a > b ? a : b; } vo..

2022. 1. 3.

알고리즘/이론

위상정렬 방향성을 가진 비순환 그래프에서만 사용이 가능 특정한 순서로 실행이 되어야하는 상황에 사용이 적합 위상정렬은 위에서 간단하게 설명한 것 처럼 특정한 순서로 실행이 되어야하는 상황에서 사용을 할때 사용을 하게 됩니다. 게임에서 예를 들어 보겠습니다. 요즘 유명한 게임이죠 리그오브 레전드라는 게임에서 피바라기 라는 아이템을 구매하기 위해 필요한 아이템 목록입니다. BF 대검 + 롱소드 + 흡혈의 낫을 그래프로 나타내면 다음과 같이 나타낼 수 있게 됩니다. B.F 대검과 롱소드 그리고 흡혈의 낫은 피바라기를 가르키고 있고 롱소드는 흡혈의 낫을 가리키고 있습니다. 그 이유는 각각의 아이템들은 피바라기의 선행조건이 되기 때문입니다. 그리고 피바라기를 구매후에는 다시 각각의 아이템으로 바꿀 수 없게 됩니다..

2022. 1. 3.

알고리즘/이론

BFS (Breath First Search) 그래프 탐색 알고리즘으로, 그래프탐색이란 한 정점에서 시작하여 탐색 조건에 맞는 노드를 찾을때까지 모든 노드를 방문하는 방법입니다. 너비 우선 탐색으로 모든 Branch의 같은 깊이의 노드들을 번갈아 가며 탐색을 하게 됩니다. FIFO구조인 큐로 구현 가능합니다. 장점 장점 단순검색 속도가 DFS에 비해 빠른편입니다. 깊이에 관계없이 최단 경로를 찾을 수 있습니다. 단점 다음에 탐색할 노드들을 모두 큐에 담아 두기 위해서는 자원이 많이 필요합니다. 과정 ※다음과 같은 그래프의 정점 1에서 모든 노드를 탐색 스택을 이용한 BFS를 하는 과정이고, 한번 방문한 노드는 방문처리가 되어 다시 방문 할 수 없다고 가정합니다. 아래쪽의 큐의 변화와 함께 보시면 이해가 ..

2021. 12. 30.