Layer7 - C언어 3차시 과제
동아리에서 과제를 풀고 블로그에 풀이를 작성해 오라고 해서 카테고리를 새로 만들었다. 앞으로는 이 카테고리에 과제나 동아리에서 공부한 내용들을 정리할 것이다.
1. 코드업 -> 문제집 -> 함수 -> 1535, 1555, 1566 풀고 블로그에 글
2. 코드업 -> 문제집 -> 재귀함수 -> 1916, 3733 풀고 블로그에 글
3. https://www.acmicpc.net/problem/10872 풀고 블로그에 글(선택)
과제는 이렇게 있었다.
CodeUp - 1535
간단하게 배열에서 가장 큰 값이 처음 나타나는 위치를 찾아주는 함수를 작성하는 문제이다. 배열의 원소를 하나씩 탐색하면서 대소비교를 하면 된다. 시간복잡도는 O(N)이 나오게 된다. 배열의 인덱스는 0부터 시작하므로 1을 더해서 return해줘야 한다.
int f()
{
int m = d[0];
int midx = 0;
for(int i = 0; i < n; i++)
{
if(m < d[i])
{
midx = i;
m = d[i];
}
}
return midx + 1;
}
CodeUp - 1555
n을 입력받고 1부터 n까지 더한 값을 return하는 함수를 작성해야 한다. 단순하게 접근한다면 1부터 n까지 하나하나 더해가는 방법이 있다. O(N)의 시간복잡도로 작성할 수 있다. 하지만 이 문제의 경우는 가우스 공식을 이용하면 O(1)의 시간복잡도로 풀이가 가능하다. 그 유명한 n*(n+1)/2 이 공식이다.
long long f(long long x) { return x * (x + 1) / 2; }
CodeUp - 1566
a의 n제곱을 구하는 함수를 작성해야 한다. 반복문으로 해도 되지만 재귀함수를 이용해서 구현했다. 시간복잡도는 O(N)이 나오게 된다. 다만 한가지 고려해야될게 있는데 1 9223372036854775807 이런식으로 입력이 주어질 경우이다. 컴퓨터는 대략 1초에 1억회의 연산을 수행할 수 있는데 9223372036854775807번의 연산을 수행하게 되면서 시간초과가 뜬다. 해결법은 간단하다. a가 1일경우에만 이런 예외 케이스가 발생하는 것이므로 a가 1일경우를 따로 체크해서 1을 return해주면 된다.
long long pow(int x, int n)
{
if (!n) return 1;
else if (n == 1) return x;
else if (x == 1) return 1;
return pow(x, n - 1)*x;
}
CodeUp - 1916
피보나치 수를 구하는 문제이다. 피보나치 수는 재귀함수를 이용해서 간단하게 구할 수 있다. 하지만 일반적으로 피보나치 수를 재귀로 구하게 된다면 O(2^N)의 시간복잡도가 나오게 된다. N이 조금만 커져도 연산 횟수가 기하급수적으로 증가하면서 시간초과가 뜨게 된다. 그러면 이 문제를 어떻게 해결할 수 있을까? 피보나치 수를 구하는 함수의 재귀 트리를 생각해보면 답이 나온다. 이미 재귀 트리를 한번 탔던 숫자를 중복해서 또 타는것을 알 수 있다. 따라서 이 문제는 한번 연산한 값을 배열과 같은 공간에 저장해둬서 같은 연산을 한번 이상 하지 않도록 하는 dynamic programming기법을 사용해서 풀어야 한다. 줄여서 dp라고도 한다. dp를 쓰면 O(2^N)이었던 시간복잡도를 O(N)까지 줄일 수 있어서 시간초과가 나지 않게 된다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int dp[201];
int f(int x)
{
if (x < 3) return 1;
else if (dp[x]) { return dp[x]; }
else { return dp[x] = (f(x - 1) + f(x - 2))%10009; }
}
int main(void)
{
int n;
scanf("%d", &n);
printf("%d", f(n));
return 0;
}
그리고 마지막 결과에만 10009를 나눠야 되지 않냐고 의문이 들 수 있는데 모듈러 산술 연산은 아래와 같이 분배법칙이 성립한다.
쉽게 말하면 (a + b) % n = (a % n)+(b % n)이 성립하기 때문에 위와 같은 코드 작성이 가능해지는 것이다.
CodeUp - 3733
이 문제는 일단 재귀함수를 이용해서 연산 루틴을 구현할 수 있다. 하지만 문제는 입력값의 범위가 너무 크다는 것이다. 최악의 경우에는 우박수 연산을 하는 함수를 1부터 10000000까지 10000000번 호출해야 하는데 이렇게 되면 재귀함수에서 평균적인 연산 횟수가 10회만 넘어도 1억회 연산을 초과하므로 시간초과가 나게 된다. 따라서 이 문제도 dp를 이용해야 한다. 작은 수부터 우박수를 구해서 길이를 배열에 저장해두면 나중에 같은 수를 만났을 때 굳이 연산을 안하고 그냥 배열에서 꺼내서 길이를 더해주면 되니까 시간이 크게 단축된다. 그리고 또 고려해야될 문제가 하나 더 있다. 바로 Out of Bounds인데 일단 나는 dp배열의 크기를 10000001로 줬다. 하지만 계속 Out of Bounds가 나길래 뭐가 문제지? 하고 게시판을 봤다. 그런데 우박수의 길이가 1억이 넘는 경우도 있다고 한다.. 최대로 나올 수 있는 우박수의 길이를 모르는 상태에서 무작정 배열의 크기를 늘리는것은 좀 억지같다고 생각해서 그냥 10000000이 넘는 길이부터는 dp에 저장을 안하는 식으로 했다. 이렇게 되면 연산 횟수가 조금 늘어나겠지만 다행히도 시간초과는 뜨지 않았다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
unsigned long long int dp[10000001];
unsigned long long int f(unsigned long long x)
{
if (x == 1) return 1;
if (x > 10000000)
{
if (x % 2) return f(3 * x + 1) + 1;
else return f(x / 2) + 1;
}
else if (dp[x]) return dp[x];
else if (x % 2) return dp[x] = f(3 * x + 1) + 1;
else return dp[x] = f(x / 2) + 1;
}
int main(void)
{
unsigned long long a, b, min, num, maxlen = 0;
scanf("%lld %lld", &a, &b);
for (int i = a; i <= b; i++)
{
num = f(i);
if (maxlen < num) { min = i; maxlen = num; }
}
printf("%lld %lld", min, maxlen);
return 0;
}
이번 과제는 이제 막 Layer7에 들어와서 C를 처음 접하는 사람들은 아예 접근도 못할것 같다고 생각되는 과제였다. 나도 처음 재귀를 공부할때는 피보나치 함수 구하는 재귀도 왜 이게 이렇게 되는지 잘 이해가 안갔던 기억이 있는데 재귀에 dp까지 써야되고 시간복잡도 까지 생각해야 하는 문제들은 초심자가 하기엔 난이도가 있는것 같다.