Stargazer

접근: 가방에는 무조건 1개만 넣을 수 있고, 최대한 넣었을 때 가장 가치가 높은 거를 넣어야 하는데, 가방 중에 가장 작은 가방에 들어갈 정도의 보석이라면, 다른 가방에는 무조건 들어갈 수 있게 된다. 전략: 가방과 보석을 크기 오름차순으로 정렬을 한다. 모든 가방을 조사하면서, 이 가방에 들어갈 수 있는 보석을 모두 꺼내어 놓은 뒤, 이 중 가장 가치 있는 것을 넣어서 하나 씩 가방을 채운다. 그렇게 되면, 들어갈 수 있는 가방 중에 가장 가치 있는 것 부터 넣을 수 있게 된다. 이때, 우선순위 큐를 이용하면, 가방에 들어갈 수 있는 보석 중에 가장 가치 있는 것을 선택하기 수월하다. 각 보석은 조사할 때 한 번 우선순위 큐에 들어간 보석은 더는 조사하지 않는다. 이유는 우선순위 큐의 성질에 의해서 ..

접근: 우선 모든 벡터의 조합을 계산 해보면, 최대 C(20*19, 10) 인데 기하급수적인 크기의 수이다. 여기서 접근은 벡터의 덧셈 뺄셈의 성질을 이해하는 것이 중요하다. 벡터는 시작점과 종점으로 이루어져 있는데, 예를 들어 두 점을 (a,b) (c,d) 라고 하면, 벡터 v는 v = (c-a, d-b) = (c,d) - (b,a) 라고 표현 할 수 있다. 모든 벡터의 합은 v1+v2+...+vn = {(c1,d1)+(c2,d2) + ... + (cn ,dn)} - {(b1,a1) + (b2,a2) + ... + (bn, an)} 라고 볼 수 있다. 모든 점을 한 번씩 사용해야 하므로, 점이 n개가 있다면 n/2개의 점을 선택해서 다 더한 것에 남은 점들을 다 뺀 것과 같다. 이렇게 된다면, 최악의 ..

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

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

접근: 트리를 이용해서 푸는 문제 트리를 순회하는 순서만 생각하면 된다. 전략: 우선 트리 저장을 배열 형태로 저장하는데, 저장 방식은 다양하나 나는 각 알파벳을 숫자로 치환해서 저장하도록 하겠다. (공간을 많이 잡아먹지 않는 문제이기 때문에, 편한 대로 쓰도록 하겠다. 즉, 최적화된 건 아님) 순회할 때 필요한 정보는 현재 위치와 자식 노드의 유무이다. 구현: #include #include using namespace std; struct Node{ int left; int right; }; vector nod; int n; int c2n(char a){ return (a != '.') ? static_cast(a - 'A') : -1; } char n2c(int a){ return (a + 'A')..