구글블로그 나눔고딕 폰트 적용

http://btsweet.blogspot.com/2014/11/blogger_10.html

알고리즘 평가방법

알고리즘이란 어떤 문제를 해결하기 위한 절차와 방법이다.
이왕 문제를 해결할 거면, 좋은 알고리즘을 쓰면 좋다는데는 이견이 없을 것이다.

그렇다면 좋은 알고리즘은 무엇인가? 어떻게 좋다는 것을 알 수 있을까?
본 글에서는 알고리즘 평가요소, 수학적 알고리즘 평가방법에 대해 끄적여 보겠다.

알고리즘 평가요소

1. 시간의 효율성 : 얼마나 빠르냐?
2. 공간의 효율성 : 얼마나 메모리를 적게 쓰느냐?
3. 코드의 효율성 : 프로그래머 입장에선 가독성, 컴퓨터 입장에선 얼마나 컴파일러와 하드웨어에 최적화 되어 있냐?

3가지 평가요소 중 가장 중요시되는 평가요소는 시간의 효율성이다.
하드웨어가 좋아지면서 공간의 효율성은 비중이 상대적으로 낮아졌으며, 실제로 프로그램이 구동하면서 잡는 메모리를 측정해야하는 어려움이 있다. 코드의 효율성은 프로그래밍 언어에 따라 달라지므로 객관적인 지표가 되기 힘들다.

최선, 평균, 최악의 경우?

모든 알고리즘들은 행복할 떄와 우울할 떄가 있다. 이를 전문용어로 최선의 경우, 최악의 경우라고 한다. 100개의 데이터를 배열에 저장하고, 특정 데이터를 찾는 알고리즘이 있다고 하자.

최선의 경우는 0번쨰 인덱스에서 바로 데이터를 찾는 경우다. 하지만 알고리즘 평가하는데 이는 생각할 필요가 없다. 대부분의 알고리즘은 최선의 경우엔 만족할만한 성능을 보인다.

평균의 경우는, 평균적인 경우를 계산하는게 쉽지 않다. 분석에 필요한 여러가지 시나리오와 현실적인 데이터를 구성해야 하는 문제가 존재한다.

최악의 경우는, 알고리즘 평가방법에 가장 많이 채택되며, 적어도 이정도의 성능은 보장한다 를 보여준다.

알고리즘의 수학적 성능 평가 방법

방법에는 빅-오 표기법, 오메가 표기법, 세타 표기법이 있으며 알고리즘 성능 평가 방법 중 가장 많이 사용하는 방법은 빅-오 표기법이다. 오메가, 세타 표기법에 대해선 다루지 않는다.

빅-오 표기법은 알고리즘 성능을 평가할 때, 최악의 성능을 채택한다. 빅-오 표기법의 수학적 정의는 아래와 같다.

(뜬금없지만, 구글블로그에 수식을 자꾸 넣으려니 화가난다....)
예를 들어 f(n) = 4n^2 + 100 , g(n) = n^2 이라고 하자. f(n) <= Cg(n)을 만족시키면 된다.
만약 C가 100이라면 즉, 4n^2 + 100 <= 100n^2 가 되며, n이 10일 경우 식을 만족하게 된다. 즉 두 개의 상수 C=100, K=10 이 존재하므로 f(n) = 4n^2 + 100의 빅-오는 n^2 이다.

빅-오의 수학적 정의 및 증명에 따라 f(n) = 4n^2 + 100에서 4를 곱하고 100을 더하는 것은 큰 의미가 없다는 말이다. 어떤 시간 복잡도 함수 T(n)이 존재할 때, 빅-오의 연산은 다음과 같다.

T(n) = n^2 + 2n + 1 ==> O(n^2)
T(n) = 999n^3         ==> O(n^3)

빅-오에는 대표적인 표기가 존재하며, 각 표기를 아래 그래프에서 보여준다. 가로축 n은 데이터 갯수 이며, 세로축은 연산횟수의 증가 패턴이다.

해시 테이블 (Hash Table)

해시 테이블은 key-value 형식으로 데이터를 저장하는 자료구조로 데이터 탐색 시, 빅-오 O(1)의 성능을 낼 수 있다. 

자료구조 측면에서 해시 테이블, 맵, 사전은 용어의 차이일 뿐 동일하다.

왜 해시 테이블이지? 해시가 뭔데?

해시 테이블은 key를 해시 함수를 거쳐 좁은 범위의 키로 생성하여 테이블에 저장하는 구조이다. 우리가 해시 테이블에서 데이터를 주세요! 라고 던지는게 데이터가 key이고 해시 함수를 거쳐 만들어지는 해시 테이블이 실제 관리하는 key를 해시 값, 이러한 맵핑 과정을 해싱이라고 한다.

해시 테이블의 정의를 다시 말해보면, 해싱된 키와 맵핑되는 데이터를 저장한 자료구조라고 할 수 있다.

 

(출처 - 위키디피아)

