목록문제풀이/Programmers (42)
말랑한 하루
[ 학습 내용 ] 최소치의 다리를 선택하면서 진행하되, 다리를 통해 연결되는 섬이 이미 연결되었는지를 판별해야한다. 처음 시도는, 단순하게 다리를 놓을 때 양 쪽 섬을 방문했었는지 판별했다. 그러나, 이는 서로 각각 연결된 두 그룹을 이을 때, 이미 모든섬이 방문했으므로 다리를 놓지 않아 마지막 연결에 실패한다. 다음 시도로, UnionFind를 활용하여 다리를 놓는 두 섬의 부모를 판단해 겹치는지 판단하는 것이다. 만약 겹친다면, 그 연결될 섬은 Cycle이 발생하고 겹치지 않는다면, 그 연결될 섬은 처음 연결되는 섬이므로 연결해준다. 여기서 그래프의 Cycle을 판단할 때, UnionFind가 가장 빠르고 편한방법인지 추후 확인하여 활용하려 한다. [ 소스 코드 ] function solution(n..
[ 개요 ] 그리디 [ 학습 내용 ] 그리디에서 가장 많이 본 유형의 문제가 아닌가 싶다. 여러구간이 존재하고, 그 구간이 겹치는 곳에 최소한의 무언가를 설치한다는 내용을 포함한 그리디 문제 이 문제를 해결하기 위해 다음의 경우를 항상 외워두도록 했다. 1) 구간에 대해 오름차순 할것 2) 첫 구간의 끝을 기억하고 배제한 뒤 시작할 것 3) 다음구간과 비교할 때 다음을 판단할 것 3-1) 내 기준끝점이, 현재 구간의 시작점보다 작은가? → 결과가 추가되어야 하며(현 문제에서는 카메라) 내 기준끝점을 현재구간의 끝점으로 변경한다 3-2) 내 기준끝점이, 현재 구간의 끝점보다 큰가? → 내 기준끝점을 현재구간의 끝점으로 변경한다 ※ 위 두 경우에 현재구간의 끝점으로 변경하는 이유는 다음구간과 비교하기 위해서..