(번역) 알고리즘 쉽게 이해하기 : 시간 복잡도와 Big-O 표기

(번역) 알고리즘을 쉬운 영어로 : 시간 복잡도와 Big-O 표기

오늘 번역글은 medium 의 freecodecamp 글입니다.
알고리즘, 시간 복잡도, Big-O 를 사례를 들어가며 이해하기 쉽게 풀어서 설명된 글입니다.
원문 의 모든 부분을 번역하지는 않습니다. 주요 부분만 발췌하여 번역합니다.

서론

  • 모든 개발자는 자신만의 시간 관념이 있습니다. 개발자들은 대부분의 시간을 사용자들에게 쏟아붓기 때문에, 최대한 시간을 효율적으로 사용하고 싶어하죠. 시간복잡도 를 최소화 함으로써 이게 실현가능해집니다.
  • 프로그래밍에서 시간복잡도를 이해하기 전에, 먼저 이 시간복잡도가 알고리즘에서 흔하게 활용된다는 사실을 기억해야합니다.

그래서 알고리즘은 뭔가요?

Algorithm is a series of contained steps which you follow in order to achieve some goal, or to produce some output

  • 알고리즘은 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미합니다.
  • 할머니가 케이크를 만드는 과정을 알고리즘으로 표현해보자면,
    function BakeCake(flavor, icing){
    /*
     1. Heat Oven to 350 F
     2. Mix flour, baking powder, salt
     3. Beat butter and sugar until fluffy
     4. Add eggs.
     5. Mix in flour, baking powder, salt
     6. Add milk and " + flavor + "
     7. Mix further
     8. Put in pan
     9. Bake for 30 minutes
    10." + if(icing === true) return 'add icing' + "
    10. Stuff your face
    */
    }
    BakeCake('vanilla', true) => deliciousness
    
  • 알고리즘은 각기 다른 모양과 형태를 지니고 있기에, 타임 복잡도를 설명하는데 자주 사용됩니다.

  • 애플파이 한 개를 100 가지 방법으로 자를 수 있는 것처럼, 한 문제를 여러가지의 알고리즘으로 풀 수 있습니다.
  • 시간복잡도를 분석 하는 것은 input n 에 대하여 알고리즘이 문제를 해결하는 데에 얼마나 오랜 시간이 걸리는 지를 분석하는 것 과 같습니다. 그리고 이는 Big-O 표기 를 이용하여 정의할 수 있습니다.

Big-O 표기란?

Big-O notation is a way of converting the overall steps of an algorithm into algebraic terms, then excluding lower order constants and coefficients that don’t have that big an impact on the overall complexity of the problem.

  • 개발자들에게는 위의 사전식 정의보다는 아래의 정의가 더 와닿을 겁니다.
    Regular       Big-O
    2             O(1)   --> It's just a constant number
    2n + 10       O(n)   --> n has the largest effect
    5n^2          O(n^2) --> n^2 has the largest effect
    
  • 이 예제가 의미하는 것은 다음과 같습니다. 시간복잡도에서 중요한 것은 정해진 표현식에 가장 큰 영향을 미치는 n 의 단위이다

  • 대표적인 시간 복잡도들을 간단하게 정의해봅니다.

    1. O(1) – 상수 시간 : 입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다.
    2. O(log n) – 로그 시간 : 입력값 n 이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듭니다.
    3. O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가집니다.
    4. O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱입니다.
    5. O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱입니다.
  • 위 정의를 가지고 아래 예제의 시간복잡도를 계산해보겠습니다.
    var n = 16; -- 입력값 n 이 16일 때
    O (1) = 1 step "(awesome!)" -- O(1)는 시간복잡도가 1입니다.
    O (log n) = 4 steps  "(awesome!)" -- O(log n)는 시간복잡도가 4입니다. (log 의 밑이 2라고 가정)
    O (n) = 16 steps "(pretty good!)" -- O(n)는 시간복잡도가 16
    O(n^2) = 256 steps "(uhh..we can work with this?)" -- O(n^2)는 시간복잡도가 256
    O(2^n) = 65,536 steps "(...)"
    
  • 위와 같은 시간복잡도 계산을 코드에 적용해봅니다.
    // 아래와 같은 데이터 구조 기준으로 시간복잡도를 적용해봅니다.
    var friends = {
    'Mark' : true,
    'Amy' : true,
    'Carl' : false,
    'Ray' :  true,
    'Laura' : false,
    }
    var sortedAges = [22, 24, 27, 29, 31]
    