수 많은 key들이 해시 함수를 거치면, 동일한 값이 나올 수 있으며, 이를 충돌(collision)이 라고 한다. 아래 글에선 충돌을 해결하기 위한 몇가지 방안들을 소개한다.

열린 어드레스 방법 (Open Addressing method)

1. 선형 조사법

아래 그림에서 key AAA가 해시 테이블에 먼저 데이터를 저장하였고, 뒤 이어 key DDD의 해시 값이 충돌하게 된다. 선형조사법은 바로 옆의 자리가 비었는지 확인 후 비어있으면 그 자리에 데이터를 저장한다. 즉, 그림에선 48 부분에 데이터를 저장한다.

선형 조사법에서 데이터를 찾는 순서는 f(k) + 1 -> f(k) + 2 -> f(k) + 3 -> .... 순으로 진행 된다.

선형 조사법은 클러스터 현상, 즉 특정 영역에 데이터가 몰리는 현상이 발생할 수 있다.

이를 완화 하기위해 충돌 발생 지점에서 먼 곳에서 빈 공간을 찾아보자 라는 아이디어로 이차조사법이 나왔다.

2. 이차 조사법

선형 조사법을 알았다면 이차 조사법은 매우 쉽다. 말 그대로 공간을 좀 더 멀리찾는다. 충돌 발생 시 이차 조사법의 조사 순서는 다음과 같이 전개된다.

f(k) + 1^2 -> f(k) + 2^2 -> f(k) + 3^2 -> ....

3. 이중 해시

이차 조사법은 선형 조사법 보다는 클러스터 현상을 완화시키지만, 해시 값이 같으면 빈 공간을 찾기 위해 접근하는 위치가 항상 동일하다. 이를 해결하기 위해 이중 해시 방법이 나왔다.

이중 해시에서는 두 가지 해시 함수가 존재한다.
첫 번쨰 해시 함수 : key를 해싱하는 과정에서 필요한 해시 함수
두 번쨰 해시 함수 : 충돌이 발생 시 몇 칸 뒤가 비었는지 살피기 위한 함수

이중 해시를 사용할 경우, 키가 다르면 빈 공간을 찾기위해 건너뛰는 길이도 달라 클러스터 현상의 발생 확률을 현저히 낮출 수 있다.

체이닝

체이닝은 닫힌 어드레스 방법으로, 충돌이 발생해도 자신의 자리에 저장하는 방법이다.

즉 동일한 해쉬 값에 대해 여러 값이 저장 될 수 있다.

아래 그림을 보자. AAA는 먼저 해시 테이블에 871이란 데이터를 저장한다. 뒤이어 DDD가 충돌이 발생하는데, 연결리스트를 이용해 동일한 45번 자리에 데이터를 연결시켜 저장한다.

블로거 글 제목의 색상 변경

https://haxingtricks.blogspot.com/2015/02/blogspot-how-to-change-post-title-color.html

구글 블로그 이미지 본문 영역에 맞게 자동 조절.

http://pastimelife.com/1319

정렬 알고리즘 Part2

Part2 에서는 복잡하지만 효율적인 정렬 알고리즘을 다룬다.

힙 정렬, 병합 정렬, 퀵 정렬 알고리즘을 다루려 했으나..

