일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 구현
- 스택
- swea
- CS
- 투 포인터
- Network
- 후니의 쉽게 쓴 시스코 네트워킹
- 세그먼트 트리
- mst
- 백준
- 동적계획법
- Kotlin
- java
- 시뮬레이션
- 에라토스테네스의 체
- 알고리즘
- 완전탐색
- 위상정렬
- 프로그래머스
- BFS
- 그리디
- 백트래킹
- 수학
- dfs
- JUnit 5
- 이분탐색
- 유니온 파인드
- 문자열
- 플로이드-와샬
- Effective Java
목록mst (7)
반갑습니다!
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 모든 섬을 연결하라는 의미는 결국 MST를 만들라는 말과 같다. 아래의 코드에서는 입력으로 들어온 costs 벡터를 edges 벡터에 저장하고 kruskal 알고리즘을 사용해 MST를 생성해서 해결했다. 코드 C++
17472번: 다리 만들기 2 boj.kr 풀이 [프로그래머스] 지형 이동과 유사한 문제인데 개인적으로 조금 더 까다로웠다. 상당히 구현할 것이 많은 문제이다. 해당 문제는 완전탐색으로도 해결할 수 있다고 한다. 아래의 코드는 MST를 사용해서 해결하였다. 이 문제에서 MST를 만들어서 문제를 해결하려면 크게 3단계로 나누어서 풀어야한다. 섬들 라벨링 하기 섬들 간의 거리 구하기 MST 생성하기 우선 섬 라벨링은 BFS 알고리즘을 통해 할 수 있었다. visited[][] 배열을 선언해 중복 방문을 막아주었다. // 섬들을 구분하기 위해 bfs 알고리즘 사용 void bfs(int x, int y, int idx) { queue q; q.push({ x, y }); visited[y][x] = idx; ..
6497번: 전력난 boj.kr 풀이 MST로 풀 수 있는 문제이다. 문제는 도시에서 절약할 수 있는 최대 액수를 구하는 것이고 이는 최소 액수로 가로등을 키는 문제라고 생각할 수 있다. 따라서 kruskal 알고리즘을 통해 가로등을 키는데 필요한 비용을 계산하고, 전체 비용에서 빼주면 된다. 코드 C++ Python3
4386번: 별자리 만들기 boj.kr 풀이 MST 알고리즘 기초 문제이다. 입력 값으로 주어지는 간선이 없기 때문에 별들 사이의 모든 간선을 구한 뒤 kruskal 알고리즘을 사용해 MST를 생성해주고 소수 둘 째 자리에서 반올림해주면 어렵지 않게 해결할 수 있다. 코드 C++
2887번: 행성 터널 boj.kr 풀이 문제를 읽어보면 MST를 만들어주면 해결할 수 있을거라는 생각이 든다. 그런데 일반적인 문제와 달리 간선의 길이가 주어져있지 않고 min(|xA-xB|, |yA-yB|, |zA-zB|)라는 조건만 나와있다. 이를 위해서 모든 접점 간의 거리를 구해 MST를 만들려고 하면 메모리 초과가 발생한다. 그렇기 때문에 다른 방식을 생각해야 한다. 사실 이 문제는 모든 접점 간의 거리를 구할 필요가 없다. 결국 MST를 만들어야하므로 각 접점 간의 최소 거리가 필요하다. 접점 간의 최소 거리라는 것은 결국 min(|xA-xB|, |yA-yB|, |zA-zB|)을 통해 계산한 거리이다. 이 것을 다시 생각해보면 두 접점 사이에 x값을 기준으로 한 간선, y값을 기준으로 한 간..