징검다리 - 김종성 목사님

너희와 하나님의 사이는 끊어져 있는 다리와 같은 관계로 있지만,

하나님과 우리를 이어주는 중보자 - 예수님

기도의 중보자가 되자.

기도는 하나님과의 교제이지만, 사역이다.

요한복음 2:5, 4:14
로마서 15:16

소프트웨어 프로세스 소프트웨어 제품을 생산하기 위해서 필요한 활동의 집합이다.
소프트웨어 프로세스의 기본적인 활동은 다음과 같으며 모든 프로세스에 대해서 공통적이다.

비록 '이상적인' 소프트웨어 프로세스는 없지만 많은 조직에서 소프트웨어 프로세스를 개선할 수
있는 여지는 있다.

소프트웨어 프로세스 모델(프로세스 패러다임)은 소프트웨어 프로세스의 추상적인 표현이며, 명확한
기술이 아니다.
오히려 소프트웨어 개발의 방법을 설명하기 위해서 사용될 수 있는 프로세스의 추상화이다.
특정 소프트웨어 공학 프로세스를 만들기 위해서 인용되고 확장될 수 있는 프로세스 프레임워크로
생각할 수도 있다.

이 프로세스 모델을 도식화 하여 나타낸 일련의 흐름을 Software LifeCycle 이라고 하며 주요한 요소

          1. Phases          |          2. Intermediate Products          |          3. Reviews

를 포함하고 있다.
어떤 LifeCycle 이 옳다거나 혹은 잘 못되었다는 기준은 없다.
개발 상황이나 목표 등을 명확하게 고려하여 적절한 모델을 택하는 것이 중요하며 그것이 S/W 공학
을 전공한 Architect 의 역량이 아닐까라고 생각해본다.

[ 1. Build and Fix Model ]
소위 'Simple is Best' 의 명확한 보기가 될 수 있는 모델로..
내 노트에 '될 때 까지 계속해, 어서~♡(싸모님 ver)'  라고 적혀있다.
제목 그대로 First 작업 후 test 를 하여 Modify 를 반복하는 방법이다.
거의 대부분의 학생들이 report 할 때 적용하는 방식이라고 강석중 교수님께서 농담을 하셨는데..;;
사실이라는..;;;
[ 2. WaterFall Model ]
한글번역본을 보면 '폭포수' 모델로 번역되어 있다.
흔히 순차적인 작업을 일컫는 용어로써 단계별로 Verify 와 Test를 거치며..
단순하고 간단하다는 장점이 있다.
또한 문서가 각 단계마다 만들어지기에 다른 공학 프로세스 모델에 잘 어울리기도 한다.
하지만 폭포수는 한 번 물이 떨어지면 다시 역으로 올라오지 못하는 자연의 진리처럼...
WaterFall Model 은 오류가 생겼을 경우 이전 단계로 돌아갈 수 없다는 단점이 있다.
그래서 수정시에는 Intergration 이라는 단계를 거치게 된다.


[ 3. Rapid Prototyping Model ]
개인적인 모토이기도 한 Speed & Fast 를 중점적으로 고려하는 Model 이다.
진화적 모델이라고도 변역하는데 여기서 Prototype 은 '원형' '시제품' 'Demo' 등을 의미한다.
즉 초기에 구현을 한 후 이것을 이용하여 사용자의 의견을 반영, 만족스러운 시스템이 개발될 때
까지 Version UP 을 하는 방법이다.
Prototype 의 운명은 다음의 두 가지로 나누어지게 된다.

이 방식의 문제점은 Abstract(추상화)이 가능하기 때문에 Design 과 실제 Implement 된 시스템
사이의 Gap 이 생길수가 있다는 점이다.
대형 시스템의 경우 WaterFall 과 함께 Prototype model 를 혼용하는 것을 추천한다.
[ 4. Incremental Model ]
순차적, 점증적이라는 뜻의 Increments 를 정의하고 각 증분에 대한 우선순위를 적용한 후에
단계별로 순차적으로 개발하는 Process Model 을 일컫는다.
이전의 WaterFall 과 Prototype 의 단점인 유지보수의 어려움 및 설계 및 요구분석에서의 난해함을
보완하기 위해서 나온 모델이다.
점증적 개발 프로세스는 다음과 같은 장점을 지닌다.
그러나 모든 것은 양면적인 성향을 띄듯이, Incremental Model 에도 문제는 있다.
증분되는 각각의 작업은 비교적 작아야 하며(20,000라인 이하) 각 증분은 시스템 기능을 제공해야
한다는 점이다.
또한 전체 Frame Work Architecture 를 미리 설계해야 하는 어려움이 따르며 각 증분을 check 하기
위한 check List 가 존재해야 한다.
Operations 가 각 단계별로 보이지 않는다는 단점도 가지고 있다.

