본문 바로가기

알고리즘 관련/BOJ

BOJ)1562 계단 수 문제: icpc.me/1562 N자리 계단수의 개수를 구하는 문제이다. 단 조건이 추가됬는데 0~9까지 모든 수가 등장했는지 확인을 해줘야 하기 때문에 비트마스킹을 통하여 상태를 체크해주면 된다. dp테이블의 정의는 dp[pos][val][state] 일때 pos자리 수이고 val번째 수로 시작하는 state(켜진 비트에 따라 i번째 자리수가 사용됬는지)의 경우의 수이다. 점화식은 dp[pos][val][state]=dp[pos-1][val+1][state|(1 더보기
BOJ)14433 한조 대기 중 문제: icpc.me/14433 A팀과 B팀에 각각 N,M의 유저가 원하는 트롤픽의 목록이 주어질 때 트롤픽을 최대로 선택하여 어떤 팀이 이기게 될지 알아보는 문제이다. A팀의 그래프와 B팀의 그래프를 각각 이분매칭에서의 최대매칭을 구해준 뒤 비교해서 답을 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include #include using namespace std;int n, m, check[5000], backmatch[5000], k1, k2, x, y, r, a;vector vt;vector wt;bool dfs(int here, const.. 더보기
BOJ)14431 소수마을 문제: icpc.me/14431 마을의 좌표가 주어질 때 두 좌표사이의 거리의 정수부분이 소수일 경우에만 이동가능한다는 조건하에 소수마을에서 A마을로 이동하는데 걸리는 최단경로를 구하는 문제이다. 에라토스테네스의 체를 이용하여 소수들을 구해준 후 거리가 소수인 정점들을 서로 간선 연결을 해준 뒤 다익스트라를 돌려서 해결하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include #include #include #include #include using namespace std;int getdist(pair a, pair b) { return sqrt((a.fir.. 더보기
BOJ) 10282 Failing Components 문제: icpc.me/10282 그래프가 주어지고 실패되는 A정점이 주어질 때 A정점에게 의존되는 모든 정점들이 실패되는데 이때 실패되는 정점 수와 실패가 전파되는 총 시간을 출력하는 문제이다. A정점부터 다익스트라를 실행하여 값이 갱신될 때 마다 시간의 최댓값을 갱신해주면서 개수를 세주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #include #include #define MAX_N 10000using namespace std;int t, n, d, c, x, y, z, r, a;int dp[MAX_N + 1];priority_queuepq;int main(){.. 더보기
BOJ)9202 Boggle 문제: icpc.me/9202 점수를 얻을 수 있는 문자열 셋이 주어진 뒤 Boggle 보드가 주어질 때 주어진 Boggle 보드에서 얻을 수 있는 최고점수 가장 긴 문자열 찾은 단어의 수를 출력하는 문제이다. 단어 사전에 단어가 30만개 까지 들어올 수 있으므로 트라이를 이용하여 해결하면 쿼리를 매번 최대 단어의 길이안에 처리해줄 수 있다. 우리는 단어 사전의 모든 단어들을 Trie에 저장해 준 후 Boggle 보드에서 Bruteforce를 통하여 모든 경우를 탐색하여 나올 수 있는 문자열들을 set에 저장해 준 뒤 답을 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505.. 더보기
BOJ)5052 전화번호 목록 문제: icpc.me/5052 전화번호 목록이 주어질 때 전화번호들이 일관성을 띄는지 조사하는 문제이다. 우리는 트라이를 활용하여 전화번호 목록들을 전부 트라이에 insert 한 뒤 모든 전화번호를 검색하여 문자열이 끝나는 지점에서 아직 더 탐색이 가능한 경우가 존재한다면 일관성이 없다고 결정해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #include #define MAX_N 10000using namespace std;struct Trie{ Trie* next[10]; bool term; Trie() : term.. 더보기
BOJ)2662 기업투자 문제: icpc.me/2662 투자 가능금액과 기업의 수가 주어지고 해당 기업에 x원만큼 투자했을 때 얻을 수 있는 이득 y가 주어질 때 최대 이익을 출력하는 문제이다. 최대 이익은 다이나믹 프로그래밍을 통하여 구해줄 수 있다. 테이블 dp[val][pos]의 정의는 "val 만큼 투자 가능할 때 pos번째 기업부터 n번째 기업까지 투자하여 얻을 수 있는 최대 이익"이 될것이다. 4 점화식은 dp[val][pos] = for(i=1~k) max(dp[val-i][pos+1]+a[i][pos]) 가 될것이다. 여기서 a[x][y]는 y번째 기업에 x만원을 투자하여 얻을 수 있는 돈이다. 이 때 역추적을 해주기 위하여 최댓값의 갱신이 일어날 때 마다 역추적 배열을 갱신해준 뒤 함수 종료후 백트래킹 해주면 된.. 더보기
BOJ)9252 LCS 2 문제: icpc.me/9252 LCS를 구해주는 문제이다. 다이나믹 프로그래밍을 통하여 LCS를 구해준 뒤 백트래킹하여 해당 LCS를 출력해주면 된다. dp테이블의 정의는 dp[x][y]는 첫번째 문자열을 x까지 두번째 문자열을 y까지 봤을 때 LCS의 크기이다. 점화식은 (if a[x]!=b[y]) dp[x][y]=max(dp[x][y-1],dp[x-1][y]) else dp[x][y]=dp[x-1][y-1] 이 된다. 소스코드에서는 테이블의 정의를 반대로 사용하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include #include #include usin.. 더보기
BOJ)1701 Cubeditor 문제: icpc.me/1701 문자열이 주어질 때 2번이상 나오는 부분 문자열 중 가장 길이가 긴 부분 문자열의 길이를 출력하는 문제이다. N이 5000밖에 안되기 때문에 문자열의 모든 Suffix에 대해서 failure function을 구해준 뒤 그 중 최댓값을 출력하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #define MAX_N 5001using namespace std;char a[MAX_N][MAX_N];int l, r;vector pi;void getpi(const char *c,int len) { pi.clear(); pi.resize(len); .. 더보기
BOJ)11585 속타는 저녁 메뉴 문제: icpc.me/11585 문자열 A와 B가 주어질 때 환형으로 이루어진 문자열 B로 이루어진 돌림판을 돌려서 A가 나올 확률을 구하는 문제이다. 우리는 환형으로 이루어진 문자열 B를 구현하기 위하여 문자열 B뒤에 문자열 B를 붙인 뒤 KMP를 이용하여 2개의 연속 된 문자열 B에서 A를 찾는 횟수를 구한 뒤 기약 분수 형태로 만들어 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #define MAX_N 1000000using namespace std;char a[MAX_N], b[2 * MAX_N];int n,.. 더보기

티스토리툴바