'분류 전체보기' 카테고리의 글 목록 (5 Page)

38. UVa-624 CD //Easy recursive Backtracking

문제 Input이 저렇게 주어질 때 저장용량에 들어갈 수 있는 곡들의 조합 중 가장 저장용량을 꽉 채울 수 있는 곡들의 조합과 그 용량을 출력하는 문제다. 이 문제는 Input의 크기가 작아서 그냥 recursive backtracking기법을 써서 완전탐색으로 풀었다. 근데 아직 재귀적 탐색이 익숙치가 않아서 별로 효율적이지 않을 수도 있다. 다음은 코드다. #include using namespace std; int maximum = 0; int N, num_of_tracks; int time_of_tracks[20]; int Choice[20]; int BestChoice[20]; int max_choice_num; void Backtracking(int c, int num_of_choices, i..

기초 알고리즘 문제 풀이 2020. 3. 2. 18:57

37. UVa-11236 Grocery Store //complex multi loop searching

문제 문제는 간단하다. Input은 따로 주어지지 않고, 0

기초 알고리즘 문제 풀이 2020. 2. 28. 16:26

36. UVa-10487 Closest Sums //nlogn solution

문제 문제는 n개의 원소로 이루어진 입력이 주어졌을 때 들어오는 또 다른 input인 query에 대해 n개의 입력 중 두 원소를 더한 sum이 query에 제일 가까운 sum을 구하는 것이다. Competitve Algorithm책에서는 가능한 모든 sum을 보는 O(n2)풀이를 제시하고 있는데, 사실 정렬을 제외한 파트를 O(n)안에 구현하는 방법도 있다. (오버헤드와 사용공간이 좀 늘어나지만) 다음를 보자. 우선, 들어온 n개의 input에 대해 nlgn시간 안에 Sorting을 하자. 그 후 배열의 시작원소를 start, 끝 원소를 end로 두자. 이후 반복문을 돌리는데 각 step에서 input[start]+input[end]를 sum으로 평가한 후 sumquery이면 --end를 하면 sum이..

기초 알고리즘 문제 풀이 2020. 2. 28. 01:03

35. UVa-1260 Sales

문제 요약 Input: Test case의 수 T, 이어서 n과 n개의 input이 들어온다. n개의 input을 an이라 할 때 각 ai에서 ai이전 원소들 중 ai보다 작거나 같은 원소들의 개수 합을 i=1~n에 대해 합한 것을 구하세요. 못풀 수가 없지 코드 #include using namespace std; int main() { int T,b_sum,n; int a[1000]; cin >> T; while (T--) { cin >> n; b_sum = 0; for (int i = 0; i > a[i]; for (int i = 1; i < n; i++) for (int j = 0; j < i; j++) if (a[j]

기초 알고리즘 문제 풀이 2020. 2. 27. 20:46

34. UVa-10976 Fractions Again?! //느린 배열?

문제 문제 자체는 쉽다 자연수 k가 주어졌을 때 1/k = 1/x + 1/y 를 만족하는 자연수 쌍(x,y)를 찾는 것이다. (대칭 해 제외) Sample Output을 보면 search space에 대해 어느정도 줄일 수 있는 IDEA를 얻을 수 있는데 다음 그림을 보자. 12가 k로 주어졌을 때 y를 보면 k+1부터 2*k까지이다. 사실 생각해보면 x나 y중 하나의 수는 k보다 작거나 같아질 수 없다.(부등식을 생각해보자) 또한 대칭해 제외이니까 2k보다 큰 해는 볼 필요 없다. 따라서 search space의 특성을 반영하여 해를 구하는 프로그램을 짜보면 다음과 같다. //CORRECT SOL #include #include #include using namespace std; int main() ..

기초 알고리즘 문제 풀이 2020. 2. 27. 16:37

33. UVa-1237 Expert Enough? //쉬운 완전탐색

문제 Input은 다음과 같은 형식으로 들어온다. 쉬운 문제니까.. 그냥 fop문 하나로 각 case에 대해 search하면 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int main() { int T, D, Q; int L[10000]; int H[10000]; int P[10000]; char names[10000][20]; bool come; int idx; scanf("%d", &T); while (T--) { //input part scanf("%d", &D); for (int i = 0; i < D; i++) scanf("%s %d %d", &names[i], &L[i], &H[i]); ..

기초 알고리즘 문제 풀이 2020. 2. 27. 01:40

32. Tips for exhaustive searching(Brute-force)

완전 탐색 algorithm을 무식하게 만들지 않는, 조금이라도 더 빠르게 돌릴 수 있게 하는 몇 가지 팁. 불가능한 탐색 공간의 빠른 가지치기 대칭성 활용 사전 작업, 사전 계산 ~ 공간을 써서 시간을 줄이기 문제를 거꾸로 접근(탐색 주체의 선정) 소스코드의 최적화 빠른 언어: C> C++ > JAVA cin, cout보다는 printf,scanf 힙정렬 보다는 퀵정렬, 힙정렬은 index가 너무 멀리 떨어져있어서 cache의 활용도가 낮다. 2차원 배열에서는 행우선으로 접근 기본 정수 자료형에 대한 비트 연산이 Boolean배열에 대한 bit연산보다 훨씬 빠르다. 가능하면 저차원의 자료구조를 이용하자 거의 모든 자료를 전역으로 두어 한 번만 선언되게 하자 반복/재귀의 갈림길에서는 반복이 낫다. 재귀해..

기초 알고리즘 문제 풀이 2020. 2. 27. 01:13