Stargazer

접근: 이름 부터 최소 스패닝 트리를 구하는 문제 이에 대한 알고리즘은 prim 알고리즘과 kruskal 알고리즘이 유명하다 전략: prim보다는 krusal이 조금 더 접근하기 쉬울 것 같아서 선택했으나, 둘 중 뭘 선택 해도 상관은 없다. 간선을 가중치가 낮은 순서대로 정렬을 한 후에, 작은 것부터 하나씩 tree에 추가한다. 추가할 때는 사이클이 발생하지 않도록 해야하기 때문에, 간선을 추가하려고 할때 두 정점이 같은 집합인지를 확인한다. 같은 집합이라면 패스하고 다음 간선을 조사한다. n-1번이 추가되면 종료한다. (다만 다음 코드 상에는 딱히 최적화를 진행하지 않고, 전체 조사를 하도록 하였다.) 구현: #include #include #include using namespace std; str..

DP는 정말 매번 할 때마다 새로운 느낌이라고 해야할까 접근 방식을 찾는게 가장 중요한 알고리즘이다. 본인도 실버인 문제임에도 불구하고 접근방식이 한번 꼬여서 2시간을 계속 시도 했는데, 예시는 잘되는 상황이다 보니 좀 더 할 것 같다는 생각에 계속 붙잡고 돌고 돌았던 문제였다. 접근: 본인은 접근 자체를 스티커를 선택할 수 있는 경우를 셌었다.(선택x, 첫째줄, 둘째줄) 그러나 이런 접근 보다 더 간단한 접근이 있었다. 우선 조건은 상하좌우를 스티커를 뗄 수가 없다는 점에서 감안하면, 이전 결과가 현재 결과에 영향을 준다는 점에서 DP를 사용하면 좋겠다는 생각을 했다. 일단 몇단계를 손수 해보면, 상하좌우가 막히면, 다음 단계는 대각선으로 스티커를 선택 할 수 있게되는데, 이 스티커를 선택해도 되는가는..