본문 바로가기

알고리즘 관련

BOJ)5397 키로거 문제:icpc.me/5397 메모장에 커서의 입력하는 단어와 커서의 움직임과 누른 백스페이스가 기록될 때 최종적으로 남는 단어를 출력하는 문제이다. 중간에 삽입 삭제가 가능한 링크드리스트를 구현하여 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include #include using namespace std;struct Node { char data; Node *prev, *next; Node() :data('\0'), pr.. 더보기
BOJ)2075 N번째 큰 수 문제:icpc.me/2075 N^2개의 수가 들어올 때 N번째로 큰 수를 구하는 문제이다. N이 최대 1500 밖에 안들어오므로 단순히 값을 다 받아서 정렬해주는 N^2logN의 해법으로 해결할 수 있다. 하지만 메모리제한이 10MB이므로 힙을 이용하여 수를 받을 때 마다 큰 수 N개만큼만 저장해주고 그 수들중 가장 작은 수와 들어오는 수를 비교를하여 힙을 관리해주면 된다. 123456789101112131415161718192021222324#include #include #include using namespace std;int n, x;priority_queue pq;int main() { scanf("%d", &n); for (int i = 0; i 더보기
BOJ)1326 폴짝폴짝 문제: icpc.me/1326 각 징검다리에 숫자가 써있고 해당 징검다리에서는 숫자의 배수만큼 떨어져 있는 징검다리까지 점프 할 수 있을때 a에서 b까지 의 최단거리를 출력하는 문제이다. 해당 징검다리에서 갈 수 있는 모든 징검다리까지 cost가 1인 간선을 연결해주고 다익스트라를 이용하여 최단거리를 구해줄 수 있다. 이 때 주의할 점은 배수 이기 때문에 나보다 작은 지점으로도 점프할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include #include using namespace std;int n, a[10001], s, e, dp[10001];vector vt;in.. 더보기
BOJ)13166 범죄 파티 문제: icpc.me/13166 범죄자 N명과 친구 2*N명의 친구 관계와 임계점이 주어질 때 모든 범죄자가 친구랑 매칭 될 수 있는 파티 비용의 최솟값을 구하는 문제이다. 파티 비용의 최솟값을 파라메트릭 서치로 탐색할건데 이 때 탐색 기준은 mid를 파티 비용으로 정했을 때 모든 범죄자가 친구들과 매칭 되야 하므로 범죄자와 친구의 이분 매칭이 N이 됨을 기준으로 한다. 단, 정점의 개수가 20만이나 되므로 일반 이분매칭 소스로는 TLE를 보게되니 호프크로프트 카프 알고리즘을 이용하여 구해줘야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162.. 더보기
BOJ)3736 System Engineer 문제: icpc.me/3736 작업 세트와 서버로 이루어진 이분 그래프에서 최대 매칭을 구하는 문제이다. 정점의 개수가 10000개 이므로 일반 이분 매칭 소스로는 TLE가 나므로 hopcroft-karp 알고리즘을 이용하여 최대매칭을 구해줘야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include #include #include #include #define INF 987654321using namespace std;struct hopcroft_karp { in.. 더보기
BOJ)2660 회장뽑기 문제:icpc.me/2660 두 사람의 친구 관계가 주어질 때 어떤 사람이 가장 먼 친구 관계가 n다리 걸쳐서 친구관계가 된다면 그 사람의 점수는 n점이라 할 때 최소 점수를 갖는 사람들이 회장 후보가 된다. 회장 후보를 출력하는 문제이다. 두사람의 친구 관계를 cost가 1인 간선으로 표현한다면 플로이드 워셜을 통하여 n:n 최단거리를 구해주면 두 사람의 친구 관계가 몇다리 걸쳐있는지 알 수있다. 이를 이용하여 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;int n, x, y, a[51][51], r, b[51];int main().. 더보기
BOJ)1755 숫자놀이 문제: icpc.me/1755 m과 n 이 주어질 때 m부터 n까지의 사이의 수들을 숫자 하나당 영어로 표현하였을 때 정렬된 순서대로 숫자를 출력하면 된다. map을 이용하여 string 정렬해주면 해결해줄 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #include #include #include using namespace std;map res;map cvt;int m, n, c;int main() { scanf("%d%d", &m, &n); cvt[0] = "zero "; cvt[1] = "one "; cvt[2] = "two "; cvt[3] = "three "; c.. 더보기
BOJ)1747 소수&팰린드롬 문제:icpc.me/1747 N보다 큰 수 중에서 소수이면서 팰린드롬인 가장 작은 수를 구하는 문제이다. 에라토스테네스의 체를 이용하여 소수들을 구해놓은 뒤 N보다 큰 수 중에서 팰린드롬인지 검사해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include using namespace std;bool p[2000001];int n;bool ck(int *a, int lo, int hi) { if (lo >= hi)return 1; if (a[lo] != a[hi])return 0; return ck(a, lo + 1, hi - 1);}bool chk(int x) { int c = -1; int a[8]; wh.. 더보기
BOJ)10835 카드게임 문제: icpc.me/10835 오른쪽 카드를 버릴 때 점수를 얻을 수 있을 때 얻을 수 있는 최고 점수를 구하는 문제이다, dp[x][y] b[y]) dp[x][y]=max(dp[x][y],dp[x][y+1]+b[y]) 라는 점화식을 통하여 문제를 해결할 수 있다. 12345678910111213141516171819202122232425#include #include #include #define INF 987654321using namespace std;int dp[2001][2001], n, a[2001], b[2001];int func(int x, int y) { if (x == n || y == n)return 0; int &ret = dp[x][y]; if (ret != -1)return r.. 더보기
BOJ)7535 A Bug's Life 문제: icpc.me/7535 서로 성별이 다른 두 벌레들의 정보가 주어질 때 vaild한지 여부를 묻는 문제이다. 우리는 두 벌레들의 정보가 들어온다는 걸 이용하여 2-SAT 모델링을 통하여 문제를 해결 할 수 있다. A와 B가 들어 왔을 때 두 벌레의 성별이 다르다는 걸 (A||B)&&(!A||!B)로 표현해준 뒤 이를 이용하여 2-SAT 모델링을 한 뒤 vaild 여부를 판단해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #include #include #include #include .. 더보기

티스토리툴바