기록보관소

리스트에서 정렬된 원소 중 특정 원소를 logn 시간 내에 찾는 알고리즘이다. 혹은 특정 원소가 리스트에 없음을 확인하는 알고리즘이다. 리스트의 중간값과 찾고자 하는 값을 비교하고 만약 찾고자 하는 값이 더 크면 리스트의 하한을 중간보다 1만큼 높은 값으로 바꾸고, 더 작으면 리스트의 상한을 중간보다 1만큼 낮은 값으로 바꾼다. 탐색하는 범위를 절반씩 줄여나가면서 결국에는 원하는 값을 리스트에서 찾거나 찾지 못하게 된다. 절반씩 범위를 줄여나가므로 lgN만큼의 시간이 소요된다.

수 찾기 문제는 빠른 정렬과 이진 탐색을 활용하는 문제입니다. N이 10만이기 때문에 NlogN의 시간복잡도를 가지는 정렬 알고리즘을 사용해야하며 탐색할 숫자의 개수도 10만이기 때문에 logM의 이진 탐색 알고리즘을 사용해야 합니다. 작성한 코드는 다음과 같습니다. #include int N,M; int number[100020]; int temp; void quicksort(int low, int high) { if (low >= high) return; int pivot =number[high]; int index = low; int temp; for (int i = low;i

마인크래프트 문제는 지형을 평탄화할 수 있는 모든 경우를 고려하여 계산하는 문제이다. 평탄화된 지형의 최소 높이는 0, 최대 높이는 지면의 블록 개수와 인벤토리에 있는 블록 개수를 면적으로 나눈 값이다. 이 두 값 사이의 값을 높이로 가지기 위해 블록을 부수거나 쌓아야 하는 데 이때 가장 시간이 적게 걸리는 높이를 찾으면 된다. 작성한 코드는 다음과 같다. #include int N, M, B; int land[520][520]; int sum = 0; int time; int min=987654321; int height; int main(void) { scanf("%d %d %d", &N, &M, &B); for (int i = 0; i < N; i++) { for (int j = 0; j < M; ..

팰린드롬수 문제는 문자열을 다루는 문제이다. 문자열을 대칭적으로 확인하여 같지 않으면 no를 출력하고, 전부 같으면 yes를 출력하도록 함수를 작성하면 된다. 작성한 코드는 다음과 같다. #include #include char temp[10]; int func() { int length = strlen(temp); if (length == 1) { if(temp[0] == '0') return -1; else { return 1; } } else { for (int i = 0;i

조합 0의 개수 문제는 소인수 분해시 2와 5의 개수를 활용하는 문제입니다. 팩토리얼 값을 소인수 분해했을 때 5의 개수를 구하는 방법은 팩토리얼에서 처음의 항을 5로 나눈 수 + 25로 나눈 수 + 125로 나눈 수 + .... 식과 같다. 이런 방식으로 2와 5의 개수를 찾고 그 중 가장 작은 값이 0의 개수가 된다. 작성한 코드는 다음과 같다. #include long long int n, m; long long int five, two; long long int d; int main(void) { scanf("%lld %lld", &n, &m); d = 5; while (1) { if ((n< d)) break; five += (n / d); d *= 5; } d = 2; while (1) { i..

팩토리얼 0의 개수 문제는 팩토리얼 값을 소인수분해를 하였을 때 2와 5의 지수 중 최소값을 활용하는 문제입니다. 0의 개수는 2와 5의 지수 중 최소의 개수와 동일하다는 사실을 이용하면 됩니다. 작성한 코드는 다음과 같습니다. #include int N; int result = 1; int cnt = 0; int two, five; int temp; int main(void) { scanf("%d", &N); for (int i = 1; i five) printf("%d\n", five); else printf("\n", two); } } 문제의 지문은 다음의 링크에서 확인할 수 있습니다. https://www.acmicpc.net/problem/1676

패션왕 신해빈 문제는 경우의 수를 이용한 문제입니다. (같은 종류의 개수 + 1) 항들의 곱에 -1을 한 값이 옷을 입을 수 있는 경우의 수가 됩니다. 작성한 코드는 다음과 같습니다. #include #include int T; int n; char temp[100]; char clothes[300][100]; char cnt[300]; int limit; int result = 1; int k; int main(void) { scanf("%d", &T); for (int i = 0; i < T; i++) { scanf("%d", &n); result = 1; limit = 0; for (int j = 0; j < 2*n; j++) { scanf("%s", temp); if (j % 2 == 1) { f..

다리 놓기 문제는 조합을 사용하는 문제입니다. mCn의 공식을 활용하여 문제를 해결할 수 있습니다. 작성한 코드는 다음과 같습니다. #include int T; int N, M; int result = 1; int main(void) { scanf("%d", &T); for (int i = 0; i < T; i++) { result = 1; scanf("%d %d", &N, &M); for (int j = 0; j < N; j++) { result = result * (M--) / (j + 1); } printf("%d\n", result); } } 문제의 지문은 다음의 링크에서 확인할 수 있습니다. https://www.acmicpc.net/problem/1010