[Udacity] Intro to Data Structures and Algorithms : Lesson #1. Introduction and Efficiency

*Udacity 의 Intro to Data Structures and Algorithms 강의 (무료) 를 수강하며 배운 내용을 정리할 목적으로 작성하는 글로, 그 어떤 금전적 지원도 받은 사실이 없음을 밝힙니다. 

*영어로 제공되는 강의를 듣고 한국어로 내용 정리를하는 포스팅이기에 강의의 내용을 100% 포함하고 있지 않을 수 있다는 점 참고 바랍니다. 원본 내용이 확인하고 싶으신 분들은 Udacity 에 회원가입 후 해당 강의를 수강 신청하시길 바랍니다. 

*포스팅 내용에 오류가 있을 시 댓글로 남겨주세요! 바로 수정하겠습니다. 

 

 

드디어 찾았다. 내 맘에 쏙 드는 강의. 이전부터 자료구조와 알고리즘을 듣고 싶었으나 대부분 자바같이 내가 잘 모르는 언어들로 과제가 나와서 미루고 있다가 최근 Udacity 에서 파이썬으로 진행되는 강의를 찾게 되었다. 심지어 무료다! 

 

곧 코드가 필요없어지는 시대가 올 텐데 뭐하러 귀찮고 힘든 길을 가냐는 의견이 있을 수 있지만, 개인적으로는 무대 뒤에서 어떤 일들이 진행되고 있는지 아는 것이 중요하다고 생각해서 망설임 없이 배우기로 했다. 

 

총 8강으로 구성된 과목의 1강을 듣고 있는 중인데, 앞으로 공부한 내용을 필요하다면 언제든지 찾아볼 수 있도록 블로그에 기록하려고 한다. 

 

---

1. 효율성 Efficiency 또는 복잡도 Complexity

 

CS 에서 '효율성' 이란 개념은 곧 어떤 코드 (혹은 프로그램) 가 실행 완료되기까지 얼만큼의 시간이 걸리는지, 어느 정도의 저장 공간 (space storage) 을 차지하는지를 말한다. 즉, 코드가 실행될 때 컴퓨터의 리소스를 얼마나 차지하는지를 의미한다. 당연히 같은 작업을 실행하는 코드라면 리소스를 최소로 사용하는 코드가 더 좋은 코드다.

그러나 모든 경우에 있어 실행 시간도 적게 걸리고, 메모리도 적게 사용하는 코드를 짜는 것은 어려운 일이다. 그러므로 종종 실행 시간과 메모리 사이에서 어떤 것을 더 우위에 둘지 선택 (trade-offs) 을 해야할 수도 있다. 

 

* 사족: 이 설명을 듣고 자료 구조와 알고리즘을 왜 배워야 하는지 이해할 수 있었다. 데이터를 어떤 그릇에 담아서 (자료구조) 어떤 방식으로(알고리즘) 처리를 하는 것이 가장 문제에 맞는 것인지 배울 수 있는 과목이기 때문이다. 다른 말로 표현하면, 효율적인 코드를 짜는 것이 '목표 goal' 라면 그 목표를 달성할 수 있게 해주는 '방법 how' 를 알려주는 과목이기 때문에 배워야 하는 것이다. 

 

 

- 표기법 (Notation) 기초 : O(n)

 

Big O notaion 이라고 읽으면 된다. 알고리즘의 효율성을 정량적 - 사실 대수적이라는 표현이 더 맞는지 아니면 그냥 객관적이라는 표현을 써야하는지 잘 모르겠다 - 으로 측정할 수 있는 방법이다. 

 

O(n) 에서 n 은 대수적 표현들이다. 예를 들면 O(1), O(log(n)), O(n^2) 이런 식이다. 이때 O(1) 이 왜 예시에 포함되어 있는지 궁금할 수 있는데, 1 = 0*n + 1 로 표현할 수 있기 때문이다. 

 

n 이 어떤 식으로 표기되는지는 알겠는데, 의미하는 바는 무엇일까? 바로 입력되는 데이터의 길이이다.

 

이제 아래의 예를 통해 시간 복잡도 time efficiency 를 이해해 보자. 

 

암호를 문자열의 형태로 입력받아 미리 정의한 암호표와 비교한 후 해당 암호가 어떤 의미인지 알려주는 함수를 정의한 의사 코드 pseudo code 이다. (글자색과 들여쓰기는 무시하고 읽길 바란다.)

