본문 바로가기

알고리즘 관련/BOJ

BOJ)14288 내리 갈굼4 문제:icpc.me/14288 트리에서 질의를 처리하는 문제이다. 우선 dfs를 이용하여 트리의 번호를 reordering 시켜주어 트리를 구간으로 생각해보자. 문제를 풀기 위해서 일반의 경우와 야자의 경우에 업데이트 시켜주는 영역을 다르게 생각해보자 일반의 경우만 생각해본다면 value가 아래로 전파되기 때문에 나의 자식들의 구간에 업데이트 시켜준 뒤, 답을 가져올 때는 해당 지점의 값을 출력하면 될것이다. 야자의 경우에는 value가 위로 전파되므로 나의 위치에 업데이트 시킨 뒤, 답을 가져올 때, 내 자식들의 업데이트 현황을 다 더해주면 되므로, 자식들의 구간의 합을 출력하면 될것이다. 두가지 모두 Fenwick tree를 이용하여 구현 가능하므로 2개의 fenwick tree를 구현하면 문제를 해.. 더보기
BOJ)14400 편의점2 문제: icpc.me/14400 고객들의 좌표가 주어 질 때 고객들과의 맨하탄 거리의 합의 최솟값을 구하는 문제이다. 문제를 함수로 표현하면 |x-a1|+|y-b1|+|x-a2|+|y-b2|+|x-a3|+|y-b3|+..... 꼴의 최솟값을 구하는 문제가 되는데, 여기서 x의 절댓값 함수들과 y의 절댓값 함수들을 독립 시켜서 보면 |x-a1|+|x-a2|+...|x-an|의 그래프는 한개의 극값(최솟값)을 가지는 unimodal 함수가 됨을 알 수 있다. 따라서 ternary search를 이용하여 문제를 해결 할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include .. 더보기
BOJ)15745 Snow Boots 문제: icpc.me/15745 1~N 영역에 쌓인 눈의 높이가 주어진다. 이제 B개의 신발에 대한 쿼리가 들어오는데 각 쿼리는 Si와 Di를 가진다. Si는 해당 신발을 신고 걸을 수 있는 최대 눈의 높이이고, Di는 한번에 최대로 걸을 수 있는 거리이다. i번 째 신발을 신었을 때 1에서 부터 N까지 갈 수 있는 지 여부를 매 쿼리마다 출력해주면 되는 문제이다. 풀이법은 여러가지가 있는것 같지만 내가 푼 풀이는 오프라인 쿼리 풀이이다. 우선 쿼리를 Si기준으로 역순으로 정렬을 해준 뒤 순서대로 봐준다. 쿼리를 역순으로 본다면, 쿼리를 보면서 점점 못넘는 영역이 늘어날 것이다. 현재 쿼리를 처리할 때 넘을 수 있는 기준은 현재 못넘는 영역중에서 가장 긴 영역이 되므로 역순으로 쿼리를 처리하면서, 못넘는.. 더보기
BOJ)13274 수열 문제: icpc.me/13274 정렬 된 수열에서 쿼리를 처리하는 문제이다. 쿼리 l r x 는 l~r 구간의 원소에 x를 더해준 뒤 다시 정렬하는 쿼리이다. n이 10만이고 쿼리가 1000개 인데 매번 퀵소트를 실행해주면 1억xlog10만 이므로 1초의 제한 시간에 간당간당한 느낌이다. 따라서 좀 더 빠른 소팅 방법이 필요한데, 정렬 된 구간에서 l~r에 x를 더하게 되면, l~r의 구간은 오름차순을 유지할 것이며, 전체의 구간에서 l~r의 구간을 제외한 구간 역시 오름차순을 유지할 것이다. 이렇게 정렬 된 두 구간에서 서로 가장 앞 원소를 비교하며 insertion sort를 하면 소팅을 O(N)의 시간에 해결할 수 있다. 1234567891011121314151617181920212223242526.. 더보기
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) 라는 식이 세워지고 이를.. 더보기

티스토리툴바