Algorithm
-
[코딩테스트] 분할과 정복(하노이탑/영역구분/트로미노 문제)Algorithm 2023. 10. 26. 18:42
1.하노이탑 (백준 11729) https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 1) 문제 2) 풀이 #include #include using namespace std; void hanoi(int num,int from,int by,int to){ if(num==1){ cout
-
[코딩테스트] 수학적 귀납법 (분할과 정복)Algorithm 2023. 10. 23. 10:50
1. 수학적 귀납법 문제) 임의의 정수 n을 입력받아 1부터 n까지 합을 구하는 프로그램 내 풀이) #include using namespace std; int function(int n,int sum){ if(n==0) return sum; sum+=n; return function(n-1,sum); } int main(){ int n,result,sum; cin>>n; result=function(n,sum); coutn; result=function(n); cout>k; function(n,k); while(!s.empty()){ coutn>>k; cout 총 2가지라고 생각했었는데, 세로로 2*1 타일 2개 배치하는 경우는 f(n-1)까지는 채워져있다고 가정했을 경우에 이미 포함된 경우이므로 제외..
-
(이진 검색 트리)7662 이중 우선순위 큐Algorithm/baekjoon 2022. 2. 25. 15:32
https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; multiset ms; int main() { cin.tie(NULL); cin.sync_with_stdio(false); cout.tie(NULL); int T; cin >> T; while (T--) ..
-
(dp)1463 1로 만들기/9095 1,2,3 더하기Algorithm/baekjoon 2022. 2. 22. 17:03
1.1463 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; int d[1000001]; int main() { cin.tie(NULL); cin.sync_with_stdio(false); cout.tie(NULL); int N; cin >> N; d[1] = 0; for (int i = 2; i T; for (int i = 0; i < T; i++) { int n; cin..
-
(bfs/dfs)4963 섬의 개수Algorithm/baekjoon 2022. 2. 22. 15:51
bfs/dfs 연장선상의 문제였지만 푸는 데 시간이 오래걸렸다. 고난이 많았던 문제... https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #define X first #define Y second using namespace std; int dx[8] = { -1,-1,-1,0,1,1,1,0 }; int..
-
1260 DFS와 BFS/11724 연결요소의 개수Algorithm/baekjoon 2022. 2. 20. 18:55
(1)DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; vector graph[1001]; vector visited(1001, false); void DFS(int ver) { cout > v1 >> v2; graph[..
-
(재귀)1629 곱셈/1074 ZAlgorithm/baekjoon 2022. 2. 19. 12:10
1.1629 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; using ll = long long; ll POW(ll a, ll b, ll c) { if (b == 1) return a % c; ll value = POW(a, b / 2, c); value = value * value % c; if (b % 2 == 0) return value; ..
-
1978 소수 찾기/2609 최대공약수와 최소공배수Algorithm/baekjoon 2022. 2. 19. 00:05
1.1978 소수 찾기 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; int main() { cin.tie(NULL); cin.sync_with_stdio(false); cout.tie(NULL); int n; cin >> n; int cnt = 0; for (int i = 0; i > a; bool flag =..