이러한 점증적 방법의 변형을 익스트림 프로그래밍(Extreme Programming) 이라고 한다.
이 방법은 매우 작은 증분을 개발하고 인도하는 것으로, 이 프로세스에 고객이 참여하고 지속적인
개선과 프로그래밍이 이루어진다.
[ 5. The Spiral Model ]
나선형 모델(달팽이 모델, Boehm, 1988)은 내부 반복을 동해서 시스템의 타당성을 증진시키고
요구사항 정의, 시스템 설계 등의 단계를 완성시키는 프로세스 모델이다.
나선에 있는 각 반복을 네 부분으로 나타내면 다음과 같다.

 

합병정렬은 mergesort(머지소트)라고도 불리우며 O(nlogn)의 복잡도를 가지는 정렬알고리즘이다. 합병정렬 또한 앞서 살펴본 분할정복법을 사용한다. 정렬은 해당 아이템의 수가 많은 수록 비교 및 삽입 연산이 많이 발생하게 된다. 따라서 그 연산을 최소화하기 위하여 정렬하고자 하는 해당 배열을 충분히 분할한 후 거꾸로 합병하면서 정렬을 하여 최종적으로 전체 배열의 정렬을 하는 방식이다.

합병정렬은 다음과 같은 절차로 진행된다.

배열을 2개 이상의 배열로 분할 할 수 있는데 n개의 배열로 분할하게 되면 n-원 합병정렬이 된다.

다음은 재귀적 방법을 이용하여 합병정렬을 구현한 것이다. 재귀적 함수에는 반드시 종료조건이 존재해야 한다. 종료조건은 배열의 크기가 1에 도달하는 경우가 되고, 바로 그 시점부터 합병이 시작된다.

위 구현된 합병정렬을 살펴보면 알겠지만 합병정렬을 수행하기 위해 입력된 배열 이외의 추가적인 배열(Ldiv, Rdiv)가 사용되는 것을 알 수 있다. 따라서 mergeSort 함수가 수행될 때 마다 배열들이 추가적으로 할당된다.

최상위의 두 배열의 아이템 개수는 n개이다. 처음 재귀호출을 하게 되면 이는 n/2개가 되고, 다음에는 n/4개가 된다. 평균적으로 재귀 호출시 두 배열의 아이템 개수는 바로 전 아이템 개수 합의 반이 된다. 따라서 추가적으로 만들어지는 배열아이템의 총 수는 n(1 + 1/2 + 1/4 + ... ) = 2n 이 된다.

위의 예제가 분할정복법(Divide-and-Conquer)를 설명하기에는 적합할지 모르지만 메모리 사용에서는 상당히 비 효율적이다. 따라서 제자리정렬(in-place sort)로 다시 구현해 보자. 제자리정렬은 입력을 저장하는 데 필요한 장소 이외의 추가적인 저장장소를 사용하지 않는 정렬 알고리즘이다.

다음은 제자리 정렬로 구현한 합병정렬이다.

 

퀵 정렬(Quick Sort)는 호아(Hoare, 1962)가 정의한 알고리즘으로 이름에서도 알 수 있듯이 매우 빠른 수행속도를 가진다. 퀵 정렬은 합병정렬과 비슷하게 분할정복법(Divide-and-Conquer) 방법에 근거한다. 전체 데이터를 두 부분으로 분할한 다음, 분할된 각 부분은 재귀적으로 다시 퀵 정렬을 수행한다.

퀵 정렬은 합병정렬과 비슷하게 보이지만 합병정렬과는 다르게 전체 데이터를 균등하게 분할하는 것이 아니라 기준(pivot)을 선택하여 기준보다 작은 데이터를 왼쪽에 위치시키고, 큰 데이터는 오른쪽에 위치시킨다. 일반적으로 기준은 첫번째 데이터로 선택한다. 결과적으로 기준의 왼쪽에는 기준보다 작은 데이터가, 오른쪽에는 큰 데이터가 위치하게 된다.


