이번에 살펴볼 정렬 알고리즘은 "Heap Sort(힙 정렬)"이다.

 

[출처] ChatGPT + WHATWANT

 

보통은 위키피디아의 animated-gif 를 통해서 정렬 알고리즘을 엿볼 수 있었는데,

heap-sort 경우에는 도저히 파악이 안되는 내용이라 다른 자료를 찾아봤다. (내가 무지해서 이해를 못한 것이겠지...)

 

[출처] https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

 

너무나 친절한 Visualization을 제공해주는 곳은 다음과 같다.

- https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

- 왼쪽 상단의 "Heap Sort" 버튼을 클릭하면 animation을 보여준다.

 

[출처] https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

 

왜 저렇게 정렬이 되는지 바로 이해가 되시는 분은 그만 공부하셔도 된다!!! ^^

 

사실 공부하기 전에는 대체 어떤 이유로 이렇게 움직이는 것인지 잘 보이지 않아야 정상일 것 같다 ^^

우리에게 필요한건?

 

공부!!!

 

Heap Sort를 알기 위해서는 일단 Heap이 무엇인지 부터 알아야 한다.

 

⑴ Heap의 정의

⑵ MAX-HEAPIFY()

⑶ BUILD-MAX-HEAP()

⑷ HEAP-SORT

 

 

⑴ Heap

Heap은 2가지의 속성을 갖고 있다. 이에 대해서 알아보자.

 

  ① A nearly complete binary tree

  ② max-heap

 

① A nearly complete binary tree

일단 tree 구조와 관련한 용어부터 확인해야 이야기가 쉬울 것 같다.

 

[출처] https://www.whatwant.com

 

tree 관련한 용어들이 더 있지만, 일단 이 정도만 알아도 될 것 같다.

 

그러면, tree 구조 관련하여  "complete binary tree"가 뭔지부터 파악하고

"nearly complete binary tree"가 뭔지 이해해보도록 하자.

 

[출처] https://www.whatwant.com

 

▷ Complete Binary Tree

  - all leaves the same depth

  - all internal nodes have degree 2

 

그러면 nearly complete binary tree는 어떻게 생겼을까!?

 

[출처] https://www.whatwant.com

 

▷ A Nearly Complete Binary Tree

  - 기본적으로는 Complete Binary Tree 구조를 갖고자 

  - all internal nodes have degree 2, but 마지막 leaf는 1개가 부족할 수 있다.

  - 마지막 depth의 leaves는 왼쪽부터 차례대로 배치

 

 

우리가 공부하고자 하는 Heap 구조는 바로 이 "nearly complete binary tree"를 따르고 있다.

 

왜 그럴까!?

 

▷ Array

 

"nearly complete binary tree" 구조를 따를 경우에 이를 array 방식으로 표현하기가 쉽기 때문이다.

반대로 말하면 array를 사용하기 위해서는 nearly complete binary tree 구조여야 한다!!!

 

[출처] https://www.whatwant.com

 

이렇게 되면 어떤 장점이 있을까?

 

[출처] https://www.whatwant.com

 

그렇다 ! 위치에 대한 계산이 가능해진다 !!!

 

여기에서 하나 더 확인해볼 것은 "The height of a heap"이다.

 

▷ The height of a heap

  - 기본적으로 height는 depth와 같은 개념이고, 특정 node를 기준으로 depth가 얼마인지를 의미한다.

  - The height of a heap = The height of the root : 그러면 depth의 의미이다.

  - 그러면, 여기에서 질문 하나

    : 어떤 Heap의 전체 node의 갯수(n)를 알면 height가 얼마인지 알 수 있을까?

 

[출처] https://www.whatwant.com

 

  - height를 h라고 하면, 다음과 같다.

 

[출처] https://www.whatwant.com

 

② max-heap

'binary heap'은 max-heaps와 min-heaps의 2가지 종류가 있다.

 

앞에서는 tree 구조에 대해서만 이야기 했지, 각 node에 들어있는 값에 대해서 이야기하지 않았다.

이제는 각 node에 들어있는 값에 대한 이야기이다.

 

[출처] https://www.whatwant.com

 

위 그림을 보고 오해를 하면 안된다.

당연하게도 모든 parent-child 를 살펴봐도 모두 저 관계를 만족해야 한다.

 

그러면 제일 위의 root node에 들어있는 값은 전체 모든 node 중에서 가장 큰 값이 위치하게 된다.

 

min-heap은 반대이다. root node가 가장 작은 값을 갖는다.

 

우리는 보통 max-heap을 사용한다.

 

 

⑵ MAX-HEAPIFY()

"Max-Heapify" 함수에 대해서 알아보겠다.

함수이기에 입력(input)과 출력(output)이 있고, 그 과정에서 어떤 처리(processing)이 있을 것이다.

 

① input

  - 입력은 어떤 하나의 node가 된다.

 

[출처] https://www.whatwant.com

 

   - 단, 그 노드가 갖고 있는 왼쪽/오른쪽의 subtree들이 이미 max-heap 구조를 갖고 있어야 한다.

 

② float down

  - "4" node를 기준으로 왼쪽/오른쪽 subtree가 각각 max-heap이기에 max-heapify 가능

  - 그래서 "4" 값과 "14"값을 exchange

  - 그런데, "4" node를 봤더니 max-heap 상태가 아님

  - subtree 들은 각각 max-heap 상태이기에 max-heapify 실행

  - 그래서 "4"와 "8"값 exchange

  - 그랬더니, 처음 "4"에서 실행한 max-heapify가 전체적으로 이루어짐

 

[출처] https://www.whatwant.com

 

이렇게 밑으로 흘러가듯이 이루어지는 과정을 "float down"이라고 

 

③ running time

  - max-heapify의 running time을 알아보자.

 

[출처] https://www.whatwant.com

 

 

⑶ BUILD-MAX-HEAP()

max-heap을 만드는 것에 대한 Pseudo Code를 살펴봅시다!!!

 

[출처] https://www.whatwant.com

 

Text에서 floor 함수 표기가 쉽지 않아 조금 이상하게 보이는 부분은 이해해주시길 바라옵니다 ^^

 

일단 A는 max-heap을 하고자 하는 입력 데이터를 의미한다.

 

[출처] https://www.whatwant.com

 

그러면, 밑의 순환문은 어떤 의미일까!?

 

[출처] https://www.whatwant.com

 

그러므로, 순환문의 시작 위치는 다음과 같다.

 

[출처] https://www.whatwant.com

 

그 다음 index가 하나씩 감소하기 때문에 다음과 같은 흐름으로 진행하게 된다.

 

