16562 친구비 알고리즘 (union find) 1. unionfind 를 구현하되, 루트에 친구비가 적은 것이 오도록함 2. 루트만 골라 친구비를 정산한다. 코드 #include <iostream> #include <vector> #include <cstring> #include <algorithm&g...

1655 가운데를 말해요 내 방식 (multiset) 1. 멀티셋으로 가운데를 트래킹해가면서 구함 2. 첫번째 원소를 넣고, s.begin()으로 첫번째 iter를 middle로 받고 그대로 출력 3. 두번째부턴 middle과 같은 원소가 들어오면, s.insert(s.upperbound(*middle), input) 으로 가장 앞에 넣음 아...

1647 split town 알고리즘(MST) 1. MST를 만들고, 가장 거리가 긴 길을 빼면 된다. 2. n개의 노드에 대해 n-1개의 간선만 연결되어있으므로, 1개만 빼면 딱 두개로 나눌 수 있는데, 뺀다면 가장 거리가 긴 길이기 때문이다.(2개 이상 빼면 3개이상으로 나눠짐) 코드 #include <iostream> #inc...

1644 소수의 연속합 알고리즘(에라토스테네스의 체, 두 포인터) 1. 에라토스테네스의 체로, N이하의 소수를 모두 구함 2. 두 포인터로 일치하는 해당하는 연속합을 구함 초기 : start = 0, end = 1, sum = prime[0] while start < end if sum == N count++ ...

1562 계단수 알고리즘(DP, 비트마스킹) 1. 숫자를 기록하는 num[101] 배열과, DP[101][10][1 << 10] 배열을 이용하여 DP로 품 2. 앞에서부터 길이에 맞게 숫자를 하나하나 기록해감. 기록하면서 비트마스킹으로 0~9가 있는지 표시 -> 이때 이미 표시된 비트에 또 표시하면 기록이 망가짐. 따라서 &...

1516 Developing game 알고리즘(위상정렬, 그래프. DP) 1. 어떤 건물을 짓기 위해 필요한 건물을 짓는 시간의 최대 + 이 건물을 짓는데 걸리는 시간을 출력하면 됨. 2. 예를 들어 A -> -> D C B -> -> E 로 그래프가 이루어져 있을 때, A : A를 짓는 시간 B ...

1509 팰린드롬 분할 알고리즘(Manacher’s Algorithm, DP) 1. 2차원 bool 형 배열 palindrome에 모든 팰린드롬을 저장. -> palindrome[i][j] 엔 시작이 i이고 끝이 j인 문자열이 팰린드롬인지 아닌지 저장돼있음 -> 구하는 법은 처음부터 i = 0~length, j = i~length; ...

14939 불끄기 알고리즘(브루트, 그리디, 비트마스킹) 1. 최소한으로 눌러야하는 경우 : 한 칸은 한번만 눌러야함. 두번 이상누르면 최소가 아니고, 무한 루프가 될 수 잇음 2. 모든 방법을 다 검사해봐야 정답을 얻을 수 있음 -> 브루트 포스 3. 한번씩만 누르면 누르는 순서는 중요하지않음 -> 첫줄부터 차례대로 누름 4. 이때 첫...

14938 서강그라운드 알고리즘(플로이드워셜) 1. 접근 방법 - 처음엔 DFS 또는 BFS로 접근 - 근데 해보니 이전에 왔던 것보다 적은 거리를 써서온건 보내고, 보낸 다음부터 이어지는 건 겹치면 빼야함. - 결국 플로이드워셜로 최소거리를 모두 구한 후, 탐색범위 안에 들어오는 지역의 아이템을 모두 더하는 방식과 동일함. 코드 #in...

14500 Samsung sw test 알고리즘 1. 가능한 모든 모양으로 검사. 코드 #include <iostream> #define MAX_WIDTH 501 using namespace std; int width, height; int map[MAX_WIDTH][MAX_WIDTH]; void getProperties();...