본문 바로가기

알고리즘 관련

BOJ)3770 대한민국 문제:icpc.me/3770 동해안과 서해안을 잇는 고속도로의 셋이 주어질 때 교차점의 수를 구하는 문제이다. 모든 고속도로를 받아서 동해안의 순서로 오름차순 정렬을 해준 뒤 동해안의 순서로 보면서 현재 보고 있는 고속도로보다 전에 봤던 고속도로 중 현재 고속도로보다 서해안이 큰 고속도로들의 수를 구해주면 된다. 이를 효과적으로 계산하기 위하여 세그먼트 트리를 사용해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #include using namespace std;int t, n, m, k, x, y, seg[10000];long long r;int update(in.. 더보기
BOJ)6091 핑크 플로이드 문제: icpc.me/6091 플로이드 워셜로 구해진 최단거리의 셋이 주어질 때 원래의 트리에 연결 된 간선만 출력하는 문제이다. 우리는 주어진 최단거리의 셋중에서 가장 작은 간선부터 그리디하게 선택할 수 있다. 근데 이 때 선택하면 안되는 간선을 트리의 성질을 이용하여 알 수 있다. 트리에서 a에서 b로 가는 경로는 유일해야 하므로 내가 현재 보고 있는 간선에 연결 된 양쪽 두 정점이 이미 하나의 컴포넌트를 이루고 있다면 그 간선은 사용하면 안된다. 따라서 우리는 가장 작은 간선부터 연결해 주되 disjoint-set을 이용하여 두 컴포넌트를 연결시켜주어 해당 간선이 컴포넌트를 이루는지 여부를 판단한다. 1234567891011121314151617181920212223242526272829303132.. 더보기
BOJ)1826 연료 채우기 문제:icpc.me/1826 1km를 가는데 1L의 연료가 필요하고 현재 가진 연료량과 목적지까지의 거리 그리고 각 주유소의 정보가 주어질 때 충전횟수를 최소화하여 목적지에 도착하는 충전횟수를 출력하는 문제이다. 우선 주유소의 정보를 받아 거리를 기준으로 sort한 뒤 내가 현재 갈 수 있는 거리보다 가까운 거리에 있는 모든 주유소의 정보를 받아와 채울 수 있는 연료량을 heap에 저장한다. 이후 그리디하게 갈 수 있는 주유소중 가장 큰 연료량을 가지는 주유소를 선택해나가면 문제를 해결 할 수 있다. 123456789101112131415161718192021222324252627#include #include #include using namespace std;priority_queue pq;int n.. 더보기
BOJ)2056 작업 문제: icpc.me/2056 a번 작업을 실행할 때 선행되야 되는 작업 b의 셋이 주어질 때 모든 작업을 완료하는데 걸리는 시간을 출력하는 문제이다. 문제에서 선행관계는 항상 번호가 증가하는 순서로 이루어진다고 하였으므로 사이클이 존재하지 않는 DAG임을 알 수 있다. 따라서 우리는 위상정렬을 해준 뒤 위상정렬의 순서대로 일을 처리해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #include using namespace std;int n, in[10002], c[10002], x, y, r;vector vt;int main() { scanf("%d", &n); vt.re.. 더보기
BOJ)7579 앱 문제: icpc.me/7579 최소한의 비용을 사용하여 m만큼의 메모리를 얻을 때 비용을 출력하는 문제이다. dp[pos][cost]= pos번째 앱까지 cost만큼의 비용을 사용해 얻을 수 있는 메모리의 최댓값으로 정의 한 뒤 파라메트릭 서치를 이용하여 cost값을 조정해주면 된다. 12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std;int n, cost, m[101], c[101], dp[101][10001];int func(int pos, int cos) { if (pos = 0) ret = max(ret, func(pos - 1, cos - c[pos]) + m.. 더보기
BOJ)2157 여행 문제: icpc.me/2157 번호가 증가하는 순서대로만 여행을 할 때 1번 도시에서 N번 도시까지 항공편을 K번 이하로만 이용하여 갈 때 얻을 수 있는 기내식 점수의 최댓값을 구하는 문제다. dp[pos][val]= pos번 나라까지 여행하고 항공편을 val번 이용했을 때 얻을 수 있는 최대 기내식 점수 로 정의 한 뒤 문제를 해결하면 된다. 소스코드는 탑 다운 방식으로 구현하여 테이블의 정의가 반대다. 123456789101112131415161718192021222324252627#include #include #include #define INF 987654321using namespace std;int a[301][301], n, m, k, dp[301][301], x, y, z;int func.. 더보기
BOJ)2618 경찰차 문제:icpc.me/2618 경찰차 두대가 사건을 순서대로 처리할 때 가장 적은 거리를 이동하도록 사건을 배치하는 경우와 거리를 출력하는 문제이다. dp[x][y] = 경찰차 1이 x번째 사건을 경찰차 2가 y번째 사건을 마지막으로 처리하였을 때 이동한 거리의 합의 최솟값으로 정의한 뒤 문제를 해결해주면 된다. 점화식은 dp[x][y] = min(dp[prev][y]+ dist(prev,x) , dp[x][prev] + dist(prev,y))이다. 소스에서는 바텀업 방식으로 구현하여 테이블의 정의가 약간 바뀌었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#in.. 더보기
BOJ)2688 줄어들지 않아 문제: icpc.me/2688 N자리 줄어들지 않는 숫자를 구하는 문제이다. dp테이블을 dp[pos][val]을 val로 끝나는 pos자리 줄어들지 않는 숫자의 수로 정의한 뒤 다이나믹 프로그래밍을 통하여 해결할 수 있다. long long을 사용하지 않는다면 overflow가 발생할 수 있다. 12345678910111213141516171819202122232425262728#include #include #include using namespace std;typedef long long ll;ll t, dp[100][10], n;ll func(ll pos,ll val) { if (val 9)return 0; if (pos == 1)return 1; ll &ret = dp[pos][val]; if .. 더보기
BOJ)2230 수 고르기 문제: icpc.me/2230 N개의 원소로 이루어진 수열에서 두 수를 뽑았을 때 그 수의 차이가 M보다 크면서 가장 작은 두 수의 차이를 구하는 문제이다. 우리는 정렬을 해준 뒤 투 포인터 i , j 를 설정하여 문제를 해결할 수 있다. a[i]-a[j]가 m보다 작다면 두 수의 차이가 더 커져야 하므로 i를 증가시키고 m보다 크거나 같다면 j를 증가시키는 방법으로 해결해나가면 된다. 1234567891011121314151617181920212223#include #include #define INF 1987654321using namespace std;int n, m, a[100001], r;int main() { scanf("%d%d", &n, &m); for (int i = 0; i 더보기
BOJ)9463 순열 그래프 문제:icpc.me/9463 두 순열이 주어질 때 같은 번호끼리 연결할 때 생기는 교점의 수를 구하는 문제이다. 우선 첫번째 순열의 순서를 기준으로 새로운 순열 A를 생성한다. 그리고 두번째 순열의 각 번호를 순열 A에 대입한 순열 B를 생성한다. 이제 순열 B에서 현재 보고있는 i보다 오른쪽에 있고 i로 인하여 만들어지는 교점의 수는 B[i]-1-(1~B[i]까지 이미 지나간 수들의 수)로 계산 가능하다. 1~B[i]까지 이미 지나간 수들의 수는 세그먼트 트리를 이용하여 관리할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include using namespace std;i.. 더보기

티스토리툴바