본문 바로가기

분류 전체보기

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에 머그컵이라는 대회가 열려있길래 참가했다. 총 8문제중 5문제를 풀었는데 나머지 3문제는 내 수준에서는 해결할 수 없는 문제였다. 출발 지점에서 끝 지점 까지 최대로 수집 가능한 자원을 찾는 전형적인 다이나믹 프로그래밍 문제였다. 점화식은 dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j] 다. 항상 주어지는 조건대로 게임을 할 때 가장 빨리 끝나는 게임과 번호를 출력하는 문제이다. 수식에 따라서 계산을 해주면 게임의 횟수는 ((k/(m+1))+1)*2 가 될 것이고 set을 이용하여 관리를 해주면 편하게 해결 가능했다. 마을의 위치가 좌표로 주어질 때 각 마을 사이의 거리의 정수부분이 소수일 경우 이동가능하다고 할 때 A부터 B까지의 최단거리를 출력하면 되.. 더보기
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(){.. 더보기
KMP(Knuth–Morris–Pratt) 알고리즘 KMP 알고리즘은 문자열 A와 문자열 B가 있을 때, 문자열 A에서 문자열 B를 찾아주는 알고리즘 입니다. KMP는 KMP를 만든 사람의 이름인 Knuth, Morris, Prett 세 사람의 앞 글자를 따서 KMP 알고리즘이라고 불립니다. 자 그러면 우리는 문자열 A에서 문자열 B를 찾는 방법을 생각해봅시다. 가장 먼저 생각해 볼 수 있는 방법은 Brute force가 있겠군요. 하지만 모든 경우를 다 탐색할 경우 문자열 A의 길이가 N,문자열 B의 길이가 M이라면 O(N*M)의 시간 복잡도를 가지게 됩니다. 만약 N,M이 10만인 문제가 주어진다면 시간 초과를 보게 될 것입니다. 자 그러면 KMP를 사용하였을 때의 시간복잡도는 어떻게 될까요? 놀랍게도 O(N+M)의 시간복잡도만에 문자열 A에서 문자열.. 더보기
[자료구조]트라이(Trie) 트라이(Trie)는 문자열에서의 검색을 빠르게 해주는 자료구조입니다. 우리는 정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간만에 원하는 데이터를 검색할 수 있습니다. 하지만 문자열에서 이진검색트리를 사용한다면 문자열의 최대 길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것입니다. 우리는 문자열에서의 검색을 개선하기 위하여 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있습니다. 트라이라는 명칭은 Retrieval에서 유래했다고 합니다. 트라이가 retrieve(탐색)하는데 유용한 걸 생각하면 납득이됩니다. 자 그러면 트라이는 어떻게 문자열의 검색을 O(M)만에 처리해 줄 수 있을까요? 아래 그림은 문자열 집합 = {"AE" , "ATV", "ATES", .. 더보기
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만원을 투자하여 얻을 수 있는 돈이다. 이 때 역추적을 해주기 위하여 최댓값의 갱신이 일어날 때 마다 역추적 배열을 갱신해준 뒤 함수 종료후 백트래킹 해주면 된.. 더보기

티스토리툴바