위 내용은 한번의 부분배열을 통해 정렬되는 과정을 보여준 것이다. 실제 퀵 정렬은 재귀적으로 더이상 분할할 수 없을때까지 분할된 후 정렬을 수행한다.

다음을 통해 좀 더 쉽게 퀵 정렬을 살펴볼 수 있다.


다음은 퀵 정렬에 대한 알고리즘이다.

다음은 분할에 대한 알고리즘이다.

그럼 이제 퀵 정렬의 복잡도를 살펴보자. 퀵 정렬은 최악의 경우 O(n²) 의 복잡도를 갖는다. 최악의 경우는 모든 데이터가 정렬된 경우이다. 이 경우 맨 앞의 데이터를 기준으로 선택했을 경우 데이터가 분할되지 못하므로 한번의 비교 연산이 n 번 이루어 진다고 하면 모든 데이터에 대해서는 O(n²)의 시간이 걸릴 것이다.

복잡도가 O(n²)인데 어떡해 이 알고리즘이 빠른 정렬이라고 불리게 되었을까? 그 이유는 평균의 경우 때문이다. 평균적인 경우 데이터에서 기준으로 선택될 확률은 모두 같다. 따라서, 평균은 모든 가능한 순서를 같은 횟수 정렬할 때의 평균 정렬시간이다. 말이 조금 어려울지 모르나 평균적인 경우에는 O(n log n)이 된다.

특히, O(n log n)의 복잡도를 가지는 다른 정렬알고리즘 보다도 더 빠르게 수행된다는 것이 증명되었다. 이러한 이유는 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만아니라, 한번 결정된 기준은 추후 연산에서 제외되는 성질을 가지기 때문이다.

퀵 정렬은 추가적인 메모리공간을 가지지 않는 제자리 정렬임에도 불구하고 한가지 단점은 앞서 말한대로 이미 정렬된 데이터에 대해서는 오히려 많은 시간이 걸리게 된다. 이러한 문제를 해결하는 방법은 기준을 선태할 때 왼쪽에서 선택하는 것이 아니라 중간 값을 기준으로 선택하는 것이다.


다음은 하나의 함수에 분할과 정렬을 모두 구현한 예이다.



퀵 정렬 라이브러리 함수 사용

---

보통 C언어 라이브러리에는 퀵 정렬 함수가 제공된다. 일반적으로 qsort 라는 이름으로 제공되며 다음과 같은 함수 원형을 가진다.

함수의 원형

함수 사용 예

Reference : Data Structures in C, 생능출판사
                 FOUNDATIONS of ALGORITHMS using C++ PSEUDOCODE, 사이텍미디어
                 http://ko.wikipedia.org/
                 http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm
출처 : http://proneer.tistory.com/entry/Sort-퀵-정렬Quick-Sort

 

삽입정렬은 이름에서 알 수 있듯이 삽입을 통해 정렬을 완성하는 알고리즘이다. 삽입정렬은 모든 데이터를 앞에서부터 차례로 비교 하여 자신의 위치에 삽입을 통해 정렬을 수행한다. 배열이 길어질수록 효율이 떨어지지만 구현이 간단하다는 장점이 있다.

삽입정렬의 과정을 살펴보면 다음과 같다.

다음은 삽입정렬을 구현한 예이다.

삽입정렬 또한 비교연산을 상수로 보고 주어진 데이터가 정렬되어 있지 않다고 보면 O(n²)의 시간복잡도를 가진다. 삽입정렬의 특징은 시간복잡도가 입력 자료의 구성에 따라 달라진다는 사실이다. 입력 자료가 정렬되어 있으면 있을 수록 빨라진다. 따라서, 같은 시간복잡도를 가지는 선택정렬이나 버블정렬보다 효율이 높다.

삽입정렬은 또한 안정한 정렬방법이며 제자리 정렬(in-place sort)이다. 안정한 정렬이라는 것은 같은 값일 경우 상대적 위치가 바뀌지 않는 경우이다. 제자리 정렬은 정렬을 위해서 주어진 자료 공간 이외의 공간을 사용하지 않고 정렬하는 것을 말한다.


Reference : http://ko.wikipedia.org/
                 Data Structures in C, 생능출판사

출처 : http://proneer.tistory.com/entry/Sort-삽입-정렬Insertion-Sort