머가필요해

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

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

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

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

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

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

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

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

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

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

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

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

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

무슨 말이냐고!?

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

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

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

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

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

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

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

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

그 2개의 결과를 merge 해줘"

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

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

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

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

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

그림으로 살펴보자.

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

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

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

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

Pseudo Code는 다음과 같다.

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

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

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

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

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

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

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

이제 모든 준비는 끝났다.

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

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

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

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

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

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

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

남은 것은 Performance 측정이다.

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

위 그림에서 보이는 것 처럼

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

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

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

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

Merge = Θ(n1 + n2)

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

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

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

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

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

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

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

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

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

위의 이미지에서는 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로 설명을 ^^

▶ ChatGPT

국제학술지 '네이처(Nature)'에서 올 한 해 과학계에 큰 화제를 불러일으킨 10명의 인물을 선정하는 '네이처 10(Nature's 10)'을 발표했는데, 역대 최초로 인간이 아닌 생성형 인공지능(AI) 챗봇 '챗GPT(ChatGPT)'를 포함시켰다.

ChatGPT라고는 하지만, 크게 바라보면 '생성형 인공지능' 자체가 우리 생활에 정말 큰 영향을 미치게 된 것이다.

지금은 시작일 것이다. 앞으로는 정말 생활 이곳 저곳에서 우리와 함께하게 될 것이다.

▶ RAG

ChatGPT는 정말 대단한 기능 및 성능을 보여주고 있지만, 한계점도 분명히 있다.

일단 ChatGPT가 이것 저것 골고루 많이 아는 똑똑한 아이이긴 하지만,

특정 분야에 대해서 전문적인 지식을 갖고 있다고 하기에는 조금 부족하다.

그리고 최신 정보를 알지 못한다는 점도 있고 장기 기억을 유지하기에 어렵다는 점도 있고,

할루시네이션(Hallucination)과 같은 문제도 있는 등

ChatGPT는 여러가지 한계점이 분명히 있고 이러한 한계점을 다양한 방법으로 해결하고자 발전하고 있다.

이러한 ChatGPT의 한계점을 극복하는 방법 중 하나로

RAG(Retrieval-Augmented Generation, 검색 증강 생성)이라는 것이 최근 엄청난 화두가 되고 있다.

위 그림에서 오른쪽 위를 잘 살펴보기 바란다.

'Knowledge Source'를 별도로 구성하고 이를 일종의 보조 기억장치처럼 사용하는 것이다.

어?! 뭔가 떠오르지 않는가!?

그렇다!!! 바로 "데이터베이스(Database)"이다.

▶ Embedding

ChatGPT의 경우 기본적으로 사용되는 데이터는 '자연어(Natural Language)'이다.

이러한 자연어를 문자 그대로 사용한다고 하면 그 안에 담겨있는 의미나 가치를 다루기가 어렵기 때문에

단어 또는 문장들을 다른 방식으로 표현을 해야하는데

현재 가장 보편적인 표현 방식이 바로 'Vector Embedding'이다.

Vector 형식으로 데이터가 저장이 되기 때문에

Vector 연산을 통해 검색을 한다거나 "king + queen = princess or prince"와 같은 연산도 가능하게 된다.

이제 이렇게 임베딩된 데이터들을 데이터베이스에 저장해놓고 쿼리를 해서 사용을 하면 되는데,

PostgreSQL이나 MySQL과 같은 기존 RDB를 이용하기에는 좀 어려움과 불편함이 한 가득이다.

▶ Vector Database

그렇다. 말 그대로 Vector 데이터들을 저장하고 제공하는데에 특화된 데이터베이스이다.

예전에도 있었던 데이터베이스 유형이지만, 최근 AI 시대가 되면서 엄청난 대박이 났다.

2021년도에 출시된 Pinecone은 1억 달러 규모의 시리즈 B 투자를 받았다고 한다. 기업 가치는 무려 7억 5천만 달러.

그 외에도 Weaviate, Chroma, Qdrant 等 다양한 Vector Database들이 모두 다 많은 투자를 받았다.

이렇게 돈이 쏠린다는 것은 이 분야에 대해서 많은 분들이 성공할거라 믿는다라는 의미일 것이고

그렇다면 우리는 이 부분에 대해서 공부해볼 가치가 충분히 있다!!!

