본문 바로가기

전체 글361

[BOJ]1766번: 문제집 문제: https://www.acmicpc.net/problem/1766 위상 정렬 문제입니다. 우선 indegree 관계를 신경써야하고 indegree가 0인 것이 여러 개라면 숫자가 낮은 문제부터 뽑아야하므로 우선순위 큐를 사용하여 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1766.java 2022. 4. 27.
[BOJ]1647번: 도시 분할 계획 문제: https://www.acmicpc.net/problem/1647 Union-find 문제입니다. 모든 도시가 연결되어 있다는 가정이 있으므로 그래프 => 트리로 만들 수 있습니다. 그리고 모든 도시를 연결하는 트리의 최소 비용은 MST로 만들 수 있습니다. MST를 구성한 상태에서 하나의 간선만 제외하면 도시(컴포넌트)를 2개로 나눌 수 있습니다. 제외하는 한 개의 간선은 MST 간선 중 최대 비용 간선입니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1647.java 2022. 4. 26.
[BOJ]1005번: ACM Craft 문제: https://www.acmicpc.net/problem/1005 위상정렬 + BFS 문제입니다. indegree 배열을 사용하여 루트 노드부터 bfs 방문을 시작합니다. 그리고 자식 노드의 indegree 값이 0이 되었을 때만 큐에 새로 넣어줌으로써 큐에 중복으로 들어가지 않도록 합니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1005.java 2022. 4. 26.
[BOJ]20922번: 겹치는 건 싫어 문제: https://www.acmicpc.net/problem/20922 투 포인터 알고리즘으로 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ20922.java 2022. 4. 13.