목록중간에서 만나기 (3)
알고리즘 모음(C++)
백준 7453 - 합이 0인 네 정수(C++)
문제 링크입니다. https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 중간에서 만나기 방법을 사용하는 문제입니다. 배열 A, B, C, D에서 수를 한 개씩 뽑아 합이 0이 되게 만드는 문제입니다. 배열의 크기가 크기 때문에 모든 경우를 탐색하기에는 무리가 있습니다. 따라서, (A+B) / (C+D)로 나눠서 합을 구한 뒤, 둘을 합치는 방법을 사용합니다. 두 배열에 있는 수를 더하는 것이기에 합이 같은 경우가 있을 수 있습니다...
백준 1450 - 냅색 문제(C++)
문제 링크입니다. https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net '중간에서 만나기' 를 사용하는 문제입니다. 가방에 물건을 C이하만큼 넣을 수 있습니다. 하나의 물건에서 할 수 있는 경우는 선택O / 선택X인 2가지입니다. 물건이 총 30개까지 주어지니, 전체의 경우는 2^30입니다. -> 시간초과가 생깁니다. 따라서, 문제를 풀기 위해선 '중간에서 만나기'를 사용해야합니다. 중간에서 만나기란, 전체 경우를 2가지로 나눠서 생각하는 것입니다...
백준 1208 - 부분수열의 합 2(C++, 복습)
문제 링크입니다. https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net '중간에서 만나기' 방법을 사용하는 문제입니다. 중간에서 만나기에 대해 잘나와있는 설명입니다. 해당 블로그를 참고해주세요 -> https://restudycafe.tistory.com/523 문제에서 N의 값은 최대 40입니다. 수는 선택하거나 선택하지 않는 2가지 방법이 있습니다. 그렇다면 모든 경우의 수를 확인해보려면 2^40이 나오게 ..