[출처] https://www.whatwant.com

 

전체 길이의 절반 위치에서 시작하는 것은 그 이후의 node는 edge-node 즉, leaves 들이기 때문에

이미 max-heapify가 되어 있어서 굳이 max-heapify를 할 필요가 없는 것이다.

 

▷ Running time

① Upper bound

  - Pseudo code를 기반으로 해서 찬찬히 살펴보면 다음과 같이 실행 시간(횟수)를 확인할 수 있다.

 

[출처] https://www.whatwant.com

 

이를 계산하면 다음과 같이 정리가 된다.

 

[출처] https://www.whatwant.com

 

 

② Tighter bound

 

그런데, 실제로 분석해보면 이는 지나친 upper-bound라고 볼 수 있다.

즉, 이것 보다는 조금 더 tighter-bound를 계산해볼 수 있는 것이다.

 

1번 node 기준으로 max-heapify를 한다고 했을 때, "n = 10" 이므로 O(log 10) 소요시간이 걸린다.

그러면, 5번 node 기준으로 max-heapify를 하면 소요시간이 얼마나 걸릴까?

 

[출처] https://www.whatwant.com

 

5번 node 위치에서의 "n = 2" 이므로 O(log 2) 소요시간이 걸린다.

4번 node 위치에서는 O(log 3), 3번 node 위치에서도 O(log 3) 이다.

 

즉, 실제로 많은 node에서 소요되는 시간이 우리가 계산한 O(log n) 값보다 작다는 것이다.

 

[출처] https://www.whatwant.com

 

이걸 고려해서 계산을 해보면 다음과 같다.

 

[출처] https://www.whatwant.com

 

엇?! 선형(linear)으로 정리가 되었다 !!!

 

⑷ HEAP-SORT

이제 마무리 단계에 왔다.

앞에서 공부한 것들을 모두 모아서 정렬하는데에 어떻게 사용할 수 있는지 Pseudo Code로 살펴보자.

 

[출처] https://www.whatwant.com

 

응!? 이건 뭔가 싶다.

 

▷ Extract-Max

  - BUILD-MAX-HEAP() 실행을 마치면, root-node에 있는 값이 가장 큰 값이 되게 된다.

 

[출처] https://www.whatwant.com

 

  - root-node에 있는 값을 제일 뒤에 있는 node와 교환을 한다.

  - 제일 뒤에 있는 node를 제외한 tree를 가지고, root-node에서 MAX-HEAPFY()를 실행한다.

  - 이 방식 가능한 이유는 이미 BUILD-MAX-HEAP()을 통해, 그 밑의 subtree들이 max-heap 상태이기 때문이다.

 

 

▷ Running Time

  - Pseudo Code를 가지고 수행 시간을 살펴보자.

 

[출처] https://www.whatwant.com

 

  - Worst-case는 이렇게 되겠지만, Best-case는? 모든 것이 같은 값일 때 !!!

  - 5번 라인의 경우 값이 하나씩 줄어들기 때문에, 시간이 조금씩 더 적게 들겠지만 유의미하지는 않다.

  - 결론적으로 Heap-Sort의 Running Time은 다음과 같이 정리할 수 있다.

 

[출처] https://www.whatwant.com

 

▷ Memory

  - Heap-Sort는 추가적인 메모리가 필요하지 않은 in-place 알고리즘이다.

  - 별도의 메모리 공간이 아니라 node 사이의 값을 exchange하는 것으로 처리되기 때문이다.

 

 

우아앙~ 너무 힘들었다.

반응형

Chapter 02

 

▶ 요약

2-1 API 사용하기
https://www.youtube.com/watch?v=s_-VvTLb3gs&ab_channel=한빛미디어

JSON (Javascript Object Notation)
- JSON ≒ Dictionay + List
- import json
  . json.dumps()
  . json.loads()
- import pandas as pd
  . pd.read_json()

XML (eXtensible Markup Language)
- import xml.etree.ElementTree as et
  . et.fromstring()
  . *.findtext()
  . *.findall()

API (Application Programming Interface)
- import requests
  . r = requests.get(url)
  . data = r.json()

2-2 웹 스크래핑 사용하기
https://www.youtube.com/watch?v=Il6L8OtNFpc&ab_channel=한빛미디어

BeautifulSoup()
- find()
- find_all()

DataFrame의 행과 열
- loc()
  . *.loc[[0,1], ['bookname':'authors']]
  . *.loc[0:1, 'bookname':'authors']
    : DataFrame에서의 slicing은 마지막 값을 포함한다. (일반적으로는 포함하지 않는다)

 

 

▶ 기본 미션

p150의 확인 문제 1번 풀고 인증하기

 

□ 다음과 같은 데이터  프레임 df가 있을 때 loc 메서드의 결과가 다른 하나는 무엇인가요?

 

 

① df.loc[[0, 1, 2], ['col1', 'col2']]

② df.loc[0:2, 'col1':'col2']

③ df.loc[:2, [True, True]]

④ df.loc[::2, 'col1':'col2']

 

 

보기를 잘 살펴보면 ①, ②는 그냥 보면(?) 되고 ^^ 답은 ③, ④ 중 하나가 될 것이라는 것을 직감적으로 알 수 있다 !!!

③번을 실제 해보면 다음과 같이 출력이 된다.

 

 

응?! 'True' 가 도대체 어떻게 반응한다는 거지!? 해당 Column을 포함할지 안할지를 지정하는 것인가!?

그러면 조금 다른 사례를 확인해보자 !!!

 

 

그렇다!!! 가설이 맞았다. 3개의 Columns에 대해서 [참, 거짓, 참]으로 했더니 정말로 그렇게 출력이 되었다.

 

그러면, 정답은 ④이어야 하는데, 한 번 살펴보자.

 

 

'::2'라고 했기 때문에 하나씩 건너뛰라고 했기 때문에 0번행, 2번행만 출력이 되고 있다.

 

 

▶ 선택 미션

p. 137 ~ 138 손코딩 실습으로 원하는 도서의 페이지 수를 추출하고 화면 캡쳐하기.

 

① 온라인 서점의 검색 결과 페이지 URL을 만듭니다.

② requests.get() 함수로 검색 결과 페이지의 HTML을 가져옵니다.

③ BeautifulSoup로 HTML을 파싱합니다.

BeautifulSoup의 find() 메서드로 <a> 태그를 찾아 상세 페이지 URL을 추출합니다.

⑤ requests.get() 함수로 다시 도서 상세 페이지의 HTML을 가져옵니다.

