전체 글 (19) 썸네일형 리스트형 1208번_부분집합의 합 2_BOJ 문제 링크1208번 부분집합의 합 2 : https://www.acmicpc.net/problem/1208 문제 설명 및 해결 아이디어정수의 개수 N이 범위가 1이상 40이하이므로, 부분집합의 개수는 2^40이 되기때문에 완전탐색으로 해결할 수 없다.그래서 주어진 정수를 절반으로 나누어 왼쪽 절반과 오른쪽 절반의 모든 경우의 수를 구하는 방법으로 접근해야한다.그래서 O(2^(N/2)log2^(N/2))으로 해결할 수 있다. 부분집합을 구하는 방법은 아래의 코드를 참고하면 된다. 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #incl.. 7453번_합이 0인 네 정수_BOJ 문제 링크7453번 합이 0인 네 정수 : https://www.acmicpc.net/problem/7453 문제 설명 및 해결 아이디어모든 경우를 다 탐색하면 O(n^4)이기 때문에 시간초과가 난다.그래서 4개의 배열 A, B, C, D중 A와 B의 가능한 모든 합을 저장한 벡터와 C와 D의 가능한 모든 합을 저장한 벡터를 둔다. 두 벡터의 합이 0이 되는 경우의 수를 찾으면 된다.두 개의 배열에서 가능한 모든 합을 구하는 것이 O(n^2)이므로 이 문제는 O(n^2longn^2)에 해결이 가능하다. 코드12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include using na.. 2632번_피자판매_BOJ 문제 링크2632번 피자판매 : https://www.acmicpc.net/problem/2632 문제 설명 및 해결 아이디어가능한 모든 방법의 가지 수를 계산하는 문제이다.피자는 붙어있는 경우에만 합칠 수 있기때문에 이중포문을 이용해서 합칠 수 있는 경우의 크기만 apizz, bpizz벡터에 넣어주었다. 손님이 주문한 크기와 똑같은 크기의 조각이 있을 수 있으므로, A, B 두 종류의 피자에서 주문한 크기와 똑같은 것들은 먼저 count를 해준다.그 후 A피자에서 나올 수 있는 모든 크기를 탐색하면서, B피자중에 나올 수 있는 크기와의 합이 손님이 주문한 피자의 크기가 나오는 것이 있으면 count해주면 된다. 코드1234567891011121314151617181920212223242526272829.. 12015번_가장 긴 증가하는 부분 수열2 / 가장 긴 증가하는 부분 수열3_BOJ 문제 링크12015번 가장 긴 증가하는 부분 수열2 : https://www.acmicpc.net/problem/1201512738번 가장 긴 증가하는 부분 수열3 : https://www.acmicpc.net/problem/12738 문제 설명 및 해결 아이디어최장 증가 수열(LIS_Longest Increasing Subsequence)에 관한 설명은 아래 블로그에 자세히 나와있다. http://jason9319.tistory.com/113?category=670441 다음 내용은 허락맡고 가져온 내용임을 밝힌다. 이 블로그에는 잘 정리된 내용들이 많기때문에 많이 들어가보면 좋다.이번 포스팅에서만 유일하게 내용을 가져왔고, 다음부턴 링크만 제공하겠다. http://jason9319.tistory.co.. 1940번_주몽 문제 링크1940번 주몽 : https://www.acmicpc.net/problem/1940 문제 설명 및 해결 아이디어두 수의 합을 구하는 문제와 해결방법이 같다. lo, hi변수를 두어 탐색하면서 푼 첫번째 방법과, binary_search()를 이용하여 푼 두번째 방법이 있다.두번째 방법의 경우, 같은 쌍을 두번씩 찾게 되므로 cnt의 반을 출력해야함을 주의하자. 코드1234567891011121314151617181920212223242526272829#include #include #include using namespace std; int n, m, num;vector vt;int main() { scanf("%d %d", &n, &m); for (int i = 0; i 3273번_두 수의 합_BOJ 문제 링크3273번 두 수의 합 : https://www.acmicpc.net/problem/3273 문제 설명 및 해결 아이디어두 수의 합을 구하는 문제이다. lo, hi변수를 두어 탐색하면서 푼 첫번째 방법과, lower_bound와 upper_bound를 이용하여 푼 두번째 방법이 있다.두번째 방법의 경우, break 조건(a > x/2, a*2==x)을 주의하자. 코드12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std; int n, x, num;vector vt; int main() { scanf("%d", &n); for (int i = 0; i 7795번_먹을 것인가 먹힐 것인가_BOJ 문제 링크7795번 먹을 것인가 먹힐 것인가 : https://www.acmicpc.net/problem/7795 문제 설명 및 해결 아이디어lower_bound를 이용하여 x라는 값을 찾으면, x보다 크거나 같은 값중 최소값의 위치를 return해준다. 이 아이디어를 이용하여 문제를 풀 수 있다. 코드12345678910111213141516171819202122232425262728293031#include #include #include #include using namespace std; int t, n, m, num;vector avt, bvt;int main() { scanf("%d", &t); while (t--) { scanf("%d %d", &n, &m); for (int i = 0; i 10815번_숫자카드_BOJ 문제 링크10815번 숫자카드 : https://www.acmicpc.net/problem/10815 문제 설명 및 해결 아이디어Binary Search문제이다. 해당 숫자가 숫자카드에 있으면 1을 출력하고, 없으면 0을 출력하면 된다. 코드12345678910111213141516171819202122232425262728293031323334353637#include #include #include using namespace std; int n, m, num;vector numCard;int findfunc(int x) { int left = 0, right = n; while (left numCard[mid]) { left = mid + 1; } else if (x 이전 1 2 3 다음
