0850

문제: https://www.acmicpc.net/problem/2887 MST 문제이다. 노드의 수가 100,000이다. 따라서 모든 간선을 연결하면 간선의 수가 너무 많아서 메모리 초과가 나온다. 따라서 최적화할 수 있는 방법을 찾아야한다. 모든 간선을 연결하지 말고 x좌표로 정렬 후 가장 가까운 행성과 간선을 연결한다. 이를 y좌표, z좌표에 대해서도 동일하게 진행한다. 그러면 간선의 수를 N^2에서 3N으로 줄일 수 있게 된다. 그 후 MST의 총 비용을 계산하면 된다. MST 알고리즘은 prim을 사용하였다. 코드는 아래와 같다. #include #include #include #include #include #include using namespace std;typedef long long..

프로그래머스 lv2 문제 중 정답률이 가장 낮아서 풀어보게 되었다.문제: https://school.programmers.co.kr/learn/courses/30/lessons/250135 문제는 간단하다. 시작 시간과 끝 시간이 주어졌을 때, 초침이 분침과 시침을 몇 번 지나가는지 세는 문제이다. 초기 시침, 분침, 초침의 각도를 계산하고 1초 씩 시간을 증가시키며 초침이 시침과 분침을 지나는지 체크했다. 문제 풀 때 유의할 부분은 아래와 같다.1. 처음에는 double로 각도 계산을 했는데, 부동소수점 타입에서 등호, 부등호 계산은 부정확할 수 있기 때문에 360도를 12*3600으로 바꿔서 정수 계산이 가능하도록 했다.2. 시작 때 초침이 분침 또는 시침과 겹쳐있는 경우도 count한다.3. 초침이..

옛날에 ps 공부를 조금 해두기도 했고, 가끔씩 문제를 풀기도 해서 실력 체크 겸, 동상 정도를 탈 수 있지 않을까 해서 참가하게 되었다. 결과는 4솔로 12등 마무리였다. 1~2문제는 더 풀 수 있었는데 아쉬움이 남았다. 시간 제한이 있어서 쉬운 문제도 어려워보이고, 공부할 때 제대로 안 해서 무슨 알고리즘을 써야하는 건 아는데 제대로된 구현을 못한게 컸다. 백준에 문제가 올라와서 빨리 풀 수 있는 문제만 풀어보았다. 아직 못 푼 문제도 천천히 풀 수도..? 있다. 풀이는 아래에 있다. 대회에서 푼 문제는 bold가 되어있다. (A, B, C, D) A: 인경호 울타리 공사풀이: https://wnstnk.tistory.com/25문제 그림에 힌트가 있는 0솔 방지용 문제였다. 그런데 이런 문제에 약해..