python

문제https://www.acmicpc.net/problem/1368백준 문제집 - 0x1B강 - 최소 신장 트리 알고리즘: 최소 스패닝 트리풀이 어떤 알고리즘을 사용하느냐에 따라 풀이 방식이 달라진다. 1️⃣ 크루스칼 알고리즘 사용크루스칼 알고리즘은 기본적으로 (노드1, 노드2, 비용)형태의 데이터를 오름차순으로 정렬하여 사용한다.하지만 이 문제에서는 두 가지 조건이 제시된다.1) 다른 논에서 물을 끌어올것인지2) 논에 새로운 우물을 팔 것인지→ 일단 정렬 후 연결비용과 우물비용 중에서 비교해야하나? 싶었지만 아니었다. 🗝️ 가상의 논 N을 설정한 뒤, (i, N, 논 i의 우물비용)을 그래프에 추가로 저장해주면 된다.그럼 모든 논과 가상의 논 사이에 우물을 파는 비용으로 간선이 연결되고, 크루스칼 ..

문제https://www.acmicpc.net/problem/2637백준 - 문제집 - 0x1A강 - 위상 정렬 알고리즘: 다이나믹 프로그래밍, 방향 비순환 그래프, 위상 정렬풀이 AI의 도움을 받았던 문제다...🤖DP + 위상 정렬을 사용해야하는 문제인데, DP에 더 가까워보인다. 문제에서 구하고자 하는것은 "필요한 기본부품의 종류와 수"인데,기본부품 - 완제품 사이 중간부품이 존재한다.그리고 기본부품은 중간부품, 완제품 모두에 사용될 수 있다. 그런고로 이 문제 역시 DFS로 풀려면 살짝 복잡해진다. (계보 복원가 호석 문제를 떠올려보자...)BFS를 사용하려면 진입차수부터 정리해줘야하는데 무의식적으로 풀다간 실수할수도 있다.장난감은 (기본부품 - 중간부품 - 완제품) 순으로 만들어져야한다.즉, 기..

문제https://www.acmicpc.net/problem/1005백준 문제집 - 0x1A강 - 위상 정렬 알고리즘: 다이나믹 프로그래밍, 방향 비순환 그래프, 위상 정렬풀이 2056: 작업 문제와 같은 로직이다. 작업이 A → B 순으로 처리되므로 B에 해당되는 작업들의 진입차수를 증가시킨다.진입차수 정리가 끝났다면 아래의 과정을 거친다.dp 리스트, queue 생성진입차수가 0인 작업들을 찾음dp값에 해당 작업의 소요시간을 저장queue에 추가위에서 저장한 queue를 가지고 BFS 실행queue: 지금 당장 시작할 수 있는 작업들queue에서 pop한 작업과 연결된 작업들을 탐색연결작업의 진입차수를 1 감소시킴연결작업의 dp값을 갱신함 => max(기존 dp값, 현재 작업의 dp값 + 연결작업의 ..

문제https://www.acmicpc.net/problem/2056백준 문제집 - 0x1A강 - 위상 정렬 알고리즘: 다이나믹 프로그래밍, 방향 비순환 그래프, 위상 정렬풀이 🗝️ DP + 위상정렬 문제다.각 작업은 선행 작업이 끝난 이후부터 시작할 수 있고, 서로 선행관계가 없는 작업들은 병렬적으로 작업할 수 있다.즉, 현재 작업의 선행 작업들 중 가장 늦게끝나는 작업을 시작 기준으로 삼아야한다. 일단 A: 선행작업, B: 후 작업 일 때 A → B 형태로 진입차수를 정리해준다.그리고 DP 리스트를 생성 후, 진입차수가 0인 작업들을 찾는다.해당 작업들의 DP값을 주어진 작업시간값으로 갱신 후, 작업번호를 queue에 삽입한다.BFS를 실행하며 DP값들을 갱신시켜준다. 과정은 아래와 같다.queue..

문제https://www.acmicpc.net/problem/1766백준 문제집 - 0x1A강 - 위상 정렬 알고리즘: 우선순위 큐, 방향 비순환 그래프, 위상 정렬풀이A B => "B를 풀기 전 A를 먼저 푸는것이 좋음"하지만 문제 조건에 "가능하면 쉬운 문제부터" 푸는것이 좋다고 명시되어있기 때문에,우선순위가 같은 문제들은 작은 번호부터 풀어나가야 한다.예를들어 우선순위가 1 → 2, 1 → 4와 같이 되어있다고 가정해보자.기존의 위상 정렬은 결과가 1, 2, 4가 되든, 1, 4, 2가 되든 상관없었지만,이 문제에선 "쉬운 문제"부터 풀어야 하므로 1, 2, 4가 답이 된다. 첫 시도는 DFS로 N번 문제부터 풀어나가는 방식이었다.큰 번호 → 작은 번호 순으로 진행되므로 자연스럽게 어려운 문제 → ..

문제https://www.acmicpc.net/problem/21276백준 문제집 - 0x1A강 - 위상 정렬 알고리즘: 정렬, 해시를 사용한 집합과 맵, 방향 비순환 그래프, 위상 정렬풀이 🚨 주의해야할 부분은 후손들이 "직계 조상(=부모)"를 기억하고 있는게 아니라는 것이다.그냥 본인의 조상 중 아무나를 선택한것이므로, 해당 조상의 범위는 (시조 ~ 부모)인 셈이다.고로 이 문제를 DFS로 푼다면 조건처리가 까다로워질것이다...(일단 나는 시간초과로 실패함) 따라서 BFS로 풀이했는데, 진행 과정은 다음과 같다.조상 → 자손 형태로 진입차수를 정리해줌진입차수가 0인 사람들 = 시조 이므로, 시조들을 모두 queue에 삽입직계자손들을 기록할 리스트를 따로 생성 후 BFS 실행queue가 빌 때까지 아..