힙 정렬은 자료구조 힙의 특성을 이용한 정렬로, 힙에 데이터를 추가하는 과정에서 정렬된 데이터가 만들어지므로 딱히 쓸게 없다. (자료구조 힙이란? - https://sjkitpro.blogspot.com/2018/07/heap.html)

병합 정렬은.. 간신히 알고리즘을 이해하고 서적을 참고하여 소스를 짯으나, 완전히 이해하지 못한 것 같아 추후에 다시 공부할 때 이 부분을 업데이트 하겠다.

정렬 Part2 지만 퀵 정렬 하나만 다루는 슬픔....

퀵 정렬

퀵 정렬이 무엇인지는 아래에 나오는 그림들을 보고 이해하도록 한다. 말로는 어렵다는

퀵 정렬에서는 몇 가지 알아야 하는 용어가 있는데 하나씩 설명하겠다.

left : 정렬 대상 중 가장 왼쪽 데이터를 가리키는 이름

right : 정렬 대상 중 가장 오른쪽 데이터를 가리키는 이름

pivot : 정렬의 기준, 중심축이라는 의미

low : pivot을 제외한 가장 왼쪽 데이터를 가리키는 이름

high : pivot을 제외한 가장 오른쪽 데이터를 가리키는 이름

퀵 정렬에서 low는 오른쪽으로, high는 왼쪽으로 이동하는데 이동하는 기준은 아래와 같다.

low의 오른쪽 이동 : pivot보다 큰 값을 만날 때 까지 이동

high의 왼쪽 이동 : pivot 보다 작은 값을 만날 때 까지 이동

위에서 말한대로 low와 high가 이동하는 그림을 아래와 같은데 step 별로 설명을 담겠다.

step1 : low는 오른쪽으로 이동하다 pivot(5)보다 큰 데이터 8을 만나 멈춘다.

         high는 가리키던 데이터 4가 pivot(5)보다 작아 이동하지 않는다.

step2 : low와 high의 값을 바꾼다.

step3: 다시 low는 오른쪽으로 이동하다 pivot보다 큰 데이터 6을 만나 멈춘다.

         high는 왼쪽으로 이동하다 pivot보다 작은 데이터 2를 만나 멈춘다.

step4: low와 high 값을 바꾼다.

step5: 서로 이동하다 low가 high보다 큰 인덱스를 가리키는 상황.  더 이상 이동하지 않는다.

step6: pivot과 high의 값을 교환한다.

위 step 6의 데이터를 보면 pivot 값을 중심으로 왼쪽에는 pivot보다 작은 데이터가 오른쪽에서는 pivot보다 큰 데이터가 정렬된 걸 확인 할 수 있다.

나머지 정렬을 진행하기 위해 pivot을 기준으로 왼쪽과 오른쪽으로 분할한다.

분할된 왼쪽과 오른쪽에 left, right, low, high 개념을 지정하고 재귀적으로 위 과정을 반복한다.

퀵 정렬 성능평가

퀵 정렬의 시간 복잡도는 아래와 같다. (구글 블로그는 수식 추가 없나...???)

동일한 빅-오 를 갖는 다른 정렬 알고리즘에 비해 평균적으로 가장 빠른 정렬 속도를 보인다.

정렬 알고리즘 part1

정렬 알고리즘 part 1에선, 빅-오 성능 n^2인 알고리즘 들을 살펴보겠다.
쉽게 말해 알고리즘 성능이 좋지 않은 정렬 방법들을 살펴본다.

정렬 알고리즘을 항상 외우고 있을 필요는 없다고 생각한다.
허나, 필요할 때 어떤 알고리즘 이였지? 라는 질문에 대한 답을 이 글에서 찾길 바라는 마음에 정리하였다.

소스 구현 및 테스트는 따로 하였으나 본 글에는 소스를 적진 않으며, 알고리즘 설명을 위해 ppt 이미지를 많이 첨부하게 되었다.

버블 정렬

버블 정렬은 인접한 요소들을 비교하는 방법으로 데이터를 정렬하며 각 라운드에서 최대값을 먼저 정렬하는 방법이다.

알고리즘

4개의 데이터를 정렬하기 위한 1 라운드 과정이다. 인접한 요소들을 비교해 큰 값을 뒤로 이동 시키며, 1라운드가 끝나면 가장 큰 데이터가 맨 뒤로 정렬된다.

버블 정렬의 2라운드 과정이다. 1라운드를 통해 가장 큰 값이 맨 뒤로 정렬되었으니, 나머지 3개의 데이터만 정렬하면 된다.

마지막 3라운드 과정이다. 1,2 라운드를 통해 4개의 데이터 중 가장 큰 값 두개가 맨뒤에 정렬이 되었다. 따라서 남은 2개만 비교하여 정렬의 위치를 찾으면 된다.

성능평가

n개의 데이터를 버블 정렬 시킬 경우, n-1 라운드가 필요하며, 각 라운드가 끝나면 비교할 대상이 한 개씩 줄어든다. 이를 알면 아래의 성능평가를 이해할 수 있다.

선택 정렬

선택 정렬은 정렬 순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이 되는 알고리즘이다. 예를 들면, 가장 작은 데이터를 선택해 첫 번째 자리로 옮기고, 두 번째로 작은 데이터를 선택해 두 번째 자리로 옮긴다.

알고리즘

아래 그림은 선택 정렬 시, 각 라운드에 따른 정렬 순서를 보여준다.

1 라운드에서는 가장 작은 값 1을 첫 번째 자리로 옮기고,

2 라운드에서는 두 번째로 작은 값 2를 두 번째 자리로 옮기며,

3 라운드에서는 세 번째로 작은 값 3을 세번째 자리로 옮긴다.

위의 버블 정렬과는 달리 각 라운드가 끝난 결과만을 보여준다. (일일히 그리기 힘들다 ㅠ)

성능평가

데이터 n개를 선택정렬 하기 위해 n-1 라운드가 필요하며, 각 라운드마다 최소 값을 찾는 루프가 존재한다. 이에 따른 성능평가는 아래와 같다.

삽입정렬

삽입 정렬은 정렬되지 않은 부분과 정렬된 부분으로 나눈다. 그리고 정렬되지 않은 부분의 각 요소를 삽입하는 과정에서 정렬이 진행된다.

그림으로 보는게 빠르다.

알고리즘

아래 그림에서 첫 번째 라운드의 정렬을 통해 정렬 된 부분과 정렬되지 않은 부분으로 나눈다. 그리고 정렬되지 않은 데이터 4, 1을 맞는 위치에 삽입함으로써 정렬을 완성한다.

성능평가

삽입 정렬도 위 정렬 알고리즘과 마찬가지로, n개의 데이터 정렬을 위해 n-1라운드가 필요하며 각 라운드마다 삽입 위치를 찾기위한 루프가 존재한다.