본문 바로가기

알고리즘 관련

BOJ)8983 사냥꾼 문제: icpc.me/8983 KOI 2013 중,고등부 문제이다. N마리의 동물들의 위치가 좌표로 주어지고 x축위에 M개의 사대가 존재하는데 이때 모든 사대의 사정거리는 공통적으로 L이다. 각 사대에서 동물들과의 거리는 [abs(x(동물)-x(사로))+y(동물)] 로 계산될 때 사냥 가능한 동물의 수를 출력하는 문제이다. N과 M이 최대 10만까지 그리고 사정거리와 좌표는 1~ 1억까지 들어온다. 우리는 모든 사대와 각 동물들을 비교할 경우 O(N*M)의 시간 복잡도로 TLE를 보게 된다는 걸 알고 있다. 따라서 최대 NlogN의 알고리즘이 필요하다. 우리는 우선 동물들을 x좌표 기준으로 정렬 ,그리고 사대도 x좌표 기준으로 정렬을 할 것이다. 그 다음 동물들을 볼건데 어떤 동물 A를 사냥 가능한 사대.. 더보기
BOJ)10277 JuQueen 문제: icpc.me/10277 C개의 코어가 있을 때 쿼리를 받아 3종류의 연산을 처리해주면 되는 문제이다. 단 코어의 하한선은 0이고 상한선은 N으로 입력으로 주어진다. 쿼리는 다음과 같다 change X S 코어X를 S만큼 증가시켜라groupchange A B S 코어 A부터 코어B까지 전부 S만큼 증가시켜라state X 코어X의 값을 출력하라 단, 코어를 증가시키다가 상한이나 하한에 다다를시 증가를 멈춘다. change나 groupchange 같은 경우 증가혹은 감소시킨 계수를 출력해야 하는데 우리는 코어를 증가시키다 상한이나 하한에 도달하는 경우를 판단해야한다. 따라서 우리는 구간에 대한 최댓값 최솟값을 세그먼트 트리로 관리하여 구간을 증가 시킬 시 상한혹은 하한에 도달하는지 여부를 판단하여 상.. 더보기
BOJ)2877 4와 7 문제:icpc.me/2877 4와 7로만 이루어진 수 중에서 K번째로 작은 수를 출력하는 문제이다. 각 숫자가 4와 7로만 이루어졌기 때문에 우리는 N의 자리 수는 2^N개 밖에 존재하지 않는다는걸 알 수 있다. 이를 이용하여 K번째로 작은 수가 L자리수라는 걸 알 수 있다. 이후 L자리에서 V번째로 작은 수는 결국 이진수로 생각하면 비트가 1인 수는 '7' 비트가 0인 수는 '4'가 된다. 따라서 V의 각 비트를 조사하여 답을 출력해주면 된다. 12345678910111213141516171819202122232425#include #include using namespace std;int k, a[31], l;int main() { for (int i = 0; i 더보기
BOJ)2775 부녀회장이 될테야 문제: icpc.me/2775 a층 b호에 사는 주민은 a-1층의 1~b호까지의 주민의 합일때 k층n호에 사는 주민의 수를 출력하는 문제이다. 사실 k와 n의 범위가 매우 작기 때문에 그때 그때 구해줘도 TLE를 받을일은 없을것 같지만 우리는 배운 사람들이니까 다이나믹 프로그래밍을 통하여 쉽게 답을 구 할수 있다. 점화식은 dp[i][j]=dp[i-1][j]+dp[i][j-1] 이다. 12345678910111213141516171819#include #include using namespace std;int dp[15][15], t, k, n;int main() { for (int i = 1; i 더보기
BOJ)5480 전함 문제: icpc.me/5480 각 레이저가 파괴하는 전함의 무게의 최댓값을 출력하는 문제이다. 우리는 우선 쿼리를 전부 받아 오프라인으로 문제를 풀어볼거다. 일단 x좌표와 y좌표가 10억까지들어올수 있기 때문에 전함과 레이저의 x,y좌표를 모두 받아 각각 좌표압축 해준다. 이후 우리는 x와 y에 대한 세그먼트트리를 각각 생성하여 세그먼트 트리에 레이저의 인덱스의 최솟값을 저장할 것이다. 수직인 레이저는 x세그먼트 트리에 수평인 레이저는 y세그먼트 트리에 레이저의 인덱스를 해당 좌표에 최솟값 업데이트 시켜주면 된다. 이후 전함마다 각각 x,y세그트리에서 최솟값인 인덱스를 받는다 가장 작은 인덱스가 의미하는건 결국 그 전함을 파괴하는 레이저라고 보면 된다. 해당 레이저에 전함의 무게를 최댓값으로 업데이트 시.. 더보기
BOJ)10167 금광 문제: icpc.me/10167 직사각형 모양의 영역으로 금광을 개발 할 때 얻을 수 있는 최대 이익을 구하는 문제이다. 문제를 푸는데 상당히 고생했는데 KOI 2014 중등부 문제인걸 보고 어이가없어서 웃음만 나왔다... 일단 N이 3000이므로 N^2혹은 N^2logN 알고리즘을 사용해야 하는데 처음 생각한것은 x축기준으로 스위핑 하여 y축을 세그먼트 트리 구간합에 업데이트 시키는 작업을 순서대로 하는데이 때 이 작업은 전단계의 점들을 반드시 포함하게 되므로 모든점에 대해서 이 작업을 반복하는 것이다. 이 때 처음에는 최대 구간합을 구하기 위해서 이미 업데이트 된 모든 점이랑 비교하여 구간합의 최댓값을 구했는데 이렇게 할 경우 한점에서 업데이트한 후 구간합의 최댓값을 구하는데 O(NlogN) 여기에 .. 더보기
BOJ)9184 신나는 함수 실행 문제: icpc.me/9184 문제에서 점화식 기저 까지 다 정해주는 진정한 꿀문제가 아닐까 싶다. 당연하게도 그냥 함수를 매번 계산한다면 시간초과가 난다. 하지만 우리는 점화식과 기저를 알고 있으니 이걸 이용해 다이나믹 프로그래밍을 이용하여 계산할때마다 결과를 배열에 저장해주면 된다. 문제에서 하라는대로 하면 쉽게 풀 수 있는 문제이다. 1234567891011121314151617181920212223242526#include #include #include using namespace std;int dp[21][21][21];int a, b, c;int func(int x, int y, int z) { if (x 20) return func(20, 20, 20); int &ret = dp[x][y].. 더보기
BOJ)1049 기타줄 문제: icpc.me/1049 N개의 기타 줄을 새로 교체하려고 할때 6개로 사는 묶음 가격과 낱개로 구매하는 가격이 M번 주어진다. 이때 기타 줄을 교체하는데 사용되는 최소비용을 구하는 문제이다. 우리는 당연히 들어오는 M개의 입력중에 최솟값만 처리해주면 된다. 그리고 각 최소 가격에 대해서 6개 묶음의 가격을 A 낱개의 가격을 B라고 할때 A>6*B 라면 무조건 낱개로 구매해주면 되고 아닌경우에는 (N/6)*A+(N%6)*B를 출력해주면 된다. 라고 생각할 수 있겠지만 안타깝게도 6개 미만인 낱개를 살 때 낱개로 1~5개 보다 6개짜리 묶음을 사는게 더 싼 케이스가 들어온다. 따로 예외 처리해주면 된다. 123456789101112131415161718192021#include #include #de.. 더보기
BOJ)2022 사다리 문제: icpc.me/2022 극혐스러운 수학문제이다. 사실 그렇게 어려운 수식은 아니고 직선의 방정식 두개를 구하여 두 교점의 y좌표인 c를 알고 있으니 이때 구해야하는 밑면 m을 이분 탐색을 통하여 찾아 나가는 문제이다. 밑면m이 클수록 c는 낮아지므로 함수로 구한 값이 c보다 크다면 lo를 mid로 c보다 작다면 hi를 mid로 잡아주면 된다. 사실 이터레이터를 얼마나 돌려야되는지 감이 안와서 제출하면서 조절했는데 너무 많이 돌리면 TLE를 보게되고 너무 적게 돌리면 오차때문에 WA를 보게된다. 123456789101112131415161718192021222324252627#include #include using namespace std;double x, y, c, lo, hi;double fx.. 더보기
BOJ)2252 줄 세우기 문제: icpc.me/2252 N명이 학생이 주어지고 두 학생의 키를 비교한 M개의 정보가 주어질 때 줄을 세운 결과를 출력하는 문제이다. 우리는 두 학생의 우선관계를 방향 그래프를 이용하여 설정해준 뒤 topology를 구해주면 된다. 즉 DFS를 돌리면서 먼저 끝나는 순서대로 스택에 저장해준 뒤 하나씩 뽑으면서 출력해주면 답을 얻을 수 있다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include #include #define MAX_N 32000using namespace std;vector vt;stack st;int n, m, x, y, visited[MAX_N + 1];void dfs(int .. 더보기

티스토리툴바