WhatISYourName?

[※ 주의 ※] 아래를 이해하지 않고 이 글을 볼 경우, 이해가 되지 않는 부분이 있을 수 있습니다. 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..

어떤 배열이나 container의 최댓값 및 최솟값이 필요한 경우는 무수히 많다고 해도 과언이 아니다. 하지만, 배열의 원소 하나씩 접근하고 비교하면서 최댓값 / 최솟값을 찾으면 이거만큼 코드의 가독성이 떨어지고 슬픈일이 아닐 수 없다. 특별한 함수를 사용하지 않고 for문을 통해 배열의 원소 하나씩 접근하며 도는 경우 다음과 같은 코드를 작성할 수 있다. HTML 삽입 미리보기할 수 없는 소스 배열 nums의 원소를 하나씩 돌면서 max_num과 min_num에 각각 최댓값과 최솟값이 담기는 모습을 확인할 수 있다. 그러나, 너무나도 귀찮고, 귀찮다. 하물며 최댓값 또는 최솟값의 index를 묻는다면 새로운 변수에 담아야 하거나, 다른 방법으로 구해야 한다. 이제, 이러한 길고 긴 for문을 탈출하고 ..

accumulate 함수는 많은 C++ 사용자들에게 널리 알려져 있지만, 그래도 아직 모르는 사용자들이 있다고 생각되어 포스팅을 남긴다. std::accumulate 함수는 특정 배열 혹은 container의 누적 합을 구할 때 사용가능한 함수이다. 특히, 전체 합을 구하거나, 한 번의 누적 합을 구할 때 사용할 수 있다. 함수 accumulate를 사용하지 않고 누적 합을 구한다면 다음과 같이 작성할 수 있다. 예를 들어, vector nums 안에 있는 모든 원소들의 합을 구한다고 가정하여보자. 다음과 같이 코드를 작성할 수 있다. HTML 삽입 미리보기할 수 없는 소스 코드 자체는 길지 않지만, accumulate는 누적 합을 구하는 것 이외의 응용을 할 수 있는 방법이 무궁무진하다. 1. accu..