개인공부용123 프로그래밍 블로그

문제 : https://algospot.com/judge/problem/read/ARCTIC 동일한 성능을 가진 무전기로 모든 기지에 연락할떄 무전기 성능을 최소화하는 문제입니다. 이분법과 프림알고리즘 두가지 방법을 이용해서 풀었습니다. 두 기지사이의 거리정보를 미리 계산해서 배열에 넣은후 이분법에서는 queue를 이용해서 인자로 넣어진값으로 모든 기지에 연락할수있으면 true를 반환하고 아닐시 false를 반환하면서 점점 최적값으로 맞춰갔고프림알고리즘은 priority_queue를 이용해서 값을 계산했습니다. 100번 반복문을 실행하는이유는 절대오차가 10^-7보다 작게하기위해서입니다. #include #include #include #include #include #include #include us..

문제 : https://algospot.com/judge/problem/read/DARPA 카메라를 설치할때 가장 가까운 두카메라의 간격을 최대화 하는 문제입니다. 이분법과 그리디알고리즘을 이용해서 풀었습니다. 100번 반복문을 실행하는이유는 절대오차가 10^-7보다 작게하기위해서입니다. #include #include #include using namespace std; int N, M; // 카메라수 중계소수 vector loc; bool decision(double gap) { int install = 0; double min_limit = -1; for (int i = 0; i < loc.size(); ++i) { if (min_limit = N; } double optimize() { doubl..

문제 : https://algospot.com/judge/problem/read/ALLERGY 사람마다 먹을 수있는 음식이 있는데 최소한의 음식만 준비해서 모든 사람이 음식을 먹을수있게 하는 문제입니다. 이 문제를 해결할때 불필요한 낭비를 하지않기위해 음식을 못먹은 사람을 찾고 그 사람이 먹을 수있는 음식을 대입해가면서 최소로 준비할수있는 음식의 수를 찾는 방법을 이용했습니다. 간단한 가지치기로 현재까지 찾은 최저값보다 클 경우는 재귀를 더이상 수행하지 않게 처리했습니다. #include #include #include #include using namespace std; int n, m; // 친구 음식 int best; // 가장 좋은경우 vector foods[50]; // 음식을 먹을수있는 사람이..

문제 : https://algospot.com/judge/problem/read/QUADTREE 문자열을 입력받았을떄 이 문자를 상하로 뒤집은 문자열을 출력하는 문제입니다. 분할 정복을 이용해서 문제를 풀었습니다. *string의 begin함수는 r-value이므로 함수의 인자에 r-value를 넣으면 알고스팟 컴파일러에서 에러가 나왔습니다. 그러므로 다음 코드와 같이 l-value로 지정을 해준후 인자로 넣어주면 제대로 컴파일이 됩니다. r-value와 l-value 참조 : http://blog.mimu.me/understand-rvalue-reference-ko.html #include #include using namespace std; string str; // 1 2 // 3 4 이형태로 만듬..

문제 : https://algospot.com/judge/problem/read/STRJOIN 문자를 합쳐서 나오는 최소비용을 구하는 문제인데 이 무제는 가장 작은 값2개를 계속 더해나갔을 경우가장 최소의 비용을 가질수 있습니다. 즉 탐욕법을 적용해서 문제를 풀면 풀 수 있습니다. priority_queue를 이용하는 방법과 매 시행마다 sort를 이용하는 방법을 2가지를 이용해서 문제를 풀었습니다. #include #include #include #include // min힙을 사용하기위해 greater를 호출하는데 사용됨 #include using namespace std; #define IMPOS 999999 vector arr; int StrJoin(int n) { int MinPrice = 0;..

문제 : https://algospot.com/judge/problem/read/LUNCHBOX 첫번째 줄에는 테스트 케이스의 수 두번째 줄에는 도시락의 수가 주어지고 세번째 줄에는 도시락 별 도시락을 데우는데 걸리는 시간 네번째 줄에는 도시락 별 도시락을 먹는데 걸리는 시간이 주어진다. 이 문제에서 도시락 데우는 데 걸리는 시간은 무조건 일정합니다.(도시락을 먹기전에 데워야하기 떄문에) 그러므로 이 문제에서는 먹는 시간을 최소화하는것이 중요합니다. 이 문제의 경우 탐욕법을 이용하면 쉽게 풀수있습니다. 탐욕법을 사용하기위해서 먹는순서가 가장 오래걸리는거 부터 먹게 sorting했습니다. #include #include #include using namespace std; typedef struct { i..

문제 : https://algospot.com/judge/problem/read/MATCHORDER 한국 팀과 러시아팀의 레이팅이 주어지고 한국팀이 이길수있는 최대 승수를 출력하는 문제입니다. 이 문제는 dp를 이용해서 풀수있지만 그럴경우 시간복잡도가 커지게됩니다. 그러므로 탐욕법을 이용해서 풀었습니다.이길수있는 경기는 가장 레이팅이 비슷한 선수를 이용해서 이기고 무조건 지는경기라면 가장낮은 레이팅의 선수를 내보내서 최적해를 구합니다. #include #include #include using namespace std; vector Rus; vector Kor; int N; int order() { int wins = 0; multiset Ordered_Kor(Kor.begin(),Kor.end()); ..

문제 : https://algospot.com/judge/problem/read/SUSHI 주어진 예산에서 최대의 선호도를 찾는 문제입니다. 이때 주어질수 있는 예산의 최대값은 2,147,483,647입니다. 이 수를 이용해서 배열을 만드는게 불가능하므로슬라이딩 윈도 기법을 이용해서 배열의 수를 줄여야합니다. budget 부분의 최대 선호도를 구하기위해서는 budget - 20000 미만의 숫자는 필요가 없습니다.그리고 물건의 값은 100의 배수이므로 예산과 물건값을 100으로 나눠줍니다. #include #include #include using namespace std; int menu[20][2]; //0 은가격 1은 선호도 int cache[201]; // 다음 예산의 값을 정할떄 budget -..

문제 : https://algospot.com/judge/problem/read/NUMBERGAME 두 사람이 서로 번갈아가면서 왼쪽 오른쪽 둘중에서 한 카드를 고르거나 게임판에 두개이상의 숫자가 있을경우 왼쪽 오른쪽 둘중에서 2개의 카드를 지우면서 게임을하는데 서로 최선을 다했을경우 나오는 결과를 출력하는 게임입니다. 가지고있는 카드중 맨 왼쪽을 begin 맨 오른쪽을 end로하고 dp를 begin과 end로 찾을수있게 배열을 이차원배열로 생성해습니다. #include #include #include using namespace std; #define IMPOSSIBLE -99999 int arr[50]; int cache[50][50]; int n; int NumberGame(int begin, in..

문제 : https://algospot.com/judge/problem/read/TICTACTOE 두명이 번갈아가면서 흑돌 백돌 대신 o와 x를 이용해서 오목이아닌 삼목을 하는데 판이 주어지고 두명이 최선을 다해서 플레이할때 누가 이기거나 비기는지 찾는 문제이다. 해당문제를 dp 없이 완전탐색으로 풀려 할 경우 많은 시간이 걸리므로 dp를 사용하기위해 해당문제를 모델링해야합니다. board 판에 나올수있는 문자는 '.' , 'x' , 'o' 셋중 하나이므로 board판이 생길수 있는 경우의수는 3^9개이므로 19683(3^9)개의 int 배열을 이용해서 dp를 이용할수있습니다. #include #include using namespace std; char board[3][3]; char init_turn..