WhatISYourName?

[※ 주의 ※] 아래를 이해하지 않고 이 글을 볼 경우, 이해가 되지 않는 부분이 있을 수 있습니다. 1. [Algorithm] 어떤 알고리즘이 더 빠르고 효율적인가? - 시간복잡도 (4) 자, 대략적인 시간 복잡도 간 속도를 알았으니, 구체적으로 시간 복잡도를 어떻게 활용할 수 있는지 생각하여보자. 시간 복잡도는 말 그대로 "대략적인 시간"에 관한 이야기이다. 다른 말로, 대충 최대 어느 정도의 시간 및 연산 횟수가 소요될 지 어림잡을 수 있다는 이야기이다. 실제 코딩 테스트나 각종 대회에서도 필요한것은 소요되는 시간이지 시간 복잡도 그 자체가 아니다. 코딩계에서 통용되는 하나의 관습이 있다. 1초당 연산 횟수는 대략 1억($10^8$)번이다.구체적으로 말하자면 시간 제한이 1초라면 대략 1억번 연산 ..

[※ 주의 ※] 아래를 이해하지 않고 이 글을 볼 경우, 이해가 되지 않는 부분이 있을 수 있습니다. 1. [Algorithm] 어떤 알고리즘이 더 빠르고 효율적인가? - 시간 복잡도 (3) 가장 "작은" 함수들끼리의 증가 속도를 비교하여 보자. 통상 사용되는 "작은" 함수들의 개형을 나타내면, 아래 차트와 같은 결과를 얻을 수 있다. "작은" 함수들 ($1,\,n,\,\log n,\,n\log n,\,n^2,\,2^n,\,n!$)을 비교하였을 때 증가속도의 크기는 다음과 같이 쓸 수 있다. $$\large O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!) < \cdots$$ 따라서, 만약 여러 알고리즘이 중첩된다면 더 오른쪽에 있는 알고리즘..

[※ 주의 ※] 아래를 이해하지 않고 이 글을 볼 경우, 이해가 되지 않는 부분이 있을 수 있습니다. 1. [Algorithm] 어떤 알고리즘이 더 빠르고 효율적인가? - 시간복잡도 (2) $$ \huge Thinking \quad about \quad Big-O$$ 저번 글에서 빅-오 표기법을 "작은" 함수들로 나타내는 법을 다루었었다. 자주 사용하는 "작은" 함수들을 통해 시간 복잡도를 나타내었고, 이를 수식적으로 증명하였다. 실생활에서는 하나의 알고리즘이 아닌, 여러 알고리즘이 복합적으로 쓰이는 경우가 많다. 정렬을 하고 원하는 숫자를 찾는다던가, 누적 합을 여러 번 구해 가장 큰 합을 찾는 경우 등등 여러 알고리즘이 쓰이는 경우 어떻게 시간 복잡도를 산출해야 할까? 모든 알고리즘을 수식적으로 나타..

[※ 주의 ※] 아래를 이해하지 않고 이 글을 볼 경우, 이해가 되지 않는 부분이 있을 수 있습니다. 1. [Algorithm] 어떤 알고리즘이 더 빠르고 효율적인가? - 시간복잡도 (1) 지난 글에 $x > k$에서 $\left| f(x)\right| \leq C\left|g(x)\right|$를 만족하는 상수 $k, C$가 존재하면 $f(x) = O(g(x))$라고 표현할 수 있었다고 하였다. (엄밀히 말하면 $f(x) \in O(g(x)))$이라 표현해야 한다. $O(g(x))$는 하나의 집합이기 때문이다.) 그럼, 이런 질문을 하여보자. $7x^2$은 $O(n^3)$인가? 생각해보면 $x > 7$ 일 때 $7x^2 < x^3$이므로 (부등식의 양변에 $x^2$를 곱하자.) $C = 1, k = 7..

1. 서론 알고리즘의 정의를 뜯어보자면, "어떤 문제의 해결을 위하여, 입력된 자료를 토대로 원하는 출력을 유도하여 내는 규칙의 집합"을 의미한다. 결국, 하나의 문제를 해결하는 규칙 / 방법이라고 요약할 수 있겠다. 컴퓨터가 인류의 역사에 나타나면서 인류는 컴퓨터의 도움으로 해결할 수 있는 일련의 규칙 혹은 방법을 체계화하였다. 컴퓨터 시대의 태동 속에서, 누구의 규칙이나 방법이 다른 규칙 / 방법에 비해 더 좋은 방법을 가지는지에 대한 궁금증은 하나의 중요한 주제로 떠올랐다. 스스로 생각해보자, 외부 요인이 같다는 가정 하에 어떤 알고리즘이 다른 알고리즘보다 뛰어나다는 것은 무엇을 의미할까? 예를 들어, 1부터 (1억 + 1) 까지의 홀수들의 합을 구하는 알고리즘을 떠올려보자. ( $ 1+3+5+\c..