▶ Pinecone

최근 가장 많은 인기를 얻고 있는(돈을 투자 받은?!) Pinecone에 대해서 알아보자.

비용은 어떻게 될까!? (너무 돈! 돈! 하는 것 같아서 조금 그렇지만... 현실이... ^^)

비용 부분을 살펴보면서 눈치 챘어야 한다.

그렇다! Pinecone은 On-Premise 형태로 제공되지 않는다. 무조건 SaaS 이다!

그나마 다행인 것은 Free 제공 부분이 있다는 점! ^^

Sign-Up은 편하게 되어있다.

무료 요금제에서는 Index 1개를 사용할 수 있다.

기존 RDB에서 table 정도로 생각하면 될 것 같다.

Python을 이용해서 접근하기 위해서는 API Key 값을 알아야 한다.

왼쪽 메뉴탭에서 'API Keys'를 눌러보면 하나 이미 만들어진 것을 확인할 수 있다.

▶ Hello-whatwant

이제 Pinecone을 사용해보자.

Knowledge를 임베딩해서 저장을 하고,

질문을 다시 임베딩해서 쿼리를 던지면 그와 유사도가 높은 것들을 답해주는 과정을 해보고자 한다.

기본적인 간단한 workflow이지만, 그래도 다음의 두 가지 사항은 미리 확인/준비 해야 한다.

① Python에서 Pinecone을 사용하기 위한 방법

② Embedding Model 선정 및 사용 방법

① Python에서 Pinecone을 사용하기 위한 방법

  - 앞에서 이미 Pinecone API Key 및 Env 값은 확보(?)했으니 이 부분은 Pass

  - 그리고, 친절하게도 Pinecone 라이브러리를 제공해주니 이를 사용하면 OK

    . https://docs.pinecone.io/docs/quickstart

② Embedding Model 선정 및 사용 방법

  - 이 부분은 정해진 것이 없기에 필요에 따라 각자의 취향/상황에 맞춰서 하면 된다.

    . 지금은 보통 적은 리소스로 괜찮은 성능을 보여준다고 하는 all-MiniLM-L6-v2 모델을 사용해보겠다.

이제 코드로 풀어보자.

설명을 위해 Colab 환경에서 진행한 내용으로 진행하겠다.

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

CPU 환경에서도 실행 가능하긴 하지만, 이왕이면 GPU 환경이 빠르니... 선택하자.

pinecone-client, sentence-transformer 2개의 패키지 설치가 필요하다.

앞에서 확인한 pinecone API key 값 및 Env 값을 넣어주면 된다.

warning은 가뿐히 무시하자 ^^

굳이 torch를 import까지 할 것은 아닌 것 같아서 주석처리했고 ^^

all-MiniLM-L6-v2 모델을 불러왔는데, 출력된 내역을 보면 간단하게나마 spec을 확인할 수 있다.

잠시 현재 Pinecone의 Index 상태를 살펴보자면 다음과 같이 아무 것도 없다.

그러면, 우리는 Index를 하나 만들어보자.

이렇게 만들면 Pinecone에서는 다음과 같이 결과가 보인다.

내용물을 살펴보면 다음과 같이 아무 것도 없다 ^^

테스트하기 위해 넣어줄 데이터는 ChatGPT로 만들어봤다.

프로그래밍 언어를 한 문장으로 정리해달라고 했다.

입력을 열심히 해주면 된다.

그 다음에는 Pinecone으로 넣어줄 형태로 변환을 해야 한다.

'일련번호, 임베딩된 내용, 원본 내용'의 조합으로 생각하면 된다.

준비가 되었으면 upsert 해주면 된다.

upsert가 뭐냐고? update or insert !!!

Pinecone에서 확인해보자.

Pinecone의 상태를 직접 확인해볼 수도 있다.

query를 요청할 용도의 function을 하나 만들어 보자.

이제 질문을 해보자.

잘 나온다 !!!

다른 식으로 질문을 해볼까?

잘 찾아준다 !!!

여기까지~~~~ ^^

알고리즘을 구현하기 위한 소스 코드의 소요 시간(실행에 필요한 시간)은 어떻게 측정할 수 있을까?

실행을 시켜서 완료될 때 까지 걸린 시간을 측정하면 될까?

