2018/06 썸네일형 리스트형 BOJ)15589 Lifeguards (Silver) 문제: icpc.me/15589 n명의 인원이 1차원 구간을 커버하는 데 이중에서 한 인원을 제외했을 때 커버가능한 최대 구간을 출력하는 문제이다. 전체 구간에서 하나를 제외 하였을 때 최대 구간을 구하면 되므로 하나의 구간에서 다른 구간에 영향을 받지 않고 유일하게 커버되는 구간 중 최솟값을 구하여 전체 구간에서 빼주면 답이 된다. 각각의 구간에서 독립적으로 커버하는 구간은 왼쪽에서 부터, 오른쪽에서 부터 , 두번 스위핑하여 구할 수 있다. 자세한 설명은 소스코드로 대신하겠다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include using namespace s.. 더보기 BOJ)14965 Lozinke 문제: icpc.me/14965 n개의 문자열이 주어질 때, 모든 문자열 s에 대해, s의 substring 중에 현재 보는 문자열을 제외한 나머지 문자열이 되는 개수를 전부합하여 출력하는 문제이다. 직접 비교하면 n^2으로 시간초과를 보게된다. 문자열의 길이가 10이하라는 사실을 이용하여 모든 문자열 s를 해싱해준 뒤 마찬가지로 모든 문자열의 substring을 전부 해싱하여 set과 map을 이용하여 개수를 계산해주면 n*10*10*logn의 시간에 문제를 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #in.. 더보기 BOJ)11964 Fruit Feast 문제: icpc.me/11964 최대 포만감의 최대치가 t이고, 오렌지를 먹으면 a만큼 레몬을 먹으면 b만큼 포만감이 오를 때, 최대 포만감을 구하는 문제이다. 단, 조건이 하나 있는데 딱 한번 물을 마시면 현재 포만감을 반으로 줄일 수 있다. 현재 물을 마셨는 지 아닌지를 제약조건으로 둔다면 다이나믹 프로그래밍으로 문제를 해결할 수 있다. dp[i][j]= 포만감이 i이고 제약조건(물을 마셨는 지 여부)이 j일 때 상태의 존재 여부 12345678910111213141516171819202122232425#include #include #include using namespace std;int dp[5000005][2];int t,a,b,r;int main(){ scanf("%d%d%d",&t,&a,&.. 더보기 BOJ)11046 팰린드롬?? 문제: icpc.me/11046 길이가 최대 100만인 문자열 s가 주어질 때 s의 인덱스 l~r 까지의 부분 문자열이 팰린드롬인지 쿼리마다 출력하는 문제이다. n이 작다면 n^2의 방법으로 해결해줄 수 있지만 n이 크므로 manacher's 알고리즘을 이용하여 해결해주어야 한다. manacher's 알고리즘으로 전처리를 해준 뒤 중심으로 부터의 최대 팰린드롬 길이와 주어진 구간의 길이를 비교해주어 답을 출력해주면 된다. 시간 복잡도는 O(N+M)이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include #include #include #include using.. 더보기 BOJ)1222 홍준 프로그래밍 대회 문제: icpc.me/1222 문제를 해석하면 만약 홍준이가 팀원의 수를 k명이라 정했다면 학교 사람의 수가 k로 나누어 떨어지는 학교만 참가할 수 있다. 즉 주어진 수들을 전부 소인수 분해를 하였을 때 i를 소인수로 가진 학교의 개수를 a[i]라고 하면, a[i]가 2이상인 경우에서의 i*a[i]의 최댓값이 답이 된다. 하지만 모든 수의 소인수를 구할 경우 O(N*sqrt(N))으로 시간내에 들어오기에는 조금 무리가 있다. 하지만 수를 받으면서 소인수를 계속 연산하는 방법이 아닌 수를 전부 받아놓고 하나의 수에는 한번의 계산만 하는 방법으로 최적화 시켜 시간내에 통과시킬 수 있다. 이보다 좋은 방법은 모든 수 i에 대하여 자신을 소인수로 가지는 수를 직접 계산해주는 방법이다. 이 방법은 소스코드로 설명.. 더보기 BOJ)15675 괴도 강산 문제 :icpc.me/15675 모든 보석을 집고, 위치 추적기를 하나도 안 가진 상태가 가능하다면 1을 아니면 0을 출력하는 문제이다. 문제의 조건을 잘 읽어보면 2NF로 모델링이 가능하여 2-SAT을 이용한 풀이가 가능하다. 우선 보석을 고르는 조건은, 보석이 존재하는 행을 a 열을 b라고 하였을 때, a b 중에 하나밖에 선택되지 않으므로 (a&&!b)||(!a&&b) 라는 식이 세워진다. 하지만 이는 CNF가 아니므로 식을 잘 풀어내어 (a||b)&&(!a||!b)로 변형하여 추가해준다. 다음으로 위치추적기를 밟는 경우 다시 그자리에 돌려놔야 하므로 a b 를 모두 선택하거나 a b를 모두 선택하지 않는 경우 중 한 경우가 이루어져야 한다. 즉(a&&b)||(!a&&!b) 라는 식이 세워지고 이를.. 더보기 advanced disjoint set 오늘은 disjoint set에 대해서 글을 적어보겠습니다. 직역하면 상호배타적 집합이며, union-find 라는 자료구조로 표현됩니다. [disjoint set, DSU(disjoint union),union find] 는 전부 union find 자료구조를 칭하는 말입니다. union find 는 union연산과 find연산을 매우 빠르게 해주는 자료구조로서, 상호배타 집합에서는 어떠한 집합에서도 공통 된 원소가 존재하지 않으며, 동시에 모든 집합의 합집합은 전체집합이 됩니다. 이해를 돕기 위하여 특수한 상황을 가정해보겠습니다. a라는 나라와 b라는 나라가 동맹이고, b라는 나라와 c라는 나라가 동맹을 맺게된다면 a와 c나라도 자동으로 동맹이 되는 경우를 생각해봅시다. 해당 경우로 각각의 나라의 동.. 더보기 BOJ)13016 내 왼손에는 흑염룡이 잠들어 있다 문제: icpc.me/13016 오랜만에 문제 포스팅을 한다. 문제를 요약하면 한 정점 v에서 다른 정점으로의 최단거리를 dist[i] (i: 1~n) 이라고 했을 때, dist[i]의 최댓값을 모든 정점 v에 대해 구하는 문제이다. 물론 한 정점에서 dist[i]의 최댓값을 구하는건 dfs를 수행하여 쉽게 해결할 수 있지만 모든 정점에 대해 구하게 될 경우 정점의 개수가 5만이므로 시간초과를 보게 될 것이다. 하지만 조금 생각해보면 한 정점에서의 부터 다른 정점으로 부터의 최단 거리 중 최댓값은 트리의 지름의 양 끝 단말 노드 중 하나로의 거리라는 것을 알 수 있다.(만약 트리 지름의 단말 노드가 아닌 다른 리프로 부터의 거리가 최댓값이라면, 트리의 지름보다 긴 거리가 생긴다는 뜻이므로 모순이된다.) .. 더보기 SCPC 2018 이벤트 당첨! 살면서 이런 이벤트와는 인연이 없다고 생각했는데 어제 갑자기 문자가 왔다. 커피 당첨됬다고 ㅋㅋㅋ 올해 SCPC는 본선에 나갈 수 없겠지만(7월 입사 ㅠㅠ... 게다가 일본 여행 날짜와 2차 예선 날짜가 겹친다 ...) 커피라도 받게되서 기분이 좋다 더보기 이전 1 다음
