https://www.acmicpc.net/problem/1208 수열 요소 개수 최대 40개 부분수열의 합 개수는 맥스 2^40 까지 갈 수 있기 때문에 정답을 구하는 변수는 long long 자료형을 사용해야한다. 브루트포스로 모든 수열을 확인하면 시간초과가 남. O(2^n) 나름 줄여본다고 오름차순 정렬하고, sum 이 S 보다 커지면 break 하는 수를 써보긴 했는데 [0,0,0,0, ... ,0] , N=0, S=0 인 TC의 경우 사실 의미가 없다. 2^40 다 돌아아한다. 근데 이걸 절반 쪼개서 풀면... 된다..? O(2^(n/2) * 2) 절반짜리 집합 두 개 각각의 부분수열합을 다 구해보고 적당히 조합하는거라 직관적으로 큰 차이가 느껴지지 않을 수 있는데, 사실상 굉장히 차..
https://www.acmicpc.net/problem/1647 최소 스패닝 트리(MST)를 구하는 알고리즘에는 크게 두가지가 있음. 크루스칼 알고리즘 - 간선들을 가중치에 따라 오름차순 정렬을 해야함. 간선 개수가 적으면 유리. 가중치가 적은 순서대로 트리에 추가하되 사이클이 생기는 경우는 제외 프림 알고리즘 - 아무 정점이나 하나 고르고 연결된 모든 간선을 집합에 추가한다. 가중치가 가장 작은 간선을 선택하고 그 간선을 따라 도착한 정점의 모든 간선도 집합에 추가한다. 한번 들렀던 정점은 다시 들르지 않는다. https://blog.naver.com/jennifer0606/222417769159 백준 #1922 네트워크 연결 : 최소신장트리(MST) https://www.acmicpc.net/..
https://www.acmicpc.net/problem/1922 최소 신장 트리 (MST) 구하는 알고리즘 1. 프림 2. 크루스칼 크루스칼 알고리즘과 유니온파인드 자료구조를 활용해서 해결 #include #include #include #include using namespace std; int N, M; priority_queue q; int uf[100001]; int Find(int x) { if (x == uf[x]) return x; int p = Find(uf[x]); uf[x] = p; return p; } bool Union(int x, int y) { x = Find(x); y = Find(y); if (x != y) { uf[y] = x; return true; } return ..
https://www.acmicpc.net/problem/1766 선행 조건( 보다 쉬운 문제) 이 딱 하나인 경우 트리 선회하면서 해결할 수 있다. 아래 코드로 해결 가능. 근데 이 문제는 선행 조건이 여러 개일 수 있다..! #include #include #include #include using namespace std; set first; int find_first[32001]; int v_up[32001]; priority_queue q; int N, M; int find(int a) { if (find_first[a] == 0) return a; int k = find(find_first[a]); find_first[a] = k; return k; } int main(int argc, cha..
https://www.acmicpc.net/problem/1562 백준 #10844 : 쉬운 계단 수를 먼저 풀어보자. >>> 조합으로 풀어야하나 고민 참 많이 했고, dp를 어떻게 활용할 지 고민 많이 했는데,, 아주 간단한 점화식으로 해결 할 수 있었다... 계단 수의 접근은 쉬운 계단 수에 서술했다. 1. 브루트포스 각 자리마다 1씩 빼거나 더해가면서 flag 0, flag 9를 체크하고, (계단식이나까 0, 9 체크됐으면 다나온거임) 재귀돌리기 역시 시간초과,, 24자리 이상 힘들다. 2. DP와 비트마스킹 쉬운 계단 수를 풀었다면, 이제 계단 수에서 0~9를 사용했는지 안했는지 체크하면 된다. 이걸 체크하는데 비트 마스킹을 사용한다. 근데..! 여기서 문제가 생겼다... 나는 쉬운 계..
1~e 까지의 문자열 중 팰린드롬으로 쪼개되 그 수가 가장 작게 하는 갯수를 dp 배열에 저장한다. dp[e]는 e로 끝나는 문자열 중에 팰린드롬인 문자열의 시작을 s 라고 놓으면, 모든 s에 대해서 dp[s-1]+1이 된다. 이중에 min 값이 곧 dp[e] 값이 된다. dp 배열을 기본적으로 무한대로 정의한다. a~b가 팰린드롬인 경우를 true, 아니면 false 의 방식으로 bool 2차원배열로 저장한다. 위 점화식을 이용해서 dp 배열을 앞에서부터 채워나가면 된다. >>>>처음에 재귀를 이용해서 i~x 까지 팰린드롬인 모든 x 에 대해서 i= x+1로 다시 재귀를 타는 방법으로 모든 팰린드롬 부분집합 조합을 다 확인하고 원소 개수를 세어서 그중 가장 작은걸로 고르는 방법을 시도했는데,, ..