⑥ BeautifulSoup로 HTML을 파싱합니다.

⑦ BeautifulSoup의 find() 메서드로 '품목정보' <div> 태그를 찾습니다.

⑧ BeautifulSoup의 find_all() 메서드로 '쪽수'가 들어있는 <tr> 태그를 찾습니다.

⑨ 앞에서 찾은 테이블의 행에서 get_text() 메서드로 <td> 태그에 들어있는 '쪽수'를 가져옵니다.

 

 

개인적으로 최근에 주로 사용하는 온라인서점이 알라딘이라서 이번 미션을 알라딘으로 해보고자 한다 ^^

 

 

URL 부분을 더 자세히 살펴보자.

 

 

응?! isbn이 아니라 Item-ID 으로 구성이 되네!?

혹시... isbn으로도 되지 않을까!?

 

 

된다 !!! ^^

어!? 그런데, 책을 다시 한 번 잘 살펴보니... 검색으로 조회 후에 상세 페이지 주소를 얻어서 진행하는 것이네...

다시 !!!

 

 

어짜피 검색에 isbn을 사용한다면

실무에서는 바로 상세페이지로 접근을 하겠지만, 우리는 공부중이니 일단 검색부터 진행해보겠다.

 

앞에서 확인한 URL을 가지고 시작했다.

 

상세 페이지 링크가 책 제목 부분에 붙어 있으므로 아래와 같은 HTML Tag 부분을 잡아내면 된다.

 

<a href="https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=329721455" class="bo3"><b>재미있는 게임 제작 프로세스</b></a>

 

아래와 같이 코딩해봤다.

 

 

여기에 있는 href 값을 이용해서 다음 웹페이지를 읽어오면 된다.

 

 

여기에서 잡아내야 하는 것은 페이지 정보이니 아래와 같은 HTML Tag 부분을 잡아내면 된다.

 

<div class="conts_info_list1"><ul><li>432쪽</li><li>188*257mm (B5)</li><li>821g</li><li>ISBN : 9788931469721</li></ul></div>

 

 

잘 살펴보면 <li> 태그 부분이 보일 것이다.

 

 

쪽 정보까지 잘 뽑아냈다~!!!

 

우리 모두 파이팅 !!!

반응형

 

최근 특히 AI 관련한 개발 업무를 하게 되면서 Anaconda를 필요로 하는 경우가 많다.

 

https://www.anaconda.com/

 

그런데, 문제는 ... 라이선스 이슈가 있기에 회사에서 사용하려면 주의를 해야 한다.

 

"어?! 오픈소스 아니야?"

 

라고 생각하는 분들이 많을 것 같은데,

홈페이지 주소를 보면 알겠지만 Anaconda는 300명 이상의 임직원을 보유하고 있는 회사다.

 

하지만, 아주 선량하게도 오픈소스 커뮤니티도 유지하면서

오픈소스 프로젝트나 교육 기관 등에서 무료로 사용할 수 있도록 해주고 있다.

 

Pricing

 

그런데, 문제는 저기 보이는 "Free" 요금제의 조건이다.

 

Free Plans

 

200명 이상의 임직원이 있는 곳이라면 .... 무료로 사용하면 안된다.

조금 더 자세히 살펴보자.

 

https://www.anaconda.com/blog/anaconda-commercial-edition-faq

 

2020년도에 (아마도 먹고 살기 위해) 서비스 약관을 변경했다.

200명 이상 규모의 회사에서 사용하기 위해서는 Enterprise Edition을 사용해야 한다.

 

그런데, 더 자세히 살펴보기 바란다.

 

"Anaconda vs. Anaconda's repositories"

 

Anaconda를 사용하는 것이 문제가 아니라

Anaconda의 저장소를 사용하는 것이 문제란다.

 

어!? 그러면 Anaconda' s repositories를 사용하지 않으면 되는 것 아닌가?!

 

https://www.anaconda.com/about-us

 

CEO이자 창립자인 피터 왕 형님(?)이 reddit에서 직접 그냥 대놓고 방법을 알려주셨다.

 

https://www.reddit.com/r/Python/comments/iqsk3y/comment/g4xuabr/

 

Miniconda + conda-forge 조합으로 사용하면

Anaconda의 commercial 약관에 영향을 받지 않는다.

 

결론 !!!

200명 이상 임직원을 보유하고 있는 회사에서는 Miniconda + conda-forge 조합으로 설치해서 사용하면 된다.

 

▶ Miniconda

쓸데 없는 패키지 설치 없이 깔끔하게 설치되는 가벼운 conda 이다.

 

https://docs.conda.io/projects/miniconda/en/latest/

 

Ubuntu 환경에서 설치하는 과정을 살펴보겠다.

❯ mkdir -p ~/miniconda3

❯ wget https://repo.anaconda.com/miniconda/Miniconda3-latest-Linux-x86_64.sh -O ~/miniconda3/miniconda.sh
--2024-01-10 23:13:40--  https://repo.anaconda.com/miniconda/Miniconda3-latest-Linux-x86_64.sh
repo.anaconda.com (repo.anaconda.com) 해석 중... 104.16.130.3, 104.16.131.3, 2606:4700::6810:8203, ...
다음으로 연결 중: repo.anaconda.com (repo.anaconda.com)|104.16.130.3|:443... 연결했습니다.
HTTP 요청을 보냈습니다. 응답 기다리는 중... 200 OK
길이: 141613749 (135M) [text/x-sh]
저장 위치: `/home/chani22/miniconda3/miniconda.sh'

/home/chani22/miniconda3/miniconda.sh        100%[==============================>] 135.05M  57.3MB/s    / 2.4s     

2024-01-10 23:13:43 (57.3 MB/s) - `/home/chani22/miniconda3/miniconda.sh' 저장함 [141613749/141613749]


❯ bash ~/miniconda3/miniconda.sh -b -u -p ~/miniconda3
PREFIX=/home/chani22/miniconda3
Unpacking payload ...
                                                                                                               
Installing base environment...


Downloading and Extracting Packages:


Downloading and Extracting Packages:

Preparing transaction: done
Executing transaction: done
installation finished.

❯ rm -rf ~/miniconda3/miniconda.sh

