일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- JUnit 5
- 투 포인터
- 동적계획법
- 그리디
- 백준
- 구현
- 스택
- BFS
- 세그먼트 트리
- Network
- Effective Java
- 플로이드-와샬
- 프로그래머스
- java
- 위상정렬
- 유니온 파인드
- 후니의 쉽게 쓴 시스코 네트워킹
- mst
- 완전탐색
- dfs
- 문자열
- swea
- 백트래킹
- 시뮬레이션
- CS
- 이분탐색
- 알고리즘
- 수학
- 에라토스테네스의 체
- Kotlin
목록mst (7)
반갑습니다!
1647번: 도시 분할 계획 boj.kr 풀이 이 문제는 최소한의 비용으로 두 마을을 만들어야하는데, 결국 1개의 최소 스패닝 트리를 만들고 그 중에 가장 큰 간선을 제거해주면 최소한의 비용으로 2개의 마을을 만든 것과 같다. 크루스칼 알고리즘을 사용해서 최소 스패닝 트리를 만들어서 해결하였다. 코드 C++ #include #include #include using namespace std; int n, m; vector edges; vector root; int find(int v) { if (root[v] != v) root[v] = find(root[v]); return root[v]; } void merge(int a, int b) { a = find(a); b = find(b); if (a < ..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 해당 문제는 크게 3단계로 풀이된다. 사다리 설치가 필요없는 지형들 그룹화 그룹화된 지형들 사이를 이동하는 최소 비용 저장 저장된 최소 비용들로 MST 생성 1. 사다리 설치가 필요없는 지형들 그룹화 DFS 혹은 BFS를 사용하여 사다리가 필요없이 이동가능한 지형들을 하나의 그룹으로 표시한다. 아래의 코드에서는 방문 여부를 체크하는 visited배열을 int형으로 선언하여 방문 여부의 체크와 그룹 표시를 같이 진행하였다. 2. 그룹화된 지형들 사이를 이동하는 최소 비용 저장 visited배열에 그룹을 구..