실행하는 컴퓨터의 CPU가 무엇인지, HDD 또는 SSD를 사용하는 지와 같은 여러 상황에 따라서

똑같은 알고리즘도 시간이 다르게 나올 수 있을텐데...

그리고 작성하는 프로그래밍 언어에 따라서도 실행 시간은 천차만별일 수 있다.

즉, 실제 시간을 측정해서 알고리즘의 성능을 비교 평가하는 것은 어렵다.

그래서, 보통은 Pseudo code의 라인별 수행하는 횟수를 카운트 하는 방식으로 소요 시간을 측정한다.

Insertion sort의 pseudo code는 다음과 같다.

한 줄씩 살펴보자.

입력값 A의 길이가 n이라고 해보자.

보통의 프로그래밍 언어에서 배열은 0부터 시작하지만 pseudo code에서는 1부터 시작한다.

그러면 1번 라인은 총 몇 번 수행이 될까?!

지금 대답을 하지 못하는 분은 개발자로서 조금 문제가 있는 상태이고 (^^)

"n - 1"번이라고 대답하신 분은 보통의 개발자 수준이고

"n"번이라고 대답하신 분은 정말 훌륭한 개발자 이거나 아니면 운으로 맞춘 분일 것이다 ^^

"j = 2"라고 되어 있기에 for문 자체는 "n - 1"번 수행한다고 말하는 것이 일반적이지만

실제 for문 자체는 마지막 조건 체크를 위해 한 번 더 수행을 하기 때문에 "n - 1 + 1"번 수행을 하게 된다.

하지만, 그냥 "n - 1"번 수행한다고 해도 무방하지 싶다.

2번 ~ 4번 라인은 각각 "n - 1"번 수행한다.

5번 ~ 7번 라인이 핵심인데...

처음 "j = 2" 상황에서는 1번 위치에 있는 값하고만 비교하면 되기에 1번만 실행이 될 것이고,

그다음 "j = 3" 상황에서는 2번 위치하고 비교하고 그 다음 1번 위치하고 비교를 하게 된다.

그렇게 해서 "j = A.length" 상황에 되면, 즉 "j = n" 상황이 되면 "n - 1"번 비교를 하게 된다.

이걸 그림으로 표현해보면 아래와 같다.

그래서, while문이 있는 5번 라인은 "1 + 2 + 3 + ... + n"번 실행을 하게 되고 (값 비교를 위해 한 번 더)

6번, 7번 라인은 "1 + 2 + 3 + ... + (n -1)"번 실행을 하게 된다.

8번 라인은 당연히 "n - 1"번 수행한다.

잘 이해가 되시나요?!

여기에서 "예"라고 대답을 하신 분은 .... No! No!! No!!!

8번째 값을 정렬할 차례가 와서

첫번째로 7번 위치랑 비교 =  pass, 6번 위치 비교 = pass

5번 위치랑 비교했더니 여기에서 break

8번째 값을 정렬할 때에는 7번의 비교가 필요한 줄 알았는데,

실제 입력값 상황에 따라 수행 횟수가 가변적이다.

그래서 이를 t변수를 이용해서 표현한다고 하면, 전체적으로 다음과 같이 정리해볼 수 있다.

C 변수는 각 라인을 실행할 때 드는 비용(시간)을 의미한다.

그래서 위 내용을 정리해서 총 실행 시간은 다음과 같이 정리할 수 있다.

여기에서 뭔가 답답하게 만드는 것이 t 변수 값인데,

best/average/worst case에 따라서 값이 달라질 수가 있다.

위 그림에서 왼쪽이 best case이고, 오른쪽은 worst case이다.

다시 말해 이미 정렬이 되어 있는 경우는 best case이고, 역으로 정렬된 경우가 worst case이다.

best case에 대해서 정리해보면 다음과 같다.

결론적으로는 an + b 형식의 식으로 나오고 이는 선형적인 모습을 보인다.

이번에는 worst case를 살펴보자.

정리된 식을 살펴보면,

worst case는 an^2 + bn + c 와 같은 2차 함수 형태로 나타난다.

best case는 입력값 n의 크기가 커짐에 따라 선형적으로 실행 시간이 증가하게 되고

worst case는 입력값 n의 크기가 커짐에 따라 제곱으로 증가하게 된다는 것을 알 수 있다.

그런데, 모든 알고리즘들에 대해서 이렇게 분석하는 것은 너무 어렵다.

