본문 바로가기

알고리즘 관련/BOJ

BOJ)1938 통나무 옮기기 문제: icpc.me/1938 BFS를 이용하여 답을 구해줄 수 있다. 구현이 상당히 귀찮다 ... 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include #include #include using namespace std;struct ele { int x, y, z; ele(int x, int y, int z) :x(x), y(y), z(z) {} ele() {}};int dx[] = { 1,-1,0,0,0 };int dy[].. 더보기
BOJ)1445 일요일 아침의 데이트 문제: icpc.me/1445 꽃을 통과하는 경우를 최소로 하고 싶고 꽃을 통과하는 경우의 최소가 여러경로가 존재할 때 꽃의 옆을 지나가는 경우를 최소로 하고 싶을 때 최단경로를 찾는 문제이다. 우선이 되는 꽃을 통과하는 경우에 나올 수 있는 최대 꽃의 수 2500보다 큰값을 곱해서 cost를 주고 꽃의 옆을 지나가는 경우를 1로 준 뒤 다익스트라를 돌린 후 곱한 값을 나눈 값과 나머지를 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #include #include using namespace std;int n,.. 더보기
BOJ)10256 돌연변이 문제: icpc.me/10256 N^3으로 만들 수 있는 모든 마커를 트라이에 넣어준 뒤 아호코라식을 통하여 몇개의 마커가 주어진 문자열에서 출연하는지 개수를 세주면 되는 문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293#include #include #include using namespace std;struct trie { trie *go[4]; trie *fail; int out; trie() { for (int i = 0;.. 더보기
BOJ)9250 문자열 집합 판별 문제: icpc.me/9250 n개의 문자열 집합 a와 m개의 문자열 집합 b가 있을 때 b의 원소들을 확인하면서 a의 문자열이 하나라도 부분문자열으로 존재하는지 여부를 출력하는 문제이다. 일대 다 패턴매칭인 아호코라식을 이용하여 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include #include #include using namespace std;struct trie { trie *go[26]; trie *fail; bool out; trie() .. 더보기
BOJ)1063 킹 문제: icpc.me/1063 조건에 맞게 시뮬레이션을 돌려주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include #include using namespace std;string mov[] = { "R","L","B","T","RT","LT","RB","LB" };string a;int dx[] = { 0,0,-1,1,1,1,-1,-1 };int dy[] = { 1,-1,0,0,1,-1,1,-1 };int n, kx, ky, sx, sy;int chk(int x, int y) { return 1 > n; ky = x[0] - 'A' + 1; kx =.. 더보기
BOJ)1514 자물쇠 문제: icpc.me/1514 비밀번호 A를 B로 바꾸기 위한 최소 돌림의 횟수를 구하는 문제이다. 동적 계획법을 통해 문제를 해결 할 수 있다. dp[pos][x][y][z][flag]=> pos번 째 자물쇠를 볼 때 x: pos번 자물쇠를 돌린 범위 y: pos+1번 자물쇠를 돌린 범위 z:pos+2번 자물쇠를 돌린 범위(flag는 자물쇠를 돌리는 방향성) 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include using namespace std;int n, a[110], b[110], dp[110][10][10][10][2];int modulo(int x) { while (x 더보기
BOJ)5721 사탕 줍기 대회 문제: icpc.me/5721 최대로 가져갈 수 있는 사탕의 수를 구하는 문제이다. 동적 계획법으로 문제를 해결 가능하다. dp[x][y][z] = x-1행 까지 모든 사탕상자와 x행의 y행 까지의 사탕상자를 커버했을 때 가질 수 있는 최대 사탕 개수(이 때 z는 x행에서 사탕상자를 한번이라도 커버했는 지 여부이다) 이렇게 정의를 해주면 dp[x][y][z]= max(a[x][y]+ dp[x][y+2][1], dp[x][y+1][z]) 라는 대략적인 점화식이 세워진다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include using namespace std;vecto.. 더보기
BOJ)11560 다항식 게임 문제: icpc.me/11560 문제를 풀기 위하여 k:0~20 에 대한 p(x)를 모두 구하여도 시간내에 충분히 수행가능하다. 따라서 미리 계산을 다 해준 뒤 쿼리를 받을 때 마다 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;typedef long long ll;vector b, a;ll x, y, z;int main() { for (int i = 3; i 더보기
BOJ)10276 Jewelry Exhibition 문제: icpc.me/10276 각 행이나 열에 빛을 발사해서 보석들을 지킬 때 모든 보석들을 지키는 최소한의 빛의 수를 구하는 문제이다. x행 y열의 위치에 존재하는 보석을 x정점과 y정점을 잇는 간선이라고 생각한다면 결국 모든 보석을 지키는건 각 행(정점)들을 몇개 선택하여 모든 간선을 커버하는 문제로 치환되므로 최소 버텍스 커버 문제로 볼 수 있다. 이분 그래프에서의 최소 버텍스 커버 문제는 쾨닉의 정리에 의해 이분 매칭으로 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include #include using namespace std;int t, n, m,.. 더보기
BOJ)1999 최대최소 문제: icpc.me/1999 n*n 행렬에 값이 주어져 있을 때 한 지점에서 부터 시작한 b*b 크기의 부분 행렬에서의 최댓값-최솟값을 출력하는 문제이다. 2차원 세그먼트 트리를 이용하면 O(K*NlogN)에 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include using namespace std;int n, b, k, minseg[251][250 * 4], maxseg[251][250 * 4], a[251][251];int minupdate(int *tree, int pos, int val, int node, int x,.. 더보기

티스토리툴바