❯ ~/miniconda3/bin/conda init zsh
no change     /home/chani22/miniconda3/condabin/conda
no change     /home/chani22/miniconda3/bin/conda
no change     /home/chani22/miniconda3/bin/conda-env
no change     /home/chani22/miniconda3/bin/activate
no change     /home/chani22/miniconda3/bin/deactivate
no change     /home/chani22/miniconda3/etc/profile.d/conda.sh
no change     /home/chani22/miniconda3/etc/fish/conf.d/conda.fish
no change     /home/chani22/miniconda3/shell/condabin/Conda.psm1
no change     /home/chani22/miniconda3/shell/condabin/conda-hook.ps1
no change     /home/chani22/miniconda3/lib/python3.11/site-packages/xontrib/conda.xsh
no change     /home/chani22/miniconda3/etc/profile.d/conda.csh
modified      /home/chani22/.zshrc

==> For changes to take effect, close and re-open your current shell. <==  

 

마지막의 init은 새로운 버전으로 업데이트하거나 했을 때 초기화 하는 것인데 그냥 첫 설치 때도 해봤다.

bash 쓰시는 분들은 뒤의 zsh 부분을 바꿔치기하면 된다.

 

 

▶ conda-forge

conda가 설치되면 기본적으로 등록되어 있는 channel은 "https://repo.anaconda.com/pkgs/" 이다.

저 저장소가 바로 문제가 되는 최종 사용자 라이선스 계약(EULA) 항목이 존재하는 곳이다.

- https://legal.anaconda.com/policies/en/?name=end-user-license-agreement#end-user-license-agreement

 

그러면 conda-forge는 무엇일까?

 

https://conda-forge.org/

 

community 리딩의 많은 기여자들의 활발한 참여로 운영되는 저장소이다.

 

정말 많은 패키지들이 등록되고 있고 그렇다보니

Anaconda의 공식 저장소보다 더 많은 패키지들이 존재하기에 commercial 이슈가 아니더라도

일부러 conda-forge를 저장소로 등록해서 사용자들도 많다고 한다.

 

conda에서는 이러한 저장소를 channel이라는 용어를 사용하고 있다.

❯ conda config --add channels conda-forge

❯ conda config --set channel_priority strict

❯ conda config --show channels
channels:
  - conda-forge
  - defaults

 

끝이다.

 

말이 좀 많았는데 실제로 손으로 직접 해야하는 것은 별 것 없다.

이걸로 compliance 이슈를 하나 해결할 수 있다 ^^

 

 

그러면, 실습을 하나 해보자 !!!

 

▶ Jupyter Notebook 실행하기

 

① 가상환경 생성하기

명령어 실행하는 위치는 어디든 무관하다.

❯ conda create -n python_39 python=3.9.15
Channels:
 - conda-forge
 - defaults
Platform: linux-64
Collecting package metadata (repodata.json): done
Solving environment: done

## Package Plan ##

  environment location: /home/chani22/miniconda3/envs/python_39

  added / updated specs:
    - python=3.9.15


The following packages will be downloaded:

    package                    |            build
    ---------------------------|-----------------
    _libgcc_mutex-0.1          |      conda_forge           3 KB  conda-forge
    _openmp_mutex-4.5          |            2_gnu          23 KB  conda-forge
    bzip2-1.0.8                |       hd590300_5         248 KB  conda-forge
    ca-certificates-2023.11.17 |       hbcca054_0         151 KB  conda-forge
    ld_impl_linux-64-2.40      |       h41732ed_0         688 KB  conda-forge
    libffi-3.4.2               |       h7f98852_5          57 KB  conda-forge
    libgcc-ng-13.2.0           |       h807b86a_3         755 KB  conda-forge
    libgomp-13.2.0             |       h807b86a_3         412 KB  conda-forge
    libnsl-2.0.1               |       hd590300_0          33 KB  conda-forge
    libsqlite-3.44.2           |       h2797004_0         826 KB  conda-forge
    libuuid-2.38.1             |       h0b41bf4_0          33 KB  conda-forge
    libzlib-1.2.13             |       hd590300_5          60 KB  conda-forge
    ncurses-6.4                |       h59595ed_2         864 KB  conda-forge
    openssl-3.2.0              |       hd590300_1         2.7 MB  conda-forge
    pip-23.3.2                 |     pyhd8ed1ab_0         1.3 MB  conda-forge
    python-3.9.15              |hba424b6_0_cpython        21.0 MB  conda-forge
    readline-8.2               |       h8228510_1         275 KB  conda-forge
    setuptools-69.0.3          |     pyhd8ed1ab_0         460 KB  conda-forge
    tk-8.6.13                  |noxft_h4845f30_101         3.2 MB  conda-forge
    tzdata-2023d               |       h0c530f3_0         117 KB  conda-forge
    wheel-0.42.0               |     pyhd8ed1ab_0          56 KB  conda-forge
    xz-5.2.6                   |       h166bdaf_0         409 KB  conda-forge
    ------------------------------------------------------------
                                           Total:        33.5 MB

The following NEW packages will be INSTALLED:

  _libgcc_mutex      conda-forge/linux-64::_libgcc_mutex-0.1-conda_forge 
  _openmp_mutex      conda-forge/linux-64::_openmp_mutex-4.5-2_gnu 
  bzip2              conda-forge/linux-64::bzip2-1.0.8-hd590300_5 
  ca-certificates    conda-forge/linux-64::ca-certificates-2023.11.17-hbcca054_0 
  ld_impl_linux-64   conda-forge/linux-64::ld_impl_linux-64-2.40-h41732ed_0 
  libffi             conda-forge/linux-64::libffi-3.4.2-h7f98852_5 
  libgcc-ng          conda-forge/linux-64::libgcc-ng-13.2.0-h807b86a_3 
  libgomp            conda-forge/linux-64::libgomp-13.2.0-h807b86a_3 
  libnsl             conda-forge/linux-64::libnsl-2.0.1-hd590300_0 
  libsqlite          conda-forge/linux-64::libsqlite-3.44.2-h2797004_0 
  libuuid            conda-forge/linux-64::libuuid-2.38.1-h0b41bf4_0 
  libzlib            conda-forge/linux-64::libzlib-1.2.13-hd590300_5 
  ncurses            conda-forge/linux-64::ncurses-6.4-h59595ed_2 
  openssl            conda-forge/linux-64::openssl-3.2.0-hd590300_1 
  pip                conda-forge/noarch::pip-23.3.2-pyhd8ed1ab_0 
  python             conda-forge/linux-64::python-3.9.15-hba424b6_0_cpython 
  readline           conda-forge/linux-64::readline-8.2-h8228510_1 
  setuptools         conda-forge/noarch::setuptools-69.0.3-pyhd8ed1ab_0 
  tk                 conda-forge/linux-64::tk-8.6.13-noxft_h4845f30_101 
  tzdata             conda-forge/noarch::tzdata-2023d-h0c530f3_0 
  wheel              conda-forge/noarch::wheel-0.42.0-pyhd8ed1ab_0 
  xz                 conda-forge/linux-64::xz-5.2.6-h166bdaf_0 


