Stargazer

접근: 용액을 모두 탐색 하긴 해야 하기 때문에, 탐색방법 중에 두포인터를 이용하도록 하겠다. (막상 두포인터인지는 모르겠다...) 전략: 입력 받은 값을 오름차순으로 정렬 후에, 작은 것부터 하나씩 기준을 정한다. 그 기준으로 오른쪽 배열에서 가장 왼쪽과 가장 오른쪽을 먼저 선택하고, 용액을 합쳤을 때 절댓값이 작게 되도록, 그 간격을 좁히는 방향으로 점점 이동한다. 만나면 다음 기준으로 옮기고 반복한다. 코드: #include #include #include #include using namespace std; int n; // 3~5000 long long sum = 3000000001; vector input; int main(){ cin >> n; input.resize(n); for(int i..

접근: 처음에는 어떻게 접근 해야 할지 직접 그려보면서, 관계를 파악해보았다. 대충 봐도 그래프 이론으로 풀어야 하는데, 그 중 순서 정렬이 필요하기 때문에 위상 정렬로 풀어야 한다는 걸 알 수 있다. 전략: 대소 관계를 표현하기 위해 입력을 digraph(유향그래프) 형태로 입력을 받는다.(형식은 자유 - 행렬, 인접리스트) 진입 차수가 0인 노드부터 큐에 넣고, 큐에서 하나씩 제거하면서 출력한다. 제거한 노드가 가리키는 다른 노드의 진입 차수를 한개 줄이고, 만약 0이라면 큐에 삽입한다. 코드: #include #include #include using namespace std; int n,m; vector comp; vector income; int main(){ cin >> n >> m; comp..

접근: 스도쿠 자체로 크기가 9x9로 정해 있기 때문에, 백 트래킹 이 가능한 크기다. 따라서 백트래킹으로 하나씩 전부 조사하되 사전식으로 조사하면 된다. 전략: 앞에서 부터 하나씩 입력 받을 때, 0의 위치와 갯수를 입력받아서 백트래킹으로 각 점을 대입하면서 답을 찾아본다. 코드: #include #include using namespace std; int map[9][9]; int cnt = 0; bool flag = false; vector vac; bool visit[81] ={false,}; void print(){ for(int i=0;i

접근: 어떤 자연수가 주어지면 그것보다는 작은 소수의 합의 갯수를 구하는 것이므로, n보다 작은 소수의 배열을 구하고, 그에 맞는 구간 합을 구하면 된다. 전략: 소수를 구하는 것은 에라스토테네스의 체를 이용하여 구하면 되고, 구간합은 투 포인터(two pointers)를 이용하여 구하면 된다. 코드: #include #include #include using namespace std; vector sosu; //n이하 소수 배열 bool so[4000001]; //소수 판별 배열 int n; int sum = 0; int s = 0, e = 0; int res = 0; int main(){ cin >> n; for(int i=2;i= sosu.size()) break; sum += sosu[e++]; ..

접근: 전광판이 무한으로 연결되어서 나오는 형태의 광고이기 때문에 적어도 L 만큼은 광고 할 수 있음이 보장이 되어있다. 문제는 주어진 문자열에 대해서 어떤 광고를 말하는 것인지 최소 길이를 구하는 것이다. 문제의 예에서도 말했듯이, aabaaa 가 주어졌다면, aaba 는 광고가 가능한 최소 길이이다 중요한 것은 반복할 문자열이 그 뒤에 얼마나 겹치는 가이다. 그래서, 최소 길이를 구하려면, 길이 L 에서 최대한 겹치는 부분을 제외한 나머지 부분으로 구해야한다. 위 예로 들자면 aabaaa 처럼 뒤에 2개가, 길이 L이 주어졌을 때, 반복하면 최대로 겹치는 부분이다. 그렇기 때문에 저 2개를 제외한 나머지 부분이 반복해야 할 최소 길이가 된다. 전략: KMP 알고리즘을 이용하여, 하나씩 길이를 늘려가면..

접근: 가방에는 무조건 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')..