본문 바로가기

알고리즘 관련/BOJ

BOJ)2419 사수아탕 문제:icpc.me/2419 사탕이 담긴 사탕바구니가 x축위에 있고 1초마다 사탕 바구니의 사탕이 1개씩 사라질 때 수아가 먹을 수 있는 최대의 사탕 수를 구하는 문제이다. 문제가 다이나믹 프로그래밍임은 쉽게 알 수 있었지만 먹을 수 있는 최대의 사탕수에 포커스를 맞추니 어려워진 문제였다. 이를 dp[l][r][state]로 해결해야하는데 l에서 r까지 사탕을 커버하고 state(왼,오)에 서있을 때 먹는 최대의 사탕수라고 정의를 한 뒤 제출을 하니까 WA를 받았다. 다시 잘 생각해보니 l~r을 커버할 때 나머지 구간에 사라진 사탕수가 항상 최적으로 있을 수 없다는 걸 깨달았다. 따라서 dp테이블의 정의를 바꾸어 l에서 r까지 구간을 커버하고 사라지는 사탕 수로 문제를 풀어야한다. 근데 이 또한 사라지는.. 더보기
BOJ)2370 시장 선거 포스터 문제:icpc.me/2370 포스터를 붙이는 순서가 주어질 때 보이는 포스터의 수를 출력하는 문제이다. 포스터의 모든 x좌표와 y좌표를 좌표압축 한 뒤 포스터를 역순으로 보면서 이미 본 포스터는 업데이트 시켜주고 내가 보이는지 여부는 이미 업데이트 된 포스터들이 나를 완전히 가리는지 확인하면 된다. 이는 세그먼트 트리를 이용하여 업데이트 된 구간의 합을 찍어냄으로 판별 가능 하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include using namespace std;int n, seg[80040], lazy[80040],.. 더보기
BOJ)3073 집으로 가는 길 문제: icpc.me/3073 집과 아이를 1:1 매칭시켜 주어야 하는데 매칭은 항상 보장되고 이때의 아이들의 최소 이동거리를 출력하는 문제이다. 1:1 매칭이 항상 보장되기 때문에 MCMF로 모델링을 하여 소스->아이->간선->집->싱크로 모델링 해주면 된다. 이 때 각 간선들의 cost를 1로 설정해주면 된다. 다만 문제에 함정이 있는데 언제 고쳐질지는 모르겠지만 입력 N,M이 20~30으로 표기되어 있지만 100 넘게 들어오는거 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879.. 더보기
BOJ)2104 부분배열 고르기 문제: icpc.me/2104 주어지는 배열에서 i~j까지의 부분 배열을 선택했을 때 (a[i]+a[i+1]+...+a[j])*(min(a[i],a[i+1]),....,a[j]) 가 최대가 되도록 i j를 선택하는 문제이다. 나이브한 풀이법으로는 i,j를 선택하는데만 O(N^2)으로 시간초과다 .. 따라서 좀 더 그리디하게 생각해보면 만약에 어떤 구간에 대해 정할 때 한 점 X를 기준으로 그 점이 최솟값이 되게 구간을 선택한다면 X를 기준으로 좌우로 최대한 X보다 큰값을 가지는 범위롤 포함하도록 배열을 선택할 수 있다. 이러한 아이디어에서 출발하여 모든 점에 대해서 이 범위를 볼건데 정렬을 해주어 작은 값부터 보면서 set에 업데이트해주어 이동가능한 lower_bound와 upper_bound를 찾아준다.. 더보기
BOJ)2872 우리집엔 도서관이 있어 문제: icpc.me/2872 책의 순서가 주어졌을 때 책을 정렬하는데 필요한 최소 이동횟수를 출력하는 문제이다. 책을 이동하는 조건은 무조건 하나의 책을 들어서 맨위에 쌓는 방법밖에 없기 때문에 가장 뒤에 있어야 하는 책은 옮길 필요가 없다. 가장 큰 숫자부터 연속 된 숫자가 얼마나 긴 부분 증가 수열을 이루고 있는지 확인하면 된다. 1234567891011121314#include #include using namespace std;int n, a[300030], here;int main() { scanf("%d", &n); for (int i = 0; i = 0; i--) if (a[i] == here)here--; printf("%d\n", here); return 0;}Colored by Col.. 더보기
BOJ)10272 현상금 사냥꾼 김정은 문제:icpc.me/10272 왼쪽 부터 오른쪽으로 순회한 뒤 순회하지 않은 정점들을 오른쪽에서 왼쪽으로 다시 순회할 때 이동거리의 최솟값을 구하는 문제이다. 이 문제는 바이토닉 투어 문제이므로 N^2 다이나믹 프로그래밍으로 해결할 수 있다. 우선 바이토닉 투어 문제는 dp[x][y]라는 테이블을 세울 수 있다. 이 때 x.는 갈 때 y는 올 때 까지 커버한 정점들의 수 이다. 점화식을 세울 때 현재 x,y까지 커버했다면 다음에 커버해야 할 정점은 당연히 max(x,y)+1이 되므로 이 정점을 갈 때 커버할 지 올 때 커버할지만 결정해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include #inc.. 더보기
BOJ)8462 배열의 힘 문제: icpc.me/8462 시퀀스와 쿼리가 주어질 때 매 쿼리에 대한 답을 출력하는 문제이다. 쿼리는 구간이 주어지면 구간에 존재하는 모든 자연수 s에 대하여 (s 의 개수의 제곱) x s를 합한 값이다. 쿼리와 시퀀스가 10만이기 때문에 적어도 쿼리를 log나 root 시간에 처리해주고 싶지만 안타깝게도 저 쿼리를 해당 시간에 처리하기는 힘든거 같다. 하지만 쿼리 도중에 업데이트가 일어나지 않기 때문에 쿼리를 정렬한 뒤 mo's 알고리즘으로 접근한다면 해답을 얻을 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include usin.. 더보기
BOJ)3172 현주와 윤주의 재미있는 단어 게임 문제:icpc.me/3172 어떤 단어가 x가 어떤 단어 y보다 사전순으로 앞서 있으면서 y를 뒤집은 y'이 x를 뒤집은 x'보다 앞서 있다면 두 단어는 서로 좋아하지 않는다고 한다. 단어가 10만개이기 때문에 brute force로 접근한다면 시간초과를 면치 못할 것이다. 그렇기 때문에 생각을 바꾸어서 기존의 문자열 기준으로 정렬을하여 번호를 매겨준 뒤 그 번호를 가진 상태로 문자열을 다 뒤집은 후 정렬을 해주고 앞에서 부터 보면 나보다 먼저 본 문자열 중에 나보다 할당 된 번호가 큰 문자열의 수를 세주면 된다. 이는 세그먼트 트리나 펜윅 트로로 효율적으로 해결할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839#in.. 더보기
BOJ)14675 단절점과 단절선 문제:icpc.me/14675 트리에서 단절선인지 단절점인지 여부를 판단하는 쿼리를 처리하는 문제이다. 단절선 단절점을 직접 구해줄 필요 없이, 트리이기 때문에 모든 선은 단절선이 된다. 트리에서 단절점 여부는 리프를 제외한 모든 노드는 단절점이 된다. 트리에서 리프판단 여부는 indegree의 개수를 세주면 된다. 1234567891011121314151617181920#include #include using namespace std;int n, m, x, y, c[100010];int main() { scanf("%d", &n); for (int i = 0; i 더보기
BOJ)14426 접두사 찾기 문제: icpc.me/14426 N개의 문자열로 이루어진 집합 S가 주어질 때 M개의 문자열 중에서 집합 S에 포함 된 문자열 중 하나 이상의 접두사인 문자열들의 수를 출력하는 문제이다. 문자열의 길이가 짧음을 이용하여 트라이를 사용하여 문제를 해결 할 수 있다. N개의 문자열을 모두 트라이에 삽입해준 뒤 문자열 X에 대해 검색을 한다고 가정하면 X가 끝날 때 까지 트라이에서 계속 탐색이 가능하면 true를 중간에 경로가 없다면 false 를 return하도록 구현해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include using namespace std;int n, m;ch.. 더보기

티스토리툴바