Proceed ([y]/n)? 


Downloading and Extracting Packages:
                                                                                                                                                                                   
Preparing transaction: done                                                                                                                                                        
Verifying transaction: done                                                                                                                                                        
Executing transaction: done                                                                                                                                                        
#                                                                                                                                                                                  
# To activate this environment, use                                                                                                                                                
#                                                                                                                                                                                  
#     $ conda activate python_39                                                                                                                                                   
#                                                                                                                                                                                  
# To deactivate an active environment, use                                                                                                                                         
#                                                                                                                                                                                  
#     $ conda deactivate                                                                                                                                                           
  

 

② 가상환경 활성화 하기

친절하게 앞에서 알려준대로 실행하면 된다.

❯ conda activate python_39

 

③ 패키지 설치

❯ pip install jupyter notebook ipykernel
Collecting jupyter
  Downloading jupyter-1.0.0-py2.py3-none-any.whl (2.7 kB)
Collecting notebook
  Downloading notebook-7.0.6-py3-none-any.whl.metadata (10 kB)
Collecting ipykernel
  Downloading ipykernel-6.28.0-py3-none-any.whl.metadata (6.0 kB)
Collecting qtconsole (from jupyter)
  Downloading qtconsole-5.5.1-py3-none-any.whl.metadata (5.1 kB)

...  

 

④ 가상환경과 Jupyter Notebook 연결

❯ python -m ipykernel install --user --name python_39 --display-name python_39
Installed kernelspec python_39 in /home/chani22/.local/share/jupyter/kernels/python_39

 

⑤ Jupyter Notebook 실행

❯ jupyter notebook
[W 2024-01-11 00:29:46.408 ServerApp] A `_jupyter_server_extension_points` function was not found in jupyter_lsp. Instead, a `_jupyter_server_extension_paths` function was found and will be used for now. This function name will be deprecated in future releases of Jupyter Server.
[W 2024-01-11 00:29:46.429 ServerApp] A `_jupyter_server_extension_points` function was not found in notebook_shim. Instead, a `_jupyter_server_extension_paths` function was found and will be used for now. This function name will be deprecated in future releases of Jupyter Server.
[I 2024-01-11 00:29:46.429 ServerApp] jupyter_lsp | extension was successfully linked.
[I 2024-01-11 00:29:46.432 ServerApp] jupyter_server_terminals | extension was successfully linked.
[I 2024-01-11 00:29:46.435 ServerApp] jupyterlab | extension was successfully linked.
[I 2024-01-11 00:29:46.439 ServerApp] notebook | extension was successfully linked.
[I 2024-01-11 00:29:46.440 ServerApp] Writing Jupyter server cookie secret to /home/chani22/.local/share/jupyter/runtime/jupyter_cookie_secret
[I 2024-01-11 00:29:46.604 ServerApp] notebook_shim | extension was successfully linked.
[I 2024-01-11 00:29:46.618 ServerApp] notebook_shim | extension was successfully loaded.
[I 2024-01-11 00:29:46.619 ServerApp] jupyter_lsp | extension was successfully loaded.
[I 2024-01-11 00:29:46.620 ServerApp] jupyter_server_terminals | extension was successfully loaded.
[I 2024-01-11 00:29:46.621 LabApp] JupyterLab extension loaded from /home/chani22/miniconda3/envs/python_39/lib/python3.9/site-packages/jupyterlab
[I 2024-01-11 00:29:46.621 LabApp] JupyterLab application directory is /home/chani22/miniconda3/envs/python_39/share/jupyter/lab
[I 2024-01-11 00:29:46.622 LabApp] Extension Manager is 'pypi'.
[I 2024-01-11 00:29:46.624 ServerApp] jupyterlab | extension was successfully loaded.
[I 2024-01-11 00:29:46.625 ServerApp] notebook | extension was successfully loaded.
[I 2024-01-11 00:29:46.626 ServerApp] Serving notebooks from local directory: /srv/workspace/python_39
[I 2024-01-11 00:29:46.626 ServerApp] Jupyter Server 2.12.3 is running at:
[I 2024-01-11 00:29:46.626 ServerApp] http://localhost:8888/tree?token=5ed486a3d676270879b3684991a11b4932c981c265dddef4
[I 2024-01-11 00:29:46.626 ServerApp]     http://127.0.0.1:8888/tree?token=5ed486a3d676270879b3684991a11b4932c981c265dddef4
[I 2024-01-11 00:29:46.626 ServerApp] Use Control-C to stop this server and shut down all kernels (twice to skip confirmation).
[C 2024-01-11 00:29:47.025 ServerApp] 
    
    To access the server, open this file in a browser:
        file:///home/chani22/.local/share/jupyter/runtime/jpserver-4428-open.html
    Or copy and paste one of these URLs:
        http://localhost:8888/tree?token=5ed486a3d676270879b3684991a11b4932c981c265dddef4
        http://127.0.0.1:8888/tree?token=5ed486a3d676270879b3684991a11b4932c981c265dddef4
[I 2024-01-11 00:29:47.041 ServerApp] Skipped non-installed server(s): bash-language-server, dockerfile-language-server-nodejs, javascript-typescript-langserver, jedi-language-server, julia-language-server, pyright, python-language-server, python-lsp-server, r-languageserver, sql-language-server, texlab, typescript-language-server, unified-language-server, vscode-css-languageserver-bin, vscode-html-languageserver-bin, vscode-json-languageserver-bin, yaml-language-server

 

웹브라우저가 실행되면서 Jupyrt Notebook이 등장한다!!!

Jupyter Notebook

 

새로운 파일을 하나 생성해보자.

New - Notebook

 

기본 kernel도 보이지만,

우리가 만들어낸 python_39 도 보인다.

Select Kernel

 

개발자라면 외쳐요. Hello ~ !!!

Hello

 

오른쪽 상단 즈음에 보이는 JupyterLab 버튼은 뭐지?

JupyrtLab

 

응?! 이건 Colab ???? ^^

 

 

즐거운 회사 생활 !!!

반응형

최근 개발 관련 커뮤니티 여기 저기에서 언급되는

재미있고 쓸만한 유틸리티가 하나 등장해서 한 번 설치해서 써봤다.

 

https://heynote.com/

 

많은 개발자들이 칭찬을 하는 여러가지 특징을 살펴보자 !!!

 

