PS/BOJ
-
[BOJ] 1509 팰린드롬 분할PS/BOJ 2020. 7. 15. 18:42
https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하�� www.acmicpc.net 알고리즘: DP 시간복잡도: O(N^2) 접근: 1. 팰린드롬 문자열 -> 팰린드롬 문자는 부분 문제의 속성을 지녔기 때문에 Dynamic 으로 접근하기가 용이함. 2. (특정 규칙을 가지고) 분할 및 개수 구하기 -> 이 부분도 Dynamic 속성을 응용하기 쉽다. 예를 들어, D[i]: 0~i까지 분할(그룹)의 개수 라고 ..
-
[BOJ] 1490 자리수로 나누기PS/BOJ 2020. 7. 15. 17:05
https://www.acmicpc.net/problem/1490 1490번: 자리수로 나누기 어떤 수 N이 주어졌을 때, N으로 시작하면서, N의 0이 아닌 모든 자리수로 나누어지는 떨어지는 수 중 가장 작은 수를 출력하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘: Math (최소공배수-소인수분해) 접근: 1. N의 0이 아닌 모든 자리수로 나누어 떨어져야 함. -> 각 자리수들의 최소공배수 $$Ans = lcm(a_0, a_1, ... , a_k)*t$$ 2. N으로 시작하면서 ... $$N*10^k \le Ans < N*10^{(k+1)}$$ $$let\ m=lcm(a_0, a_1, ... , a_k)$$ $$Then, {N*10^k\over m}\le t$$ $$\therefo..
-
[BOJ] 12852 1로 만들기 2PS/BOJ 2020. 7. 15. 15:18
https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 알고리즘: DP, DFS 시간복잡도: O(logN) 1463 1로 만들기에서 경로 추적을 추가한 문제. https://moon323.tistory.com/5 접근: Dp 경로 추적 문제들이 늘 그렇듯 점화식에서 참고한 부분문제의 성분을 저장해주면 됨. ex) v[] : 경로 추적 배열 D[X] = Min(D[X/2] + X%2 + 1, D[X/3] + X%3 +1) 에서 D[X/2] 부분을 가져왔으면 v[X] = 2로 표시, D[X/3] 부분을 가져왔으면 v[X] = 3 으로 표시 v를 참고하여 역추적..
-
[BOJ] 1463 1로 만들기PS/BOJ 2020. 7. 15. 15:06
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 알고리즘: DP, DFS 시간복잡도: O(logN) 문제는 Dynamic 이긴 한데... N 조건이 작기도(10^6) 하고, 취하는 연산이 계속 나누는거여서 DFS로도 충분히 빠르게 풀리긴 함. Dynamic 접근: 1. 연산을 사용하는 횟수의 최솟값을 출력 2. 답이 이전 부분 문제들에 영향을 받음. -> ex) N = X*2 라고 하자. N의 최소 연산 횟수를 알려면 그 전에 X의 최소 연산 횟수를 알아야한다. 정수 X에 대한 3가지 연산을 잘 관찰하면 점화식을 아래와 같이 정리할 수 있다. D[X] = M..
-
[BOJ] 1202 보석 도둑PS/BOJ 2020. 7. 15. 14:51
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net 알고리즘: Greedy 접근: 1. 가방에는 보석을 한 개만 넣을 수 있다. -> 각 가방은 본인이 담을 수 있는 보석 중에 가장 가치가 큰 보석을 가져야 한다. (Greedy 방식 접근) 다만, 무턱대고 가장 가치가 큰 보석을 집으면 안됨. ex) 3 2 1 100 11 20 3 1 20 5 무게가 20인 가방이 무턱대고 가장 가치가 높은 1짜리 보석을 넣으면 그 밑에 무게가 5인 가방이..
-
[BOJ] 1197 최소 스패닝 트리PS/BOJ 2020. 7. 15. 14:29
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 � www.acmicpc.net 알고리즘: MST(Kruskal, Prim) 시간복잡도: O(E*logV) 1. Kruskal (간선 기준): 가중치가 최소인 간선부터 하나씩 선택해가면서 같은 트리에 속해있는지 확인. 같은 트리인지 확인하는건 Union-Find 알고리즘 이용 2. Prim (정점 기준): 정점 기준으로 BFS 돌리기 (가장 작은 가중치를 가진 간선 선택) pri..
-
[BOJ] 1005 ACM CraftPS/BOJ 2020. 7. 15. 13:29
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 알고리즘: 위상 정렬 시간복잡도: O(n^2) 접근: 1. 건물 짓는 순서가 정해져 있음. 2. 각각의 건물들은 선행 건물들이 모두 지어져야 건설 가능. Point: 순서, 선행(prev.) -> 위상 정렬 최종 시간복잡도: O(n^2) 더보기 #include #include #include #define MAX(a, b) (((a)>(b))?(a):(b)) using namespace s..