앜지

[1182] 부분수열의 합 C++

문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. $1 ≤ N ≤ 20, |S| ≤ 1,000,000$ 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.출력첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.결국에는 모든 경우의 수를 봐야된다고 생각해서 2^n 경우를 모두 고려했다. 재귀함수를 사용하여 순차탐색을 하면서 해당 원소를 포함하거나 포함하지 않은 경우로 재귀적으로 호출을 해서 마지막 인덱스에 도달했다면 s와 sum이 일치하는지 체크후 카운트를 올리도록 코드를 ..

문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 사실 이 문제는 아주 불편하다.원래는 1,2,3으로 개수를 카운팅하는 함수를 사용해서 재귀를 통해서 아주 복잡하게 풀었는데 그거는 중복때문에 답이 안됐고 중복을 카운팅하려면 더 코드가 아주 복잡해져..

https://www.acmicpc.net/problem/10974문제 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.입력첫째 줄에 N$1 ≤ N ≤ 8$이 주어진다. 출력첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다. 모든 순열을 보는 케이스에는 다양한 방법이 있다.다음 블로그 포스트를 참고해서 봤다.https://velog.io/@soyeon207/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%9C%EC%97%B4-yaxs0hh7 [알고리즘] 순열 $Permutation$n개의 값 중에서 r 개의 숫자를 순서를 고려해 나열한 경우의 수velog.io나는 visited을 사용하지 않고 재귀로 지금까지..

백준을 풀다가 보면 분명히 코드는 작동하는데 메모리나 시간초과로 통과가 되지 않는 케이스가 있다.C++을 사용한다면 혹시 입출력에서 문제가 발생한거 일수도 있다. Printf, scanf와 cin, cout의 차이 C++에서는 C 스타일의 입출력 함수인 printf, scanf와 C++ 스타일의 스트림 기반 입출력 방식인 cin, cout을 모두 사용할 수 있다. 하지만 이 두 방식은 문법, 성능, 안정성 등에서 차이가 있으며, 각각의 장단점이 존재한다. 1. 기본 사용 문법 비교printf, scanf#include int main { int age; float height; printf$"나이를 입력하세요: "$; scanf$"%d", &age$; printf("키를 ..

https://www.acmicpc.net/problem/2003문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N$1 ≤ N ≤ 10,000$, M$1 ≤ M ≤ 300,000,000$이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.출력첫째 줄에 경우의 수를 출력한다. 전형적인 순열 조합 문제다.. NC2 를 구현하면 되는데 브루트 포스를 쓰고 싶긴 했지만 투포인터를 사용해서 풀어줬다.https://butte..

https://www.acmicpc.net/problem/2309학부때 자구/알고를 제대로 공부 안한 벌로 처음부터 다시 시작하겠다.문제왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.입력아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며,..

문제주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력주어진 수들 중 소수의 개수를 출력한다. 풀이:그냥 브루트 포스로 풀면 되기야 하지만 그러면 메모리 초과날까 싶어서 아리스토텔레스의 체를 사용하였다.https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 ..