① 오픈소스 프로젝트

갑자기 변심할지 모르겠지만, 일단 현재 GitHub에 소스코드가 모두 공개되어 있다.

 

https://github.com/heyman/heynote

 

라이선스를 살펴보니 최근 많은 프로젝트에서 적용하고 있는 "Common Clause" 라이선스를 적용하고 있다.

상업용으로 사용하는 것이 아니면 개인적으로 사용하는데에는 문제가 없을 것 같다.

 

LICENSE

 

② Mac / Win / Linux 모두 지원

기본 업무 환경은 Windows를 사용하고, 개발할 때에는 Linux를 사용하고,

취미 생활 할 때에는 Mac을 사용할 때 모두 Heynote를 설치해서 사용할 수 있다 ^^

 

Downloads

 

심지어 Mac은 갖가지 환경을 모두 지원한다.

아쉬운 것은 서로 Sync까지 되면 좋을 것 같기는 한데.... 기본 기능으로 제공해주진 않는다 ^^

 

③ 블록 단위 텍스트 버퍼

Jupyter Notebook을 써보신 분들은 조금 익숙할 수 있는 여러 블록으로 구성된 하나의 화면을 제공해준다.

 

Heynote

 

하나의 텍스트 버퍼이지만, 여러 유형을 나누어서 구성할 수 있다.

 

④ 멀티 포맷 지원

각 블록은 여러 유형의 Syntax Highlighting과 자동 포맷을 지원한다.

 

Language

 

Sample로 제공하는 것을 보면 알 수 있지만,

특별한 유형으로는 Markdown과 Math 블록이 있다.

 

Markdown은 아직 부족한 기능이라서 checkbox 정도만 되는 것 같지만,

Math의 경우에는 좀 많이 신기했다.

 

 

지금 한창 관심을 받다보니 많은 Issues와 Pull-Request들이 진행되고 있다.

여러분들도 한 번 관심갖고 지켜보면서 많은 사용을 해보면 좋을 것 같다.

 

반응형

 

▶ 요약

  ● 데이터 과학 vs 데이터 분석

    - 데이터 분석은 데이터 과학에 포함되는 one of them

    - 데이터 과학 = 데이터 분석 + 머신 러닝

 

  ● '데이터 분석'의 정의
    - 광의적 정의 : 데이터 수집/처리/정제 및 모델링을 포함한 전체 영역
    - 협의적 정의 : 기술통계, 탐색적 데이터 분석, 가설 검정

 

  이번 공부에서 사용하는 Python Package

    - Numpy
    - pandas
    - matplotlib
    - SciPy
    - scikit-learn

 

  ● 데이터 파일 확보하기

    - 이번 공부에서는 '도서관별로 공개된 장서/대출 데이터'를 사용

      . https://www.data4library.kr/openDataL
    - 한글 데이터의 경우에는 특히 인코딩에 대한 처리가 필요할 수 있음

 

  ● pandas dataframe
    - 하나의 행은 여러 데이터 타입의 열을 갖을 수 있다.
    - 하나의 열은 한 종류의 데이터타입으로만 구성된다.

 

 

▶ 기본 미션

p. 81의 확인 문제 4번 풀고 인증하기

 

4. 판다스 read_csv() 함수의 매개변수 설명이 옳은 것은 무엇인가요?

    ① header 매개변수의 기본값은 1로 CSV 파일의 첫 번째 행을 열 이름으로 사용합니다.

    ② names 매개변수에 행 이름을 리스트로 지정할 수 있습니다.

    ③ encoding 매개변수에 CSV 파일의 인코딩 방식을 지정할 수 있습니다.

    ④ dtype 매개변수를 사용하려면 모든 열의 데이터 타입을 지정해야 합니다.

 

매뉴얼을 찾아보자.

[출처]&nbsp;https://pandas.pydata.org/docs/reference/api/pandas.read_csv.html

 

① header 매개변수의 기본값은 1로 CSV 파일의 첫 번째 행을 열 이름으로 사용합니다. (X)

 

header 매개변수의 기본값은 "infer"이고, 자동으로 header를 추론하게 된다.

header가 없는 경우 "None"으로 명시해줘야 한다.

[출처]&nbsp;https://pandas.pydata.org/docs/reference/api/pandas.read_csv.html

 

② names 매개변수에 행 이름을 리스트로 지정할 수 있습니다. (X)

 

names 매개변수는 column 이름을 지정하기 위한 것이다.

[출처]&nbsp;https://pandas.pydata.org/docs/reference/api/pandas.read_csv.html

 

③ encoding 매개변수에 CSV 파일의 인코딩 방식을 지정할 수 있습니다. (O)

[출처]&nbsp;https://pandas.pydata.org/docs/reference/api/pandas.read_csv.html

 

④ dtype 매개변수를 사용하려면 모든 열의 데이터 타입을 지정해야 합니다.

 

전체 dataset의 데이터 타입을 지정할 수도 있지만, 개별 column의 데이터 타입을 지정할 수도 있다.

[출처]&nbsp;https://pandas.pydata.org/docs/reference/api/pandas.read_csv.html

 

▶ 선택 미션

p. 71 ~ 73 남산 도서관 데이터를 코랩에서 데이터프레임으로 출력하고 화면 캡처하기

 

→ 다음 순서대로 진행해보겠다.

  ① 도서관 데이터 다운로드 받기

  ② 구글 드라이브에 업로드 하기

  ③ Colab 실행해서 코드 작성하기

 

차근 차근 진행해보자.

 

① 도서관 데이터 다운로드 받기

  - https://www.data4library.kr/

https://www.data4library.kr/

 

상단 탭 메뉴에서 "데이터 제공"을 선택하고 받고자 하는 도서관을 선택해보자.

나는 ... 우리 동네 도서관을 골라봤다 ^^

데이터 제공 - 도서관 선택

 

"도서관명"을 클릭하면 상세 화면이 나온다.

상세 화면

 

하단에 있는 리스트 중에서 마음에 드는 것을 하나 고르고,

다운로드에서 "Text"를 선택하면 CSV 파일을 다운로드 받을 수 있다.

 

② 구글 드라이브에 업로드 하기

구글 드라이브에 들어가서 이번 공부에서 사용할 폴더를 하나 새로 만들자.

https://drive.google.com/

 

앞에서 다운로드 받은 파일을 업로드 하자.

파일 업로드

 

③ Colab 실행해서 코드 작성하기

이번 공부를 위한 새 노트를 하나 만들자.

https://colab.research.google.com/

 

