프로그래머스 - 섬 연결하기: 크루스칼
ncostsreturn4[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]4 다음과 같은 그래프에서 MST(최소신장트리)를 만든뒤 그 비용을 반환하는 문제이다.Greedy로 분류된 문제이길래 costs를 비용기준 오름차순을 만들고 Set을 통해 모든 노드를 방문할 때까지 return값에 간선비용을 더했다. 후에 알고보니 이 방식이 크루스칼 알고리즘이었다;;내가 생각한 방법이 이미 있는 알고리즘인 것까지는 좋았다만 방문처리만으로는 모든 노드가 연결되어있는지 알 수 없었다. 따로 떨어져 있는 집합이어도 방문처리는 되기때문.그래서 찾은 방법이 유니온 파인드 자료구조? 알고리즘?이었다. https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%..
데이터 컨테이너 성능
BFS 문제를 풀다 효율성에서 막혀 vector, tuple, struct에 대해 정리하게 되었다. 프로그래머스 2레벨 게임 맵 최단거리int solution(vector > maps){ int answer = 0; vector> visited(maps.size(), vector(maps[0].size(), false)); tuple location = { 0,0,1 }; //vector location = { 0,0,1 }; pairtarget = { maps.size()-1,maps[0].size()-1 }; queue> que; que.push(location); visited[0][0] = true; int dx[4] = { 0,0,-1,1 }; int dy[4] = { -1,1,0,0 }; in..