[C#] 24313번: 알고리즘 수업 - 점근적 표기 1

목차

---

백준 단계별로 풀어보기

25.10.04

11단계: 시간 복잡도

24313번: 알고리즘 수업 - 점근적 표기 1

문제 링크 : https://www.acmicpc.net/problem/24313

 

문제 풀이

>> 문제에 나온 O-표기법 해석

• O(g(n)) = {f(n) | 모든 n ≥ n₀에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n₀가 존재한다}
• O(n) --> g(n) = n
• f(n) = a₁n + a₀

--> a₁, a₀, c, n₀ 가 주어졌을 때,

1. O(n)에서 조건을 보면 a₁과 c에 각각 n을 곱하는 것이므로 'a₁ ≥ c' 라면 처음에 O(n₀) 가 참이더라도 n이 커지면서 결국엔  f(n) ≥ c × g(n) 즉, a₁n + a₀ ≥ c × n 이 되기 때문에 O(n) 정의를 만족할 수 없다.
2. a₁ < c 이고, f(n₀) ≤ c × g(n₀) 즉, a₁n₀ + a₀ ≤ c × n₀ 이 참이라면 모든 n ≥ n₀ 이기 때문에 항상 O(n) 정의를 만족한다.

 

ex1) a₁ = 7, a₀ = 7, c = 8, n₀ = 1 --> f(n) = 7n + 7, g(n) = n

→ f(1) = 7 + 7 = 14, c × g(1) = 8 × 1 = 8

∴ 14 ≤ 8 이므로, O(n) 정의를 만족하지 못한다.

 

ex2) a₁ = 7, a₀ = 7, c = 8, n₀ = 10 --> f(n) = 7n + 7, g(n) = n

→ f(10) = 70 + 7 = 77, c × g(1) = 8 × 10 = 80

∴ 77 ≤ 80 이므로, O(n) 정의를 만족한다.

 

>> 실수한 부분

- 작성한 코드

class Backjoon
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
        int a1 = int.Parse(input[0]);
        int a0 = int.Parse(input[1]);
        int c = int.Parse(Console.ReadLine());
        int n0 = int.Parse(Console.ReadLine());

        if (a1 >= c)
        {
            Console.Write("0");
        }
        else
        {
            Console.Write(a1 * n0 + a0 <= c * n0 ? "1" : "0");
        }
    }
}

-->  a₁, a₀의 범위는 -100 ~ 100 이므로, a₁ = c 이고 a₀ ≤ 0 라면, O(n) 정의를 만족하게 된다.

ex) a₁ = 7, c = 7, a₀ = 0 라면 a₁n + a₀ ≤ c × n 에서 7n ≤ 7n 이기 때문에 O(n) 정의를 항상 만족하게 된다.

 

>> 풀이

1. a₁, a₀, c, n₀ 를 입력받아 int 값으로 변환한다.
2. a₁ > c 라면, O(n) 정의를 만족하지 않으므로 "0" 을 출력한다.
3. a₁ == c 이고 a₀ ≤ 0 라면, O(n) 정의를 만족하므로 "1"을 출력한다. --> a₁ == c 이고 a₀ > 0 인 경우는 어차피 항상 a₁n + a₀ ≤ c × n 을 만족할 수 없으므로 아래의 else에서 걸러질 것이기에 따로 조건을 추가하지 않는다.
4. 그 외의 경우에는 삼항연산자를 통해 a₁n₀ + a₀ ≤ c × n₀ 을 만족하면 항상 O(n) 정의를 만족하므로 "1"을, 아니라면 "0"을 출력한다.

 

정답 코드

class Backjoon
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
        int a1 = int.Parse(input[0]);
        int a0 = int.Parse(input[1]);
        int c = int.Parse(Console.ReadLine());
        int n0 = int.Parse(Console.ReadLine());

        if (a1 > c)
        {
            Console.Write("0");
        }
        else if (a1 == c && a0 <= 0)
        {
            Console.Write("1");
        }
        else
        {
            Console.Write(a1 * n0 + a0 <= c * n0 ? "1" : "0");
        }
    }
}