본문 바로가기

알고리즘 관련/BOJ

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.. 더보기
BOJ)2992 크면서 작은 수 문제:icpc.me/2992 등장하는 수로 조합가능 한 모든 수를 비교하여 그 중 최솟값을 구해주면 된다. 시간 복잡도는 O(6!)이다. 12345678910111213141516171819202122232425#include #include #include #include #define INF 987654321using namespace std;char a[7];int r = INF;int main() { scanf("%s", &a); int v = stoi(a); vector vt; for (int i = 0; a[i] != '\0'; i++) vt.push_back(a[i]); sort(vt.begin(), vt.end()); do { for (int i = 0; i 더보기
BOJ)1058 친구 문제: icpc.me/1058 2-친구수가 가장 많은 사람의 2-친구 수를 구하는 문제이다. 2-친구의 수는 플로이드 워셜을 통하여 구한 최단거리가 2이하인 모든 정점들의 합으로 구할 수 있다. 12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std;int n, a[51][51], r;char b;int main() { scanf("%d", &n); memset(a, 0x3f, sizeof(a)); for (int i = 1; i 더보기
BOJ)12100 2048 (Easy) 문제:icpc.me/12100 2048 게임에서 가능한 5번의 움직임 이내에 나올 수 있는 가장 큰 블럭을 출력하는 문제이다. 하나의 상태에서 가능한 움직임은 4방향이고 N*N의 모든 블럭이 움직여야 하므로 하나의 상태에서 4방향으로 움직일 때 연산 횟수는 4*N*N이다. 5번 움직일 때 나올 수 있는 모든 횟수는 4^5이므로 모든 경우를 전부 구했을 때 시간 복잡도는 (1024*N^2*4)이므로 완전 탐색으로 해결 가능하다. 이 때 주의해야 할 점은 한번의 움직임에서 이미 합쳐진 블럭은 다시 안합쳐지므로 visited배열을 관리해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950.. 더보기

티스토리툴바