O(1) — Constant Time (상수 시간)

  • 값을 검색할 때, 객체에서 키를 알거나 배열에서 인덱스를 알고 있으면 언제나 한 단계만 걸립니다.
    //If I know the persons name, I only have to take one step to check:
    function isFriend(name){ //similar to knowing the index in an Array
    return friends[name];
    };
    isFriend('Mark') // returns True and only took one step
    function add(num1,num2){ // I have two numbers, takes one step to return the value
    return num1 + num2
    }
    

O(log n) — Logarithmic Time (로그 시간)

  • 배열에서 값을 찾을 때, 어느 쪽에서 시작할지를 알고 있으면 검색하는 시간이 두배로 줄어듭니다.
    //You decrease the amount of work you have to do with each step
    function thisOld(num, array){
    var midPoint = Math.floor( array.length /2 );
    if( array[midPoint] === num) return true;
    if( array[midPoint]  only look at second half of the array
    if( array[midpoint] > num ) --> only look at first half of the array
    //recursively repeat until you arrive at your solution
    
    }
    thisOld(29, sortedAges) // returns true
    //Notes
    //There are a bunch of other checks that should go into this example for it to be truly functional, but not necessary for this explanation.
    //This solution works because our Array is sorted
    //Recursive solutions are often logarithmic
    //We'll get into recursion in another post!
    

O(2^n) — Exponential Time (지수 시간)

  • 지수 시간은 보통 문제를 풀기 위해 모든 조합과 방법을 시도할 때 사용됩니다.
    //The number of steps it takes to accomplish a task is a constant to the n power
    //Thought example
    //Trying to find every combination of varters for a password of length n
    

마무리

it’s hard to say there is a single “right” or “best” answer to these problems. But it is possible to say there are “better” or “worse” answers to a given problem.

  • 문제를 해결하려고 할 때마다 시간복잡도를 분석하는 습관을 들이면 좋은 개발자가 될 수 있습니다.
  • 엔지니어에게 있어서, 문제라는 것은 정답이나 최선의 답의 관점에서 접근하는 것보다, 상황에 더 맞는 답인지 아닌지의 관점에서 접근해야 합니다.
  • 마지막으로 한번 더 요약합니다.
    1. O(1) – 상수 시간 : 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다.
    2. O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듭니다.
    3. O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가집니다.
    4. O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱입니다.
    5. O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱입니다. (상당히 큰수가 됩니다)

넥슨 연습문제3 풀이 (Python)

지인의 요청으로 8월 23일에 공개된 넥슨 청소년 프로그래밍 챌린지 연습문제 3번을 풀기 위한 Python API와 자료구조 지식들을 정리해보았습니다.

list & tuple 이해

  • 데이터를 순차적으로 저장하는 저장소 (또는, 배열 & 자료구조)

input()

  • 파이썬 콘솔에 입력되는 값들을 인식하여 저장할 수 있다.
  • 사용법
    textinput = input() # 코딩하면, 아래에 입력 값을 받을 수 있게끔 줄 바뀜이 일어난다.
    'hello' # 원하는 문자열 값을 넣는다 (주의 : 따옴표 꼭 입력)
    print (textinput) # hello
    

split()

  • 해당 변수를 split() 의 괄호 안에 지정되는 값으로 쪼개어 list로 저장한다.
  • 사용법
    re = "dizni kephi"
    re.split()
    print (re) # ['dizni', 'kephi']
    

for in

  • 자주 쓰이는 반복문의 한 종류로 직관적인 것이 특징
  • 기본 구조
    for 변수 in 리스트(또는, 튜플 문자열 가능):
    수행할 문장1
    수행할 문장2
    

list 와 for

  • list 안에 for 문을 포함하면 편리하고 직관적이다.
    relations = [input().split() for y in range(10)] # range(10) 은 0부터 10 미만의 숫자인 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 를 포함하는 list 를 반환한다.
    
    # 문자열 입력값이 아래와 같을 때,
    # kephi dizni
    # bazzi gabriel
    # evan gabriel
    # marid evan
    # pungjin dizni
    # evan bazzi
    # marid fiona
    # fiona gabriel
    # pungjin kephi
    
    # 아래와 같은 형태로 relations에 저장된다.
    # [['kephi', 'dizni'], ['bazzi', 'gabriel'], ['evan', 'gabriel'], ['marid', 'evan'], ['pungjin', 'dizni'], ['evan', 'bazzi'], ['marid', 'fiona'], ['fiona', 'gabriel'], ['pungjin', 'kephi']]