반갑습니다!

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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값을 기준으로 한 간..