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

스택을 쓸수도있는 문제이지만 배열을 써서 쉽게풀리므로 배열로 풀었습니다. String으로 문자를 입력받은후 문자열을 각각확인해서 '('이면 +1 , ')' 이면 -1을 chk변수에 취합니다. 이 과정을 반복하는중에 chk가 0보다작게되면 괄호문자열이 아니므로 바로 빠져나가서 NO를 출력합니다 만약 끝까지 반복했을때 chk변수가 0일경우 정상적인 괄호이므로 YES를 출력합니다. #include #include using namespace std; int main() { std::ios::sync_with_stdio(false); string str; int chk; int C; cin >> C; while (C--) { chk = 0; str = ""; cin >> str; for (int i = 0; i..

제목에서 아시다시피 스택수열입니다.. 그렇습니다 스택을 사용해서 풀어보겠습니다. 이 문제는 인풋으로주어진 수열을 스택의 push, pop연산을 이용해서 표현할수있는가를 묻는 문제입니다. 이문제의 포인트는 현재 스택의 top값이 만들려는 수열의 값보다 크면 안된다는것입니다. 왜냐하면 스택의 입력은 1부터 차례대로 주어지게됩니다. 그리고 스택의 특성인 FILO(후입 선출)의 특성상 이후 스택에 들어올수있는 값은 적어도 스택의 top보다 크기때문입니다. 아래는 해당 소스 코드입니다. #include #include #include using namespace std; int main() { std::ios::sync_with_stdio(false); stack st; string str; int K; int ..

소수찾기문제는 유명한 알고리즘인 에라토스테네스의 체를 이용하면 쉽게풀수있습니다. 에라토스테네스의 체의 최악 수행시간은 O(N*log(logN))이라고합니다. #include #include using namespace std; int main() { // 에라토스테네스의 체를 이용한 소수 구하기 std::ios::sync_with_stdio(false); int M, N; // M > M >> N; bool* arr = new bool[N + 1]; for (int i = 2; i

백준 9426문제는 N개의 원소중에서 K개의 부분집합원소의 중앙값들의 합을 구하는 문제입니다. 이 문제는 세그먼트 트리를 이용해서 풀었습니다. 세그먼트 트리의 각노드에는 노드들의 갯수를 저장하고있습니다. (리프 노드에는 해당 노드가 세그먼트 트리에있는지 없는지를 표시) 업데이트시 1, -1로 원소를 추가 삭제 가능합니다. 쿼리함수를 이용해서 서브트리에 대한 중간값에 해당하는 값을 찾을수있습니다. 세그먼트 트리는 보통 포화 이진트리이므로 값이 N개일 떄 높이는 O(logN)입니다. 즉 하나의 중간값을 찾는데 걸리는시간은 O(logN)이 걸립니다. 그러므로 세그먼트 트리를 이용한 최악의 경우 시간 복잡도는 약 O(NlogN)입니다. Worst Case time Complexity = O(NlogN) incl..

문제 : https://algospot.com/judge/problem/read/GRADUATION 졸업하기위해 전공과목을 수강해야하는데 전공과목을 듣기위해서는 선행과목이 필요할수있다. 이런 제한조건을 가지고 최소학기에 졸업할수있는 학기를 출력하거나 불가능할경우 불가능을 출력하는 문제입니다. 이 문제는 비트마스크와 DP를 이용해서 문제를 풀었습니다. 비트연산을 이용해서 메모리 사용량을 줄이고 dp를 이용해서 탐색 시간을 줄였습니다. 처음에 입력부분에서 or 비트연산을 이용하지않고 (int)pow(2,n)연산을 이용해서 각과목에대한 선행과목 정보등을 더해가면서 표시했더니 테스트케이스는 정확히 나왔지만 사이트에서 답안 제출을 할때 오답이 나왔습니다. 그리고 cache배열은 이진연산을 이용한 정보를 담을수있게..

문제 : https://algospot.com/judge/problem/read/PASS486 주어진 범위내에서 정해진 약수의 갯수를 가지는 수를 찾는 문제입니다. 이를 해결하기위해서 주어진 범위내에서 수의 약수를 배열에 미리 저장해두고 찾는 방식을 사용했습니다. 가장작은수인 2부터 10,000,000까지 차례대로 약수의 갯수를 미리 구해서 문제를 해결했습니다. 이를 위해 에라토스테네스의 체를 이용해서 소인수분해한 수 중 최소의 수를 찾은후 그것을이용해서 각 수의 약수의 갯수를 구했습니다. #include #include using namespace std; const int MAX = 10000000; int MinPrime[MAX + 1]; // 최소 소수 int MinPrimeNum[MAX + 1]..

문제 : https://algospot.com/judge/problem/read/POTION 마법의 약을 만드는데 넣어야할 재료의 최소량을 구하는 문제입니다. 유클리드알고리즘을 이용해서 마법의 약을 만드는데 필요한 재료들의 최소공배수를 찾은후 가지고있는 모든 재료들중 가장 높은 비율로 나머지 재료들을 맞춰야합니다. 이떄 이 비율의 분모는 최소공배수여야합니다 왜냐하면 맞춰진 재료들이 정수여야하기때문입니다. #include #include using namespace std; int n; // 재료의수 int recipe[200]; int cur[200]; int answer[200]; int gcd(int a, int b) { if (a < b) swap(a, b); return b == 0 ? a : g..

문제 : https://algospot.com/judge/problem/read/RATIO 플레이한 횟수 N, 승리 횟수 M 일떄 몇연승을 했을경우 승리율을 높일수있는지 찾는 문제이다 (승리율은 승리횟수 / 플레이한 횟수를 한 정수이다) 연승한 횟수 + 승리 횟수 / 연승한 횟수 + 플레이한 횟수 와 승리 횟수 / 플레이한 횟수를 비교해서 이분법을 사용해서 답을 찾으면 됩니다. (문제를 풀때 decision함수의 인자로 long long을 사용하지않으면 범위를 초과해서 결과가 나오지않습니다.) #include using namespace std; #define MAX_SWIN 2000000000 long N, M; // 플레이횟수, 승리횟수 int decision(long long s_win, long ..

문제 : https://algospot.com/judge/problem/read/LOAN 갚을 금액 N, 연이율 P, M개월동안 C원을 갚는다했을경우 한달에 최소 얼마를 갚아야하는지 구하는 문제입니다. 이문제는 이분법으로 접근해서 풀었습니다. (식으로도 풀수있습니다.) *이분법으로 접근했을경우 setprecision(10)을 사용하지 않을경우 오차가 10^-7을 넘기때문에 오답처리가됩니다. #include #include using namespace std; double N, P; // 갚을 금액, 이자율 int M; //몇달동안 bool if_possible(double Monthly_payment) { double Money = N; const double interest = P / 1200.0; f..

문제 : https://algospot.com/judge/problem/read/CANADATRIP N개의 도시가 있는데 도시 M[i]미터 전부터 표지판이 세워지고 G[i]미터 간격으로 표지판이 세워진다. 이때 K번째 표지판의 위치를 구하는 문제이다. 이 문제또한 결정문제로 바꿔서 풀경우 빠르게 풀수 있습니다. 이분법을 이용해서 K개 이상의 표지판을 포함하는 거리를 좁혀나가면서 K개의 표지판을 포함하는 거리를 찾았습니다. #include #include #include using namespace std; int N, K; int L[5000], M[5000], G[5000]; // 시작점부터 도시의 거리, (표지판이)몇미터부터, (표지판이)몇미터 간격 bool decision(int dist) { in..