이와 같은 과정을 뭔가 단순하면서 명확하게 표현하는 것에 대해서 알아보도록 하자.

지금 말고 다음에.... ^^

Youtube를 보다가 갑작스레 보게 된 재미난 영상 하나가 있었다.

으잉?! IT 뉴스를 이런 감성으로 전달한다고!?

위 영상의 출처는 다음과 같다.

  - https://www.youtube.com/@GoogleDevelopers

여기에서 특히 재미있는 것은 "Google Developer News tl;dr"인데,

Web, Mobile, AI, Cloud 관련 소식들을 정말 깔끔하고 재미있게 소개해주고 있다.

지루하고 어렵지 않냐고!?

영상에서는 정말 간략하고 핵심적인 내용만 소개하고 자세한 소식은 각자 찾아볼 수 있도록 링크로 제공해준다.

구글 관련된 소식만 알려주는 것 아니냐고!?

뭐 맞는 말이긴 한데.... 개발자 세상에서 Google이 관여 안된 것을 찾는 것이 더 어렵지 않을까!?

TensorFlow도 Google 거다. (이거 모르는 사람 많지 않나!? 나만 몰랐나?! ^^)

Chrome에서 3rd-party Cookie 지원을 24년 1분기부터 순차적으로 종료할건데, 웹 개발하는 사람 모두 알아야 하지 않나!?

AWS를 더 많이 쓰긴 하지만, GCP 기반으로 개발하는 사람들도 많지 않나!?

뭐, 구글 소식만 알아도 훌륭한 개발자이지 않을까 한다 ^^

그러니, 구독과 좋아요~..... ^^

(Google에서 따로 후원 받지 않았습니다!!!! 아! 애드센스..... 받은건가?????)

영어가 부담스러우면 자동 번역하면 되니까 부담 없이 구독해서 정보를 얻으면 좋을 것 같다.

한글 좋아하는 저같은 개발자들을 위해 추가적으로 공유하자면

한국 개발자를 위한 블로그도 별도로 운영되고 있다. 최신 업데이트도 꾸준히 되고 있다.

  - https://developers-kr.googleblog.com/

한국 개발자를 위한 페이스북도 운영하고 있다.

  - https://www.facebook.com/googlefordevskr/

한국 개발자들을 위한 공식 사이트는 다음과 같다.

  - https://sites.google.com/view/gdeveloperskorea/홈

국내에서는 공식적으로 14개 GDG(Google Developer Groups)가 굴러가고 있는데,

최근에는 GDG SongDo가 이벤트도 많이 하면서 활발한 것 같다.

Google for Developers Korea의 공식 유튜브 채널도 있긴한데, 최근 업데이트는 잘 안되고 있다.

  - https://www.youtube.com/channel/UCZU3wmgRuH9gc2E3jhvEE_g

이 글을 포스팅하는 시점에서 유용한 정보 하나 더!

Devfest Cloud 2023이 23년 12월 9일에 있다.

  - https://festa.io/events/4385?fbclid=IwAR12BFTRSFTI9LUbLd8eclbtvm_jIAJ82reVs-8mbECKtWTdzbeuKRoVtnw

개발자 여러분들에게 조금이나마 도움이 되기를 기원해보며 포스팅합니다!!!

이제와서 왠 알고리즘 !? ^^

나름의 이유로 알고리즘을 차분히 조금은 깊게 살펴볼 이유가 있어서 정리를 해보고자 한다.

우선 알고리즘에서 가장 대표적인 문제 유형은 바로 정렬(sort)이다.

크기가 다른 여러 개의 입력값이 있을 때, 이를 크기 순서대로 줄을 세워야 하는 문제이다.

정렬 문제(Sorting Problem)를 해결할 수 있는 알고리즘(Algorithm)은 상당히 다양한데,

그 중에서 가장 첫번째로 언급되는 것이 바로 '삽입 정렬(Insertion Sort)'이다.

삽입 정렬을 한 번에 확인하기 위한 가장 좋은 예시는

위키피디아에서 보여주는 에니메이션이다.

찬찬히 잘 살펴보면 어떻게 하겠다라는 것인지 충분히 이해할 수 있겠지만

그래도 좀 더 설명을 해보자면 다음과 같다.

