티스토리

도토리이야기

검색하기

블로그 홈

도토리이야기

23dotory.tistory.com/m

23DOTORY 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

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.. 공감수 0 댓글수 0 2018. 7. 18.
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.. 공감수 0 댓글수 0 2018. 7. 18.
2632번_피자판매_BOJ 문제 링크2632번 피자판매 : https://www.acmicpc.net/problem/2632 문제 설명 및 해결 아이디어가능한 모든 방법의 가지 수를 계산하는 문제이다.피자는 붙어있는 경우에만 합칠 수 있기때문에 이중포문을 이용해서 합칠 수 있는 경우의 크기만 apizz, bpizz벡터에 넣어주었다. 손님이 주문한 크기와 똑같은 크기의 조각이 있을 수 있으므로, A, B 두 종류의 피자에서 주문한 크기와 똑같은 것들은 먼저 count를 해준다.그 후 A피자에서 나올 수 있는 모든 크기를 탐색하면서, B피자중에 나올 수 있는 크기와의 합이 손님이 주문한 피자의 크기가 나오는 것이 있으면 count해주면 된다. 코드1234567891011121314151617181920212223242526272829.. 공감수 0 댓글수 0 2018. 7. 18.
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.. 공감수 1 댓글수 0 2018. 7. 17.
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 공감수 0 댓글수 0 2018. 7. 17.
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 공감수 0 댓글수 0 2018. 7. 17.
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 공감수 0 댓글수 0 2018. 7. 17.
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 공감수 0 댓글수 0 2018. 7. 17.
2110번_공유기 설치_BOJ 문제 링크2110번 공유기 설치 : https://www.acmicpc.net/problem/2110 문제 설명 및 해결 아이디어좌표의 범위가 최대 1,000,000,000이여서 시간초과가 난다.그래서 Parametric Search로 해결할 수 있다.mid값을 간격으로 설정한다.설치한 공유기 개수가 주어진 공유기 개수 C보다 크거나 같을 경우, mid를 크게하여(간격을 크게하여) 공유기 개수를 줄일 수 있다.반대의 경우, mid를 작게하여 공유기 개수를 늘릴 수 있다. 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include using namespace std;#define ll lo.. 공감수 0 댓글수 0 2018. 7. 16.
1300번_K번째 수_BOJ 문제 링크1300번 K번째 수 : https://www.acmicpc.net/problem/1300 문제 설명 및 해결 아이디어이 문제를 그냥 구현하게 되면 시간초과가 난다. Parametric Search로 해결할 수 있다.mid값은 1부터 K까지의 범위안에서 움직여주자. 이 문제를 풀기 위해서는 다음의 내용을 알아야 한다.즉, 특정한 mid값은 mid이하의 수의 개수가 주어진 K개 이상이면서 가장 작은 수가 된다. 코드12345678910111213141516171819202122232425262728293031#include #include using namespace std;#define ll long long intll n, k, res;void func() { ll left = 1, right.. 공감수 0 댓글수 0 2018. 7. 16.
2512번_예산_BOJ 문제 링크2512번 예산 : https://www.acmicpc.net/problem/2512 문제 설명 및 해결 아이디어Parametric Search문제이다.mid는 배정할 예산으로 설정한다.문제의 요구대로, 각 지방의 예산요청액이 배정할 예산액보다 클 경우 예산액을 더해준다.반대의 경우, 예산요청액을 더해준다.그 합이 주어진 총 예산인 M보다 작거나 같을 경우, mid를 크게해준다.반대의 경우, mid를 작게하여 M과 비슷해지도록 합을 작게 해준다. 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include using namespace s.. 공감수 0 댓글수 0 2018. 7. 16.
1654번_랜선 자르기_BOJ 문제 링크1654번 랜선 자르기 : https://www.acmicpc.net/problem/1654 문제 설명 및 해결 아이디어Parametric Search문제이다.이때 right는 10,000,000,000으로 해야한다.mid는 랜선 길이로 설정한다.특정 mid값으로 만들 수 있는 랜선의 개수가 주어진 N보다 작을 경우, mid값을 작게하여 랜선의 개수를 늘릴 수 있다.반대의 경우, mid값을 크게하여 랜선의 개수를 줄일 수 있다. 코드123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include using namespace std;#define MAX_S 10001#defi.. 공감수 0 댓글수 0 2018. 7. 16.
6236번_용돈 관리_BOJ 문제 링크6236번 용돈 관리 : https://www.acmicpc.net/problem/6236 문제 설명 및 해결 아이디어Parametric Search문제이다.left의 범위는 이용할 금액중 가장 큰 값부터 시작하면 된다.mid는 인출 할 금액 K로 설정한다.특정 mid값으로 인출한 횟수가 주어진 M보다 클 경우, mid값을 크게하여 인출 횟수를 줄인다.반대의 경우, mid값을 작게하여 인출 횟수를 늘릴 수 있다. 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #include using namespace std;#define ll long long int.. 공감수 0 댓글수 0 2018. 7. 16.
2343번_기타 레슨_BOJ 문제 링크2343번 기타 레슨 : https://www.acmicpc.net/problem/2343 문제 설명 및 해결 아이디어Parametric Search문제이다.left의 범위는 레슨 중 가장 긴 길이부터 시작하면 된다.mid를 lesson길이로 설정한다.만들어진 블루레이 개수가 M보다 클 경우, mid를 크게하여 블루레이 개수를 줄인다.만들어진 블루레이 개수가 M보다 작거나 같을 경우, mid를 작게하고, 이때의 mid값 중 최소값을 저장한다. 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include using namespace std;#define ll lon.. 공감수 0 댓글수 0 2018. 7. 16.
2805번_나무 자르기_BOJ 문제 링크2805번 나무 자르기 : https://www.acmicpc.net/problem/2805 문제 설명 및 해결 아이디어나무의 수 N은 1이상 1,000,000이하이다. 그리고 가져갈 나무의 길이 M은 1이상 2,000,000,000이하이다. 가장 간단하게 완탐을 하게 되면 O(NM)이 되어 시간초과가 난다.이를 효율적으로 하기위해 Parametric Search로 해결할 수 있다.그리고 이 문제의 비교함수 y=f(x)의 관계를 생각해보면, 다음과 같다. 즉, SUM이 커질수록 가져갈 나무의 길이 M이 작아지는 관계이다. 이를 잘 생각하여 코드를 작성해야한다. 코드12345678910111213141516171819202122232425262728293031323334353637383940414.. 공감수 0 댓글수 0 2018. 7. 15.
1072번_게임_BOJ 문제 링크1072번 게임 : https://www.acmicpc.net/problem/1072 문제 설명 및 해결 아이디어주어진 게임횟수는 최대 1,000,000,000이다. 시간초과가 날 수 있기 때문에 Parametric Search로 접근해야 한다. mid를 게임횟수로 설정하여, 승률(Z)이 변할 때의 mid의 최소값이 문제의 출력이된다. 코드12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std;#define ll long long int#define INF 9999999999999999 ll total, win;ll originRatio, newRatio;ll f.. 공감수 0 댓글수 0 2018. 7. 15.
14502번_연구소_BOJ 문제 링크14502번 연구소 : https://www.acmicpc.net/problem/14502 문제 설명 및 해결 아이디어3개의 벽을 세워 바이러스가 퍼질 수 없는 안전영역 크기의 최대값을 출력하는 문제이다. 기본 아이디어는 완점탐색을 하면서 바이러스가 퍼질수 있는 영역의 최소값을 구하는 것이다.3개의 벽을 세울 수 있는 모든 경우의 수를 돌린다. 각 경우마다 Depth-First Search(DFS)를 수행하여 퍼질 수 있는 영역의 크기를 계산해나간다.바이러스가 퍼질 수 있는 영역 크기의 최소값을 찾은 후, 전체 크기에서 벽(1)의 개수, 새로 세운 벽 3개, 바이러스 퍼진 영역 크기의 최소값을 빼주면 된다. 코드12345678910111213141516171819202122232425262728.. 공감수 0 댓글수 0 2018. 6. 25.
14503번_로봇 청소기_BOJ 문제 링크14503번 주사위 굴리기 : https://www.acmicpc.net/problem/14503 문제 설명 및 해결 아이디어로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 출력하는 문제이다. 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 한다.A. 현재 위치를 청소한다.B. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다.a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한칸을 전진하고 A번부터 진행한다.b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 B번으로 돌아간다.c-1. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 B번으로 돌아간다.c-2. 네 방향 .. 공감수 0 댓글수 0 2018. 6. 25.
14499번_주사위굴리기_BOJ 문제 링크1449번 주사위 굴리기 : https://www.acmicpc.net/problem/14499 문제 설명 및 해결 아이디어주사위를 굴리면서 주사위의 윗면에 있는 수를 출력하는 문제이다. 주사위를 굴려 해당 칸의 수가 0이면, 주사위 바닥 면에 있는 수가 칸으로 복사된다.해당 칸의 수가 0이 아니면, 칸의 수가 주사위 바닥 면으로 복사된다. 그리고 칸의 수는 0으로 갱신된다. 1, 2, 3, 4로 주어진 명령은 각 동쪽, 서쪽, 북쪽, 남쪽으로 주사위를 굴리는 것을 의미한다.주사위가 굴러가는 것은 네 방향 탐색을 이용했다.12int dx[] = {0, 0, -1, 1 };int dy[] = {1, -1, 0, 0 };cs 주사위가 특정 방향으로 굴러가게 되면, 양 옆면은 그대로 이고 나머지 네 .. 공감수 0 댓글수 0 2018. 6. 25.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.