교재를 보면 'gdown' 패키지를 통해서 구글 드라이브에 있는 파일을 다운로드 받을 수 있다고 하는데,

내가 멍청해서인지.... 성공하지 못했다.

 

이유는 아마도 인증 관련해서 처리가 안되어서인 것 같은데,

구글 드라이브에 있는 파일을 누구나 다운로드 받을 수 있도록(인증 없이 다운로드 되도록)

권한을 처리해주면 될 것 같기는 하지만.... 여하튼, 그냥 사용하기에는 이슈가 있었다.

 

하지만, 우리의 Colab은 구글 드라이브를 편하게 사용할 수 있도록 기능을 제공해준다!!!

Drive Mount

 

왼쪽 위의 저 메뉴를 누르면 된다.

액세스 허용

 

Google Drive 연결을 진행하면 된다.

mount

 

drive라는 폴더에 Google Drive가 마운트 되어있는 것을 확인할 수 있다.

우리는 이제 그냥 사용하면 된다.

 

파일 경로를 일일이 타이핑하려면 힘드니까 편하게 복사하자.

경로 복사

 

이번 숙제의 소스코드는 정말 심플하다.

code

 

실행 결과는 다음과 같다.

pd.read_csv()

 

이번 공부는 여기까지~

반응형

자~ 이번에는 "Merge Sort"에 대해서 알아보자.

한글로는 "합병 정렬" 또는 "병합 정렬"이라고 불리운다.

[출처] https://www.whatwant.com

 

세계의 모든 지식이 들어있다고 해도 과언이 아닌 위키피디아에서는

Animated GIF 이미지로 Merge Sort를 너무나 잘 설명해주고 있다.

[출처] https://en.wikipedia.org/wiki/Merge_sort

 

이 알고리즘은 그 유명한 "존 폰 노이만(John von Neumann)"님이 1945년에 개발했다고 한다.

우리의 갓 노이만 형님 !!!

 

위 Animation을 잘 지켜보면 알겠지만,

"Divide-and-Conquer (분할 및 정복)" 알고리즘의 하나이다.

[출처] https://www.whatwant.com

 

반절씩 잘라서 나누고, 합치면서 정렬을 하는 것이다.

[출처] https://www.whatwant.com

 

그런데, 실제 구현을 할 때 divide를 하기 위해서

위의 그림에 있는 모든 박스의 갯수만큼 별도의 메모리 공간을 확보해야 할까?

 

한 번에 모든 메모리 공간을 확보하는 것 보다는

한 단계씩 나눠서 그 때 그 때 필요한 값을 복사해서 사용하는 방식이 훨씬 효율적이고 똑똑한 방법이 되겠다.

 

무슨 말이냐고!?

한 단계씩 밟아나가보자 !!!

[출처] https://www.whatwant.com

 

위 그림과 같이 8개의 입력이 있다고 해보자.

인덱스(index)값의 의미로 "[ ]"로 묶은 형태로 표기해보았다.

 

우리의 명령(입력)은 다음과 같다.

 

"1번부터 8번까지의 인덱스를 갖고 있는 입력값을 merge sort 해줘 !!!"

 

이것을 1-depth 더 들어가서 살펴보면 다음과 같다.

 

"1번부터 4번까지의 값을 merge sort하고

5번부터 8번까지의 값을 merge sort한 다음에

그 2개의 결과를 merge 해줘"

 

어!? 여기에서 조금 애매한 표현이 등장했다. merge ???

[출처] https://www.whatwant.com

 

[5, 6] 과 [1, 3]을 merge 하는 과정을 보면 그냥 합치는 것이 아니라

크기를 비교해서 작은 것부터 차례대로 하나씩 넣어가는 과정이다.

 

그리고 여기에서 주의해야할 사항이 하나 더 있다.

 

[5, 6] 과 [1, 3]을 merge 할 수 있는 것은 [5, 6] 과 [1, 3]이 각각 이미 sort가 되어있기 때문이다.

 

그림으로 살펴보자.

[출처] https://www.whatwant.com

 

[2, 4, 1, 3]이라는 값을 merge 한다고 하면

반절 크기의 2개의 메모리 공간을 잡아놓고, 거기로 값들을 복사한다.

[출처] https://www.whatwant.com

 

그리고 2개 메모리 공간의 앞 부분의 값을 비교해서

작은 값 순서대로 하나씩 복사해 넣는 과정으로 정렬이 된 값으로 merge가 된다.

 

Pseudo Code는 다음과 같다.

[출처] https://www.whatwant.com

 

p, q, r 값의 정체는 다음과 같다.

[출처] https://www.whatwant.com

 

merge 작업을 할 시작 위치(p), 끝 위치(r), 그리고 divide를 할 중간값(q)이다.

그러면 pseudo code를 진행하면서 정해지는 값/상태들을 확인해보자.

 

쪼갠 값들을 저장할 메모리 공간의 크기를 계산하기 위한 n1, n2 값을 계산한다.

[출처] https://www.whatwant.com

 

divide한 값을 저장할 2개의 메모리 공간을 생성한다.

[출처] https://www.whatwant.com

 

응?! 4개가 아니라 5개씩 공간을 준비하네?!

그 다음 pseudo code들을 진행해보면 이유를 알겠지.

[출처] https://www.whatwant.com

 

이제 모든 준비는 끝났다.

[출처] https://www.whatwant.com

 

여기까지 해서 merge 과정에 대해서 살펴봤다.

이제, 전체적으로 merge sort 하기 위한 pseudo code를 알아보자.

[출처] https://www.whatwant.com

 

3번 라인은 본래 아래와 같은 notation이다.

Editor에서 사용 가능한 기호 중에서 마땅한 것을 찾지 못해서 ^^

[출처] https://www2.hawaii.edu/~suthers/courses/ics311f20/Notes/Topic-02.html

 

2로 나눈 결과의 소숫점 버림값을 취하겠다는 의미이다.

 

지금까지 살펴본 내용을 기반으로 Python으로 구현해보면 다음과 같다.

[출처] https://www.whatwant.com

 

 

Merge Sort를 어떻게 하는 것인지에 대해서는 이제 다 알아봤다.

남은 것은 Performance 측정이다.

 

먼저, Merge 과정에 소요되는 시간을 계산해보자.

[출처] https://www.whatwant.com

 

위 그림에서 보이는 것 처럼

핵심적인 부분은 move와 comapre로 구성되어 있다.

 

move는 "n1 + n2" 횟수만큼 실행이 되고

compare는 "n1 + n2" 보다 작거나 같은 횟수만큼 실행이 될 것이다.

 