function decode(input):
    create output string
    for each letter in input:  #한 글자씩 해독
    	get new_letter from letter's location in cipher  #암호표는 cipher 라는 이름으로 저장되어 있음
    	add new_letter to output  #해독 완료한 글자를 output 에 순차적으로 포함시키기
    return output

 함수가 1번 실행될 때 create output string 과 return output 은 각각 1번씩만 실행되는 코드이다. 따라서, 이점을 반영하여  O( ___ + 2) 라고 (이유: create 으로 시작하는 코드 1줄 + return 으로 시작하는 코드 1줄) 우선 쓸 수 있다. 다음으로, 입력받은 문자열에 n 개의 글자가 있다고 할 때, 함수 1번 실행 시 for 문 안에 있는 코드 2줄은 더 읽을 글자가 없을 때까지 계속 실행된다. 따라서 O(2*n + 2) 라고 쓸 수 있다. (이유: 글자 n 개 * 글자 1개 당 코드 2줄) 

 

시간 복잡도를 구하면, O(2*n + 2) 에 코드의 1회 실행 시간이다. 예를 들어 위 함수가 1번 실행되는데 1초가 걸리고, 입력받은 문자열이 10개의 글자로 이루어져 있다면 시간 복잡도는 22 계산 횟수 *1초 = 22초가 된다. (이유: 글자가 10개이므로 O(2*n + 2) 의 n 에 10 대입)

 

- 표기법 (Notation) 계속

 

바로 윗 단락까지가 기초 중의 기초에 해당하는 내용이었는데, 사실 O(n) 을 잘못 썼다. 왜냐하면, for 문을 빼먹었기 때문이다. for 문이 입력받은 문자열에서 글자를 1개씩 가져올 때, 바로 다음에 어떤 글자를 가져올지에 대한 계산이 이루어지므로 O((2+1)*n + 2) = O(3*n + 2) 으로 쓰는 것이 맞다. 

 

여기서 안심해도 될까? 아니다. 암호문을 저장한 cipher 가 남아있다...! 예를 들어 해독을 하려는 문자열이 영어 알파벳이라고 생각할 때 cipher 에는 26개의 알파벳이 어떤 암호 표시에 대응하는지에 대한 정보를 담고 있을 것이다.  그럼 함수가 1번 실행될 때, for 문 바로 아래의 get new_letter from letter's location in cipher 코드는 최대 26번의 대조 작업을 할 수도 있는 것이다. 이 경우 O(n) 은 O((3+26)*n + 2) = O(29*n + 2) 이 된다. 10개 글자로 이루어진 암호 문자열을 입력했을 때 시간 복잡도를 계산하면 292초가 된다. (함수 실행 완료까지 걸리는 시간은 1초로 동일)

 

 

- 최악의 경우와 근사법 Worst Case and Approximation

 

<표기법 (Notation) 계속> 에서 확인한 것처럼, O(3*n + 2) 라는 복잡도 표현식은 상황에 따라 달라질 수 있다. 따라서 보통의 경우, 예를 들어 개발자 코딩 면접에서는 계수나 상수까지 구체적으로 포함한 복잡도를 구할 수 있는지 묻지 않고, 대신 근사식으로  표현할 수 있는지를 확인한다고 한다. 이를테면 O(29*n + 2) 대신 O(n) 라고 쓰는 것이다. 

 

 사실 코드의 효율성(복잡도)에 대해 언급할 수 있는 방법에는 3가지가 있는데, 첫번째는 Best Case 를 가정하는 경우고 두번째는 Average Case 를 가정하는 경우, 그리고 마지막으로는 Worst Case 를 가정하는 경우이다. O(29*n + 2) 는 최악의 경우, 즉 암호 문자열 내의 글자를 cipher 의 알파벳과 26번 대조하게 되는 상황을 가정하고 도출한 값이다. 만약 평균적인 경우를 가정한다면, 보통 13번의 대조를 통해 대응되는 알파벳이 무엇인지 알게 될 것이므로 O(16*n + 2) 를 복잡도라고 할 것이다. 

 

수업에서는 시간 복잡도를 주로 다루었는데, '공간 복잡도' 라는 개념도 존재한다. 예를 들어, 문자열을 입력받아 3번 복사하는 작업을 한다고 할 때, 공간 복잡도는 O(3*n) 과 같이 표현된다. 

 

---

이상 1강에서 배운 효율성(복잡도)의 정리를 마친다! 과연 언제 완강을 할 수 있을지 기대된다. (두근)