본문 바로가기

백준154

백준 2637 c++ "장난감 조립" -[PlusUltraCode] https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net [필자 사고] 이 문제는 위상정렬 알고리즘을 사용하여 풀 수있는 문제이다. 이 문제의 특이한 점은 dist 카운트를 2번 사용하여 기본 부품의 갯수와 위상정렬에 사용해야 하는 dist총 2번을 저장해야 된다. 또한 위상정렬의 대표 문제들은 dist==0일때 마다 특별한 이벤트가 발생했지만 이번 문제는 dist==0이 아닐 때에도 pathLoad에 값을 갱신해줘야 한다. .. 2024. 3. 2.
백준 14567 c++ "선수과목(Prerequisite)" -[PlusUltraCode] https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net [필자 사고] 이 문제는 위상정렬 알고리즘을 사용하여 해결할 수 있는 문제이다. 또한 이 문제만의 특이한 점은 필자가 사용한 Level변수를 사용하여 위상정렬에 맞게 레벨처리를 완료해야 되는 문제다. [소스 코드] #include #include #include using namespace std; int N, M; vector Arr; vector dist; vector Record; void Input() { cin >.. 2024. 2. 29.
백준 2623 c++ "음악프로그램" -[PlusUltraCode] https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net [필자 사고] 위상정렬 알고리즘을 알고 있으면 쉽게 풀 수 있는 문제이다. 다만 이 문제의 특이한 점은 위상정렬 입력값들이 잘못 됬을때 과연 이 잘못된 과정을 어떻게 찾냐가 관건이다. 필자는 하나하나 연필로 3,2 인 경우를 풀어보니 dist[]의 모든 값이 0이 되지않고 도중에 탐색을 멈추게 된다는 것을 알았다. 이러한 과정만 잘 알고 있으면 쉽게 해결할 수 있다. [소스 코.. 2024. 2. 29.
백준 1766 c++ "문제집" -[PlusUltraCode] https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net [필자 사고] 이 문제의 핵심은 위상정렬 알고리즘을 알고 있냐 모르고 있냐 이다. 위상정렬 알고리즘은 쉽게 말해 이 노드와 저 노드가 레벨차이에 따라 정렬해 놓는 알고리즘이다. 또한 이 문제에서 위상정렬에서 사용하는 큐를 보통의 큐가 아닌 우선순위 큐를 사용하여 N이 낮은값부터 출력할 수 있도록 유도했다. [소스 코드] #include #include #include.. 2024. 2. 29.

티스토리툴바