6번째까지 정렬이 된 상태에서 (1, 3, 5, 6, 7, 8), 7번째 '2' 순서가 되었을 때를 설명해보려고 한다.

일단, 자기 자신의 앞에 있는 '8'과 비교했더니 나(2)보다 큰 값이기에 '8'을 한 칸 앞으로 옮긴다.

그 다음에는 하나 더 앞에 있는 '7'과 비교를 하고 옮기고 ... 그렇게 진행하다가

'1'을 만나게 되는데, 이번에는 '2'보다 작은 값이기에 자기 자신(2)이 '1' 뒤에 위치하면 된다.

'Pseudo Code'는 다음과 같다.

2번째 입력값부터 시작해서 마지막 입력까지 수행을 해야 하는 것이고

기준이 되는 값을 일단 'key'에 저장해놓고,

key랑 비교를 시작할 위치는 key보다 하나 앞선 값이다.

이제 앞에 있는 값들과 비교를 해보고 비교한 값이 크면 비교한 값을 뒤로 한 칸 옮기고

같거나 작으면 비교를 멈추고 거기에 key값을 넣어주면 된다.

Python으로 작성해본 코드는 다음과 같다.

Pseudo code와 거의 동일하다.

뭐 당연히 결과는 잘 나온다.

자~ 이제 시작이다.

살펴봐야할 많은 것들이 있다.

과연 이 알고리즘은 얼마의 시간이 걸릴 것이며, 얼마의 메모리가 필요하고,

Best Case일 때와 Worst Case일 때 어떻게 되는지를 살펴봐야 한다.

거기에다가 하나 더 알아봐야 할 것은 입력값들의 순서가 유지되는지에 대해서도 알아봐야 한다.

하지만, 벌써부터 지칠 수 있으니

다음 기회로.... ^^ (절대 귀찮아서 미루는 것이 아니다! 절대로! 절대로?)

집에서 문득 인터넷이 느리다고 느껴지면

갑자기 우리집 통신사 서비스 품질이 낮아진 것이 아닌지 의심이 들곤 한다.

그럴 때 사용해볼만한 네트워크(인터넷) 속도 측정 사이트들을 알아보자.

아! 별도의 설치 없이 웹브라우저만으로 사용가능한 사이트만 리스팅했다.

1. 클라우드플레어

   - IT에 종사하는 분들이 아니라면 모르실 수도 있지만,

     CDN/DNS 서비스 분야에 있어서는 전세계의 1/5 이상이 사용하고 있다는 클라우드플레어의 속도 측정 서비스

   - 규모가 있기에 당연히 우리나라에도 데이터센터가 있다.

   - https://speed.cloudflare.com/

2. 넷플릭스

   - 넷플릭스 고객들이 OTT 스트리밍을 받아야 하기에 이와 관련하여 운영하는 서비스

   - 결과가 너무 심플해보일 수도 있는데, 상세 정보 보기를 선택하면 조금 더 자세한 정보 확인 가능

   - https://fast.com/ko/

3. OOKLA

   - 미국 회사로써 웹 테스트 및 네트워크 진단 관련 업체에서 제공하는 서비스

   - 인터넷 서비스 제공 업체가 아니기에 조금 더 신뢰할 수 있을 거라 기대

   - 광고 때문에 조금 지저분해 보이기는 함

   - https://www.speedtest.net/

4. Google

   - 구글도 구글파이버라는 이름으로 인터넷서비스 사업을 하고 있고, 그래서 운영하는 서비스

   - 아마도 미국에서만 서비스를 하고 있기에 측정 결과가 좀 낮게 나오는 것으로 추정

   - https://fiber.google.com/speedtest/

5. OpenSpeedTest

   - HTML5를 이용한 네트워크 스피드 테스트를 하는 서비스

   - 다양한 디바이스를 모두 지원

   - https://openspeedtest.com/

6. 벤치비

   - 인터넷 속도 측정을 하는데에 있어서 빼놓지 못하는 벤치비 (아재 인증?)

   - http://speed.benchbee.co.kr/

7. Etrality GmbH

   - 주로 모바일 앱으로 인터넷 속도 측정 어플을 개발하는 것으로 여겨지는 업체

   - https://www.speedcheck.org/

이 정도로 측정하면 어느 정도 추세는 충분히 파악할 수 있을 것 같다.