그렇기 때문에, 전체적으로 2 * (n1 + n2) 횟수보다 같거나 적은 횟수만큼 실행이 된다고 봐도 무방할 것이다.

 

Merge = Θ(n1 + n2)

 

그러면, 전체 Merge Sort의 소요 시간은 얼마나 될까!?

 

[출처] https://www.whatwant.com

 

MERGE-SORT(A, p, r) 의 소요 시간을 T(n) 이라고 하면,

3번째 라인과 4번째 라인은 n의 이등분된 값을 갖게 되므로 T(n/2) 값을 갖는다고 할 수 있다.

 

5번째 라인은 바로 앞에서 살펴본 내용에서 n1 + n2 = n 이므로 Θ(n) 값으로 표현해볼 수 있다.

 

여기에서 생각해볼 것은 1번 라인이 비교문이라는 것이다.

비교문을 통과하지 못하는 경우를 생각해보면, p < r을 만족하지 못하는 경우는 n=1 일 경우일 것이다.

 

그래서 점화식으로 표현해보면 다음과 같다.

[출처] https://www.whatwant.com

 

이와 같은 경우는 'Recursion Tree Method(재귀 트리 방법)'을 통해 풀어낼 수 있는데,

중간 과정은 생략하고.... 그래서 계산한 결과는 다음과 같이 정리된다.

[출처]&nbsp;https://cs.stackexchange.com/questions/64060/mergesort-recurssion-tree-depth-logs

 

위의 이미지에서는 Big-O로 표기되었지만, Big-Theta로 할 수 있다.

 

그러면 메모리 공간은 얼마나 사용할까?

 

"n"개 만큼 더 필요로 한다.

최대 n개 공간이 있으면 그것을 이용해서 모두 계산 가능하다.

반응형

 

매번 타이밍을 놓쳐서 참여하지 못했던 "혼공학습단"인데,

드디어 모집 공고를 제 때 발견(!)하여 바로 신청할 수 있었다.

 

공짜로 참여할 수 있는 것만으로도 감지덕지인데,

열심히 공부하면 상품권도 준다고 그러고 ... 매주 간식도 주신단다 ~~~ !!!

 

정말 리뷰어 활동할 때도 느꼈지만,

한빛미디어는 정말 밝게 빛나는 햇빛이다 !!!

 

 

신청하고선... 뽑히기를 간절히 바라며... 기다리고 있었는데, 선정 메일이 도착을 해버렸다 !!!!

 

혼공학습단으로 선정이 되면 뭘 해야 되냐고?

말 그대로 빡세게 공부하면 된다!!! ^^

 

완주를 목표로 파이팅 !!!

 

반응형

 

함수의 증가? 함수의 성장? 함수의 성장률?

 

한글로 어떻게 표현해야 하는지 좀 애매한 타이틀인데,

구글링을 해봐도 명확하게 번역한 명칭이 확인되지 않는다.

보통은 그냥 "함수의 성장" 정도로 번역하면 적당한 것으로 보인다.

 

여기에서 하고 싶은 말이 무엇이냐면,

입력값에 대한 결과값, 즉 함수의 값이 어떻게 변화(증가/성장)하는지를 살펴봐야 한다는 것이다.

 

특히 우리는 지금 알고리즘 공부를 하기 때문에 이에 특화되어 정의해보자면,

입력 크기(n)에 따라 얼마나 많은 시간이나 공간을 필요로 하는 것인지를 살펴보는 것이다.

 

 

▶ Notation (표기법)

알고리즘의 성능, 즉 소요시간을 표현하는 3가지 notation을 먼저 알아보자.

 

① Θ-notation (Big-Theta) : tight

 

아주 정확하게 일치하는 것은 아니지만, 최대한 근접하게(tight) 표현하는 방법이다.

 

② Ο-notation (Big-O) : upper-bound

 

O-notation으로 표현한 값이 실제값과 같거나 더 큰 범위이기 때문에 upper-bound 라고 한다.

 

③ Ω-notation (Big-Omega) : lower-bound

 

Ω-notation으로 표현한 값이 실제값과 같거나 더 작은 범위에 속하기 때문에 lower-bound 라고 한다.

 

보통 'Big-O'라고 부르는 O-notation만 알고 있는 사람도 많은데(me...??? ^^),

위와 같이 3가지 표기법이 존재하고 있고 주로 많이 사용하는 것이 Big-O notation이다.

 

 

▶ Asymptotic Notation (점근 표기법)

정확히 문장으로 설명하기에 쉽지 않지만 위와같은 표기법에서 보는 것처럼

정확히 일치하지는 않지만 어떤 추세/경향을 대강(?!) 보여줄 수 있는 표기법을 Asymptotic Notation이라고 한다.

 

▷ O-notation

  - 아래 그래프를 잘 분석해야 한다. 상당히 많은 의미가 내포되어 있다.

 

일단 g(n)과 f(n)만 놓고 앞 부분을 살펴보면

때로는 g(n)이 더 높은 값을 갖기도 하고 f(n)이 더 크기도 하다가

어느 순간, n0 값 이후로 g(n)이 지속적으로 더 큰 값을 갖는다.

 

g(n)도 잘 살펴보면 그냥 g(n)이 아니라 양의 상수 값 c 를 곱한 c * g(n) 값이다.

앞에서의 n0 값 역시 양의 값이다.

 

위와 같이 깔끔하게 요약할 수 있다.

이럴 때 g(n)은 f(n)의 asymptotic upper bound라고 부를 수 있다.

 

 

여기에서 문제를 한 번 풀어볼까!?

 

위 식이 성립함을 증명해보자.

막막할 수 있으니 바로 설명을 보자면 (^^) 다음과 같다.

 

여기에서 가장 중요한 부분은 첫 줄이다.

 

이 문장만 이해할 수 있으면 Asymptotic notation에 대해서 이해한 것이다.

 

 

▷ Ω-notation

  - 마찬가지로 그래프를 하나 보자.

 

간단히 정리하면 다음과 같은 내용이다.

 

이젠 이해가 될거라 믿는다.

 

▷ Θ-notation

  - 마찬가지로 살펴보자.

 

 

 

 

앞에서 공부한 Insertion Sort에 대해서 표기를 해보면 다음과 같다.

 

Best-Case / Worst-Case가 존재 하므로 Θ-notation은 없고,

O-notaion과 Ω-notation이 존재하고 각각의 값은 위와 같다.

 

나름 쉽게 정리해본다고 했는데.... 기회가 되면 F2F로 설명을 ^^

 

반응형

+ Recent posts