절차지향(Procedural Programming)이란?

절차지향 프로그래밍이란 물이 위에서 아래로 흐르는 것처럼 순차적인 처리가 중요시 되며 프로그램 전체가 유기적으로 연결되도록 만드는 프로그래밍 기법입니다. 대표적인 절차지향 언어에는 C언어가 있습니다. 이는 컴퓨터의 작업 처리 방식과 유사하기 때문에 객체지향 언어를 사용하는 것에 비해 더 빨리 처리되어 시간적으로 유리합니다. 옛날에는 하드웨어와 소프트웨어의 개발 속도차이가 크지 않았습니다. 하지만 소프트웨어 언어의 발달과 컴파일러의 발달로 하드웨어가 소프트웨어의 발달을 따라오지 못하는 상황이 발생했습니다. 이는 객체지향 언어가 등장하게 되는 계기로 작용했습니다. 객체지향 프로그래밍은 개발하려는 것을 기능별로 묶어 모듈화를 함으로써 하드웨어가 같은 기능을 중복으로 연산하지 않도록 하고, 모듈을 재활용하기 때문에 하드웨어의 처리양을 획기적으로 줄여주었습니다.

장점

  • 컴퓨터의 처리구조와 유사해 실행속도가 빠름

단점

  • 유지보수가 어려움
  • 실행 순서가 정해져 있으므로 코드의 순서가 바뀌면 동일한 결과를 보장하기 어려움
  • 디버깅이 어려움

객체지향(Object Oriented Programming)이란?

객체지향의 정의를 살펴보면 객체지향이란 실제 세계를 모델링하여 소프트웨어를 개발하는 방법입니다. 객체지향 프로그래밍에서는 데이터와 절차를 하나의 덩어리로 묶어서 생각하게 됩니다. 이는 마치 컴퓨터 부품을 하나씩 사다가 컴퓨터를 조립하는 것과 같은 방법입니다. 객체 지향의 3대 특성은 다음과 같습니다.

1. 캡슐화

  • 캡슐화란 관련된 데이터와 알고리즘(코드)이 하나의 묶음으로 정리된 것으로써 개발자가 만들었으며, 관련된 코드와 데이터가 묶여있고 오류가 없어 사용이 편리합니다. 데이터를 감추고 외부 세계와의 상호작용은 메소드를 통하는 방법인데, 라이브러리로 만들어 업그레이드하면 쉽게 바꿀 수 있습니다.
    • 메소드: 메시지에 따라 실행시킬 프로시저로서 객체지향 언어에서 사용되는 것. 객체지향 언어에서는 메시지를 보내 메소드를 수행시킴으로써 통신(communication)을 수행

2. 상속

  • 상속은 이미 작성된 클래스를 이어 받아서 새로운 클래스를 생성하는 기법으로 위에서 말한 기존 코드를 재활용해서 사용하는 것을 의미합니다. 객체지향 방법의 큰 장점중 하나입니다.

3. 다형성

  • 다형성이란 하나의 이름(방법)으로 많은 상황에 대처하는 기법입니다. 개념적으로 동일한 작업을 하는 함수들에 똑같은 이름을 부여할 수 있으므로 코드가 더 간단해지는 효과가 있습니다.

위의 특성들로 인해 생기는 객체지향 방법의 장점은 다음과 같습니다.

  •  신뢰성 있는 소프트웨어를 쉽게 작성할 수 있다. (개발자가 만든 데이터를 사용하기에 신뢰할 수 있다.)
  •  코드를 재사용하기 쉽다.
  •  업그레이드가 쉽다.
  •  디버깅이 쉽다.

이론적으로만 본다면 객체지향 언어는 절차지향 언어에 비해 장점이 많습니다. 하지만 프로그래밍을 할 때 항상 객체지향 언어만 사용하는 것은 아닙니다. 객체지향 언어는 어떤 모듈에 있는 하나의 기능만 필요하더라도 모듈 전체를 가져와야 하기 때문에 절차지향 프로그래밍보다 프로그램 사이즈가 더 커질 수도 있습니다. 또한 데이터에 대한 접근도 상대적으로 절차지향식보다 느려질 가능성이 많습니다. 메소드를 통해서만 접근이 가능하기 때문에 절차지향식처럼 특정 함수에 접근할 수 없고, 식으로만 접근이 가능해 속도적인 측면에서 불이익이 있습니다.

장점

  • 코드의 재활용성이 높음
  • 코딩이 절차지향보다 간편함
  • 디버깅이 쉬움

단점

  • 처리속도가 절차지향보다 느림
  • 설계에 많은 시간소요가 들어감

객체지향과 절차지향의 차이점

객체지향의 반대는 절차지향이 아니고 절차지향의 반대는 객체지향이 아닙니다. 위에서 설명한 것처럼 절차지향은 순차적으로 실행에 초점이 되어 있고 객체지향은 객체간의 관계/조직에 초점을 두고 있습니다. 이렇게 설명하면 객체지향은 절차적으로 실행되지 않냐? 라는 의문이 드는데 객체지향 역시 절차지향과 동일한 순서로 실행됩니다.



절차지향은 데이터를 중심으로 함수를 구현합니다. 이에 반해 객체지향은 기능을 중심으로 메서드를 구현하게 됩니다.
아래는 절차지향과 객체지향의 차이점 예시입니다.



someServiceCheck() {
    ...
    if (new Date().after(member.getExpirationDate()))) { ... } 
    ...
}



// Member의 일부
private Date expirationDate;
public Date getExpirationDate() {
    return expirationDate;
}
public void setExpirationDate(Date expDate) {
    expirationDate = expDate;
}

위 코드는 만료 여부를 확인하기 위해 member.getExpirationDate()로 만료일을 구합니다. 즉, someServiceCheck() 메서드는 member의 expirationDate 데이터를 사용하고 있습니다. 현재 시점에서 expirationDate 데이터는 someServiceCheck()와 Member가 공유하고 있습니다.

여기서 만료일을 1년 늘려주는 코드는 아래와 같이 구현됩니다.


renewContract() { Date date = member.getExpirationDate(); Date renewedDate = ... // date에 1년 더한 값 member.setExpirationDate(renewedDate); }

이제 Member의 expirationDate를 공유하는 함수는 someServiceCheck()와 renewContract()로 늘어났습니다. 여기서 Member는 객체가 아닙니다. Member는 객체라기 보다는 데이터를 담고 있는 구조체에 가깝습니다. 즉, 두 함수가 데이터를 공유하고 이를 기준으로 구현하는 전형적인 절차지향 방식입니다.

만료 여부를 확인하는 코드가 많아지거나 만료 데이터를 변경하는 코드가 많아질수록 expirationDate라는 데이터를 중심으로 함수를 구현하게 됩니다.


이렇게 절차 지향은 데이터를 중심으로 코드를 구현합니다. 개별 함수가 일부 기능을 구현하지만, 그 기능의 완성은 데이터 공유에 있습니다.절차 지향은 데이터를 중심으로 연관된 함수들을 묶어줍니다. 여기에 발생될 수 있는 문제점으로 예를 들어, 만료 없이 무한정 서비스를 받을 수 있다는 것을 표현하기 위해 expirationDate에 null을 할당하기로 했다고 가정합니다. 이 순간 데이터를 공유하는 모든 함수가 영향을 받습니다. 기존 코드에 null 검사를 추가해야 하고, null이면 에러가 아니라 만료일이 없도록 로직을 수정해야 되고 null 대신 9999년 12월 31일을 만료일자로 주기로 했다고 가정하면 남은 기간을 중심으로 환불 금액을 구하는 refund() 함수와 기타 만료일을 중심으로 중요 로직을 수행하는 코드들이 영향을 받게 됩니다.


객체 지향은 데이터 구조체가 아닌 기능을 중심으로 프로그램이 엮이게 됩니다. 예를 들어, Member를 구조체가 아닌 기능을 제공하는 객체로 바꾸면 다음과 같이 생성됩니다.


public class Member {
    private Date expirationDate;
    public boolean isExpired() {
        return new Date().after(expirationDate);
    }


    public int getRestDay() {
        ... //
    }


    public boolean renewContract() { // 데이터와 관련된 일부 기능이 객체로 들어옴
        .... //
    }
}

이제 다른 기능들은 만료 여부를 확인하기 위해 expirationDate 데이터를 사용하지 않고 Member가 제공하는 isExpired() 메서드를 사용합니다.


someServiceCheck() {
    ...
    if (member.isExpired())) { ... } 
    ...
}

계약 갱신 기능과 같이 일부 기능은 Member 안으로 들어가게 됩니다. 데이터와 밀접하게 연결된 기능을 데이터와 같은 객체의 기능으로 넣습니다. 이렇게 함으로써 객체의 내부 구현(특히 데이터)를 외부에 노출하지 않을 수 있습니다. 이를 캡슐화라 부릅니다.

기능 구현을 캡슐화하면 내부 구현 변경을 조금 더 쉽게 할 수 있습니다. Member 객체를 사용함으로써 만료 여부 로직을 변경할 때 다른 코드는 영향을 받지 않게 됩니다. 무한대로 사용할 수 있는 사용자의 만료 데이터를 null로 하든, 9999년 12월 31일로 하든, Member 객체를 사용하는 코드는 isExpired() 라는 기능을 사용하면 되기 때문입니다. 만료 데이터 저장 방식 때문에 영향을 받는 코드는 Member 객체 뿐이므로 변경이 수월해집니다.

자바나 C#과 같은 언어가 아니라 C와 같은 언어를 사용해도 객체 지향적으로 코딩할 수 있습니다. 핵심은 데이터 중심이 아닌 기능 중심으로 구현하는 것입니다. 즉, 여러 함수가 데이터를 공유하는 방식이 아니라 특정 함수가 다른 함수를 사용하는 방식으로 구현을 하고, 데이터 공유를 적절히 제한하면 캡슐화 효과를 얻을 수 있습니다.

요약

  • 절차지향은 데이터 중심, 객체지향은 기능 중심
  • 절차지향의 반대는 객체지향이 아니고 객체지향의 반대는 절차지향이 아님


'공부' 카테고리의 다른 글

절차지향 VS 객체지향  (0) 2018.12.22
엔디안(Endian)이란?  (0) 2018.07.15
이진법, 16진법, 비트와바이트, 인코딩  (0) 2018.07.12
마이크로소프트 REST API 가이드라인  (0) 2017.03.14
칸반  (0) 2017.03.13
XP - 익스트림 프로그래밍  (0) 2017.03.13

Heap Sort

Heap

Tree에서의 Heap을 사용 (Max Heap 또는 Min Heap)

  • 따라서 complete binary tree 임
  • Max Heap일 때 parent node는 child node(subtree)의 key보다 무조건 큼
  • binary search tree가 아님
  • Tree의 Heap은 정렬을 위함이 아닌 Insert와 Delete를 위함
  • Max(Min) Heap의 내용은 Heap 에서 확인



1. Max(Min) Heap을 만든 다음 모든 데이터를 넣음

2. (Max Heap이라 할 때) 만든 heap tree에서 root node를 지우고 정렬하고자 하는 list에 지운 root node를 넣음

3. (Max Heap이라 할 때) heap tree를 재조정해서 루트를 결정한 다음, 다시 루트를 지우고 list에 해당 값을 넣음

4. 이 방식을 트리가 없어질 때 까지 진행

퍼포먼스

시간복잡도는 O(nlog₂n)

  • n은 트리의 노드 개수

Heap tree의 전체 높이가 log₂n(완전 이진 트리)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 Heap tree를 재구성하는데에 log₂n 만큼 소요됨

insertion 또는 deletion 하는 개수가 n개 이므로 전체적으로 O(nlog₂n)의 시간이 소요됨


저장공간이 적게 필요

  • Heap tree를 구성하는 공간만 필요함 (+ 정렬된 값을 저장하는 리스트)

빠르고 저장공간이 적게 필요하기에 임베디드 시스템에 유용

Quick Sort

정렬하고자 하는 값 중, 1개를 선택하고 선택된 값을 기준으로 작으면 왼쪽, 크면 오른쪽으로 나눈 다음 2개로 분할한 리스트에서 각 정렬한 후 합침.

  • 위와 같이 분할 후, 합치는 방식으로 divide and conquer 라고 부름

    • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

    • 분할 정복 방법은 대개 순환 호출을 이용하여 구현

  • merge sort와 다르게 리스트를 균등하지 않게 분할함

Quick Sort 종류

  • Plain Quick Sort
  • Quick sort with randomized pivot
  • In-place quick sort


1. 정렬하고자 하는 리스트에서 값 1개를 선택 (선택한 값을 pivot이라 부름)

  • 보통 정렬하고자 하는 리스트의 가장 왼쪽, 중간 또는 가장 오른쪽을 선택

2. 다음 pivot을 중심으로 pivot 보다 작으면 왼쪽 pivot 보다 크면 오른쪽으로 분류 (divide)

3. 분류를 한 다음, 왼쪽과 오른쪽으로 분류된 값들 중, 각각 가장 왼쪽에 있는 수를 다시 pivot으로 잡고 다시 분류를 함.

  • 만약 수가 변하지 않으면 다음 수를 pivot으로 잡음
  • 가장 왼쪽에 있는 수가 바뀌었을 시, 해당 수를 pivot으로 잡고 다시 정렬

4. 더이상 정렬할 값이 없으면 분류한 값을 새로운 리스트에 담고 종료

예시


예시2


예시3

항상 마지막의 수를 선택

아래와 같은 방식이 in-place quick sort로 추가적인 저장공간이 필요없음

  • in-place : 입력된 리스트 내부에서 정렬이 일어남

예시4

상세 예시

6 3 8 7 9 2 1 5


pivot은 P, 왼쪽에서 시작하는 값은 L, 오른쪽에서 시작하는 값은 R이라 가정

L은 P보다 큰 값이 나올때까지 오른쪽으로 이동

R은 P보다 작거나 같은 값이 나올때까지 왼쪽으로 이동

L이나 R이 위 공식이 성립한다면 해당 값에 멈춤

  • L과 R이 전부 멈췄을 때 위치를 변경

R의 인덱스가 L보다 작아질 경우 P와 R 값의 위치를 변경

L과 R이 동일한 인덱스에 있을 경우, P와 R 값의 위치를 변경

pivot을 리스트의 가장 왼쪽 값을 선택하는 경우

1. 초기 값 세팅

6, 3, 8, 7, 9, 2, 1, 5

PR

L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

6, 3, 8, 7, 9, 2, 1, 5

PL R

3. 두 값의 위치 변경

6, 3, 5, 7, 9, 2, 1, 8

PㅤㅤL ㅤㅤ R

4. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 7, 9, 2, 1, 8

PL R

5. 두 값의 위치 변경

6, 3, 5, 1, 9, 2, 7, 8

PㅤㅤㅤL R

6. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 1, 9, 2, 7, 8

Pㅤㅤㅤㅤ L R

7. 두 값의 위치 변경

6, 3, 5, 1, 2, 9, 7, 8

Pㅤㅤㅤㅤ L R

8. 해당 위치부터 다시 2번내용

6, 3, 5, 1, 2, 9, 7, 8

Pㅤㅤㅤㅤ R L

9. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

2, 3, 5, 1, 6, 9, 7, 8

ㅤㅤㅤㅤP


1. P의 위치가 변경 () 되었으므로 P의 양쪽 리스트에서 다시 P를 선택하여 재진행 (왼쪽 먼저 진행)

2, 3, 5, 1, 6, 9, 7, 8

PR

L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

2, 3, 5, 1, 6, 9, 7, 8

P LR

3. 두 값의 위치 변경

2, 1, 5, 3, 6, 9, 7, 8

P LR

4. 해당 위치부터 다시 2번내용 수행

2, 1, 5, 3, 6, 9, 7, 8

P RㅤL

5. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

1, 2, 5, 3, 6, 9, 7, 8

P


1. P의 위치가 변경 () 되었으므로 P의 양쪽 리스트에서 다시 P를 선택하여 재진행

  • 왼쪽에 값이 1개밖에 없으므로 오른쪽만 진행

1, 2, 5, 3, 6, 9, 7, 8

P R

L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 5, 3, 6, 9, 7, 8

P R

L

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 9, 7, 8

P



1. 처음 pivot을 6으로 잡았을 때 기준으로 왼쪽은 모든 정렬이 완성됐으므로 오른쪽 진행

1, 2, 3, 5, 6, 9, 7, 8

PR

L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 3, 5, 6, 9, 7, 8

PㅤㅤR

ㅤㅤ L

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 8, 7, 9

P



P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

1, 2, 3, 5, 6, 8, 7, 9

P R

L

1. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 3, 5, 6, 8, 7, 9

P R

L

2. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 7, 8, 9

P


Quick Sort 완성

1, 2, 3, 5, 6, 7, 8, 9

pivot을 리스트의 중간 값을 선택하는 경우

1. pivot을 리스트의 인덱스 중간으로 선택

6, 3, 8, 7, 9, 2, 1, 5

L ㅤPR

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

6, 3, 8, 7, 9, 2, 1, 5

L PR

3. 두 값의 위치 변경

6, 3, 5, 7, 9, 2, 1, 8

ㅤ ㅤ L PR

4. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 7, 9, 2, 1, 8

P LR

5. 두 값의 위치 변경

6, 3, 5, 7, 1, 2, 9, 8

ㅤㅤㅤㅤP LR

4. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 7, 1, 2, 9, 8

ㅤㅤㅤㅤP ㅤ R L

5. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

6, 3, 5, 2, 1, 7, 9, 8

ㅤㅤ ㅤㅤㅤㅤP


1. P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

  • pivot을 리스트의 인덱스 중간으로 선택

6, 3, 5, 2, 1, 7, 9, 8

L PㅤR

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

6, 3, 5, 2, 1, 7, 9, 8

L ㅤ PㅤR

3. 두 값의 위치 변경

1, 3, 5, 2, 6, 7, 9, 8

L ㅤ PㅤR

4. 해당 위치부터 다시 2번내용 수행

1, 3, 5, 2, 6, 7, 9, 8

PR L

5. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

1, 3, 2, 5, 6, 7, 9, 8

ㅤㅤP


1. P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

  • pivot 5의 우측 리스트는 값이 1개이므로 왼쪽만 진행

1, 3, 2, 5, 6, 7, 9, 8

L P R

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 3, 2, 5, 6, 7, 9, 8

P R

ㅤL

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 7, 9, 8

P


1. P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

  • 좌측의 경우 1, 2인데 1에 P와 R이 동일한 위치가 되므로 변경되는 값은 없음

1, 2, 3, 5, 6, 7, 9, 8

P L

R


1. 처음 pivot을 7으로 잡았을 때 기준으로 왼쪽은 모든 정렬이 완성됐으므로 오른쪽 진행

1, 2, 3, 5, 6, 7, 9, 8

P R

ㅤL

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 3, 5, 6, 7, 9, 8

P R

ㅤL

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 7, 8, 9

P


Quick Sort 완성

1, 2, 3, 5, 6, 7, 8, 9

pseudo code

위 예시를에 해당하는 코드 컨셉

int partition(int list[], int low, int high )
{
	int left, right; int pivot; int pivot_item;
	pivot_item = list[low];
	pivot = left = low;
	right = high;

	while ( left < right ) {
		/* Move left while item < pivot */ 
		while( list[left] <= pivot_item ) left++; 
		/* Move right while item > pivot */ 
		while( list[right] > pivot_item ) right--; 
		if ( left < right ) swap(&list[left],&list[right]);
	}
	
	/* right is final position for the pivot */
	list[low] = list[right];
	list[right] = pivot_item;
	
	return right;
}

퍼포먼스

시간복잡도는 O(n·log₂n) - worst case 제외

  • list의 개수인 n 번만큼 비교 x log₂n 실행

    log₂n 번 만큼 어떻게 실행?

    Quick Sort는 리스트를 반으로 쪼개나가는 형식. 최대 degree는 2라고 볼 수 있어서 binary tree라 볼 수 있다.

    더이상 쪼갤 수 없는 크기만큼 쪼갠다면 node는 1개만 가지게 되므로 위 그림처럼 트리의 높이만큼 실행이 됨. 따라서 트리의 높이 공식인 log₂n 번 만큼 쪼개 나간다는 것을 알 수 있음.

    n 번 만큼 어떻게 비교?

    위의 각 트리의 depth마다 리스트의 크기인 n번 만큼 비교가 일어남.


    따라서 n·log₂n


  • 시간복잡도가 worst case에서는 O(n²)까지 발생함

문제점


위와 같이 이미 정렬된 상태에서 가장 왼쪽의 값을 pivot으로 잡으면 시간복잡도가 O(n²)이 발생

  • O(n²)이 나오는 경우는 리스트에서 pivot을 가장 왼쪽이나 오른쪽을 잡을 때 발생함

해결책

  • 최악의 경우를 피하기 위해 pivot을 랜덤하게 선택
  • 3개의 pivot을 고른 후, median (중앙값)을 사용
  • Insertion Sort를 사용하여 확인
    • Insertion Sort는 규모가 작고 거의 정렬이 다된 리스트에서 효율적으로 동작

Merge Sort

Quick Sort와 마찬가지로 divide and conquer 


  • split: 주어진 리스트를 두개의 서브 리스트로 완벽하게 쪼갬
  • merge: 두개의 서브리스트를 정렬된 리스트에 합침


예시

예시2

상세 예시

6 5 3 1 8 7 2 4


Split


Merge

1. 6과 5를 비교하여 작은 수를 왼쪽, 큰 수를 오른쪽에 배치하여 길이가 2인 리스트에 저장

2. 나머지 값들도 동일하게 생성


3. [5, 6] 과 [1, 3] 에서 각 리스트의 값을 비교하여 작은 순서대로 길이가 4인 리스트에 저장


4. 나머지 리스트인 [7, 8] , [2, 4]도 동일한 로직으로 적용 

5. 두 리스트에 대해 위의 로직을 적용

6. 정렬 완성


퍼포먼스

O(nlog₂n) 만큼의 속도가 나옴

  • 리스트 내 키의 개수 n * 리스트를 쪼갠 뒤, 합치는 비용 log₂n

    log₂n 번 만큼 어떻게 실행?

    merge sort에서 split은 단순히 반씩 쪼개기 때문에 값의 비교나 각 단계별 비교한 값의 이동 연산이 수행되지 않음


    Merge Sort는 리스트를 반으로 쪼개나가는 형식. 최대 degree는 2라고 볼 수 있어서 binary tree라 볼 수 있다.

    더이상 쪼갤 수 없는 크기만큼 쪼갠다면 node는 1개만 가지게 되므로 위 그림처럼 트리의 높이만큼 실행이 됨. 따라서 트리의 높이 공식인 log₂n 번 만큼 쪼개 나간다는 것을 알 수 있음.

    n 번 만큼 어떻게 비교?

    위의 각 트리의 depth마다 리스트의 크기인 n번 만큼 비교가 일어남.


O(n)개의 저장공간이 필요함

merge sort는 stable sort라고 볼 수 있음

병렬처리가 가능함

external sorting에 적응력이 높음

어레이에 있는 키의 개수 n과 쪼개고 다시 합치는 데에 log₂n만큼 든다.

Stable Sort

서브로 정렬한 결과의 순서가 뒤바뀌지 않을 때 stable sort라 함

  • merge sort, insertion sort, bubble sort

다시 말해 {key:value} 쌍의 값들이 있을 때, 같은 키 값을 가지는 2개 이상의 데이터를 정렬할 때, 기존의 순서가 바뀌지 않으면 stable 이라 하고 아니라면 unstable이라 함

웹 페이지에서 특정 데이터의 정렬된 결과를 항상 동일하게 보여줘야 한다고 할 때, unstable sort는 보여주는 데이터와 연관 없는 데이터가 추가되어도 웹페이지를 새로고침 했을 때 순서가 계속 바뀔 수 있음.

예시


'공부 > 자료구조' 카테고리의 다른 글

Sorting (Heap, Quick, Merge Sort)  (0) 2018.09.30
Sorting (Bubble, Selection, Insertion Sort)  (0) 2018.09.30
트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17

대부분 정렬의 시간복잡도는 O(n·logn)와 O() 사이임

특별한 경우 O(n)까지 가능


Internal sorting - main memory 에서 일어나는 정렬

External sorting - secondary storage(하드디스크) 에서 일어나는 정렬

Bubble Sort

이웃되는 값끼리 비교하여 자리를 변경해나가는 방식

기본적으로 O(n²). 이미 정렬이 되어 있을 경우는 O(n)

예시

예시2

Selection Sort

array에서 가장 큰 수를 찾은 다음, 찾은 수를 어레이의 맨 끝인 n자리에 놓는다.

다음 큰수를 찾은 다음, 어레이의 n-1자리에 넣는다. 이때 찾은 수와 해당 자리에 있는 수의 자리를 바꾼다.

O(n²)의 performance가 나옴

  • bubble sort와 똑같이 O(n²)이지만 bubble sort에 비해 값의 교환 수가 적음

이미 정렬이 되어 있어도 O(n²)임

예시

예시2

Insertion Sort

새로운 키를 넣을 때, 정렬을 하고 있는 어레이에서 자신이 어디에 들어가야 할지 결정한 다음 맞는 자리에 넣는다.


performance: O(n²) 이미 모든 키가 정렬되어 있으면 O(n)

짧은 list에서 단순하고 좋음.
이미 부분적으로 정렬이 되어 있는 경우에 좋다

예시

예시2

Selection Sort vs Insertion Sort

Selection Sort는 정렬되어있지 않은 수를 전부 확인 해 가장 큰 수를 찾아야 함

  • 정렬이 전부 되어 있어도 모든 수를 비교

Insertion Sort는 정확한 위치에 들어가는 것을 결정하기 위해 정렬 중인 어레이를 확인 해야 함

  • 필요한 값만 읽고 정렬된 리스트에서 비교

n개의 element가 있다고 가정할 때, Selection은 n번만 쓰면 됨. 뒤에서부터 쓰기 때문에 어레이의 key들이 이동할 필요가 없지만, Insertion은 key들이 전부 이동할 수도 있기 때문에 write가 더 많이 일어남

  • 예를 들어, 2 3 4 5 1 의 값을 Insertion Sort로 정렬한다고 하면, 마지막 1을 정렬하기 위해 2 3 4 5 의 값이 한 칸씩 이동해야함

만약 write비용이 비쌀 경우 (예를 들어, flash memory) Insertion Sort보단 Selection Sort이 더 좋음

요약

  • bubble, selection, insertion sort의 시간복잡도 worst case는 O(n²)
  • 만약 전부 정렬된 리스트를 비교한다면 bubble, insertion sort는 O(n)이지만 selection은 여전히 O(n²)


'공부 > 자료구조' 카테고리의 다른 글

Sorting (Heap, Quick, Merge Sort)  (0) 2018.09.30
Sorting (Bubble, Selection, Insertion Sort)  (0) 2018.09.30
트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17

Preorder

  • Visit the root.
  • Visit the left-subtree.
  • Visit the right-subtree.

Inorder

  • Visit the left-subtree.
  • Visit the root.
  • Visit the right-subtree.

Postorder

  • Visit the right-subtree.
  • Visit the left-subtree.
  • Visit the root.

Breadth First Search(BFS) or Level order traversals

  • starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.

Depth First Search(DFS)

예시


'공부 > 자료구조' 카테고리의 다른 글

Sorting (Heap, Quick, Merge Sort)  (0) 2018.09.30
Sorting (Bubble, Selection, Insertion Sort)  (0) 2018.09.30
트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17

Spanning Tree

N개의 노드들의 connected graph에서 얻을 수 있음

  • depth-first traversal 또는 breadth-first traversal 을 통해 확인
  • N개의 node와 N-1개의 edges로 된 Tree
  • cycle은 그래프로부터 제거됨 - 한번 방문한 노드는 다시 방문하지 않기에 cycle이 생길 수 없음

한개 이상의 spanning tree는 같은 그래프에서 구할 수 있음

추가정보

그래프가 connected 일 때, dfs나 bfs는 암묵적으로 그래프 G의 edge를 두개의 집합으로 분리

  • T(for tree edges): edge의 집합으로 사용되거나 search 도중에 방문
  • N(for nontree edges): 남아있는 edge의 집합
  • T의 edge는 G의 모든 vertex들을 포함하는 트리를 형성

요약

  • Spanning Tree는 G의 edge로만 구성되며 G안의 모든 vertex들을 포함하는 트리
  • 다시말해, 정점집합 v를 그대로 두고 (각 점들을 움직이지 않고) 간선(link)를 v-1개(v개의 link로 연결하면 cycle이 생김)만 남겨 트리가 되도록 만든 것.

Spanning Tree의 이점

  1. spanning tree에 nontree edge를 추가한다면 cycle이 됨

  2. spanning tree는  V(G’) = V(G) 이고 G’는 connected 와 같은 G의 minimum 그래프 G’임

  3. |E(G’)| = n - 1 이라면 |V(G)| = n 임
    • edge를 최소한으로 사용하므로 minimum cost spanning tree 이다.

예시

Depth-First Traversal Search

Breadth-First Traversal Search

Minimum Spanning Tree

N 개의 노드들의 weighted connected 그래프에서 얻을 수 있음

총 weighted가 최소한인 spanning tree

일반적으로 unique가 아님

minimum-cost 문제를 모델링하고 해결하는데 사용됨

어느 노드에서 시작하느냐에 따라 결과가 달라질 수 있음

추가정보

weighted undirected 그래프의 spanning tree 비용

  • spanning tree 안에 있는 edge의 cost(weight)의 합
  • 최소비용의 spanning tree
  • KruskalPrimSollin 알고리즘이 대표
  • greedy method: 단계적으로 최적의 해결책을 구성하고, 어떤 기준을 사용하여 각 단계에서 최적의 결정을 내림

spanning tree는 최소비용을 기준

  • 그래프 안에 있는 edge만을 사용
  • 정확하게 n-1 개의 edge를 사용
  • cycle을 유발할 수 있는 edge는 사용하지 않을 수 있음

요약

  • 각 연결한 link의 edge가 가장 작은 신장트리를 말한다.
  • 여기에 prim's, kruskal's, sollin's algorithm이 대표적이고 이 알고리즘들은 전부 greedy method이다. greedy 방법은 현재의 상황에서 자신이 최선의 선택을 하는 방법을 사용한다.

Prim 알고리즘

  1. 그래프의 node에서 시작
  2. 모든 인접한 node들을 계산
  3. 최소한의 edge의 weight를 선택
  4. 선택된 인접한 노드에서 계속 시작
    • 선택되지 않은 모든 edge를 계산
    • 새로 인접한 모든 edge들을 계산
    • 최소한의 weight를 가진 edge를 선택. 단 cycle은 피함
  5. 그래프의 모든 node들을 포함할 때까지 진행하고 모든 노드는 1번만 방문하도록 고려

추가정보

단일 vertex를 포함하는 T 라는 트리에서 시작

T ∪ {(u,v)}가 트리(cycle은 안됨)가 되도록 T의 최소비용인 edge(u,v)를 추가하고 T가 n-1 edge를 포함할 때까지 이 단계를 반복

알고리즘의 각 단계에서 선택되는 edge의 집합

  • prim 알고리즘은 나무를 형성하고 kruskal 알고리즘은 숲을 형성

요약

  • 어느 한 점을 선택해 해당 점에서 갈 수 있는 최소의 edge를 결정한 다음 잇는다이은 다음 두 점에서 갈 수 있는 최소의 edge를 다시 결정해 잇고 이러한 방식으로 모든 vertex를 이을 때 까지 한다.

예시

위와 같은 그래프를 prim알고리즘을 사용하여 탐색

B-D의 edge를 선택할 경우, cycle이 되기 때문에 선택하지 않음

예시2


위와 같은 그래프를 prim알고리즘을 사용하여 탐색

Kruskal 알고리즘

prim 알고리즘과 다르게 어느 한 vertex를 선택하지 않고 전체 link의 edge중 가장 작은 edge를 찾아 잇는다그 다음 가장 작은 edge를 이어가는 방식

예시

위와 같은 그래프를 kruskal 알고리즘을 사용하여 탐색

Dijkstra 알고리즘

source에서 destination 까지 최단거리는 무엇일까?

Dijkstra 알고리즘은 단일 출발지에서 그래프 이론 안에 있는 가장 짧은 경로 찾기 문제를 해결하는 알고리즘

directed와 undirected 그래프 모두 작동하지만 모든 edge는 양수의 weight를 가져야 함

접근법: greedy 알고리즘

Input: Weighted 그래프 G={E,V} 와 출발지 vertex v∈V이고 모든 edge는 양수

Output: 주어진 출발지 vertex v∈V 에서 다른 모든 vertex까지의 최단 경로 길이 (또는 최단 경로 그 자체)


출발점에서 모든 목적지까지의 가장 짧은 경로를 탐색 - greedy 알고리즘

  • 양수의 edge 비용만 탐색: Dijkstra 알고리즘
  • 음수를 포함한 모든 edge 비용을 탐색: Bellman-ford 알고리즘
  • 모든 pair의 가장 짧은 경로 탐색 (dynamic programming): floyd 알고리즘

기본컨셉

edge가 양수인 길을 선택


(A,B)  (A,C) 이므로 (A,B) 선택

(A,B,C)  (A,C), (A,B,D) 이므로 (A,B,C) 선택

(A,B,D)  (A,B,C,E), (A,B,C,F), (A,B,C,G) 이므로 (A,B,D) 선택

위와 같은 방법으로 A에서 모든 vertex까지의 모든 경로를 찾을때까지 반복

기본컨셉설명

  1. S는 가장 짧은 경로를 가지는 v0을 포함하는 vertex들의 집합을 나타내도록 함
  2. S가 아닌 w의 경우, dist[w]는 v0에서 출발해 S의 vertex들을 지나고 w로 끝나는 최단 경로의 길이라고 나타냄
  3. S 안에 있지 않은 vertex u를 찾을 수 있고 dist[u]는 minimum이고 S안에 u를 추가함
  4. 경로를 적절하게 유지


해당 알고리즘의 시간복잡도는 (|V|2)

예시

A 에서부터 시작

요약

  • 시작점에서 모든 도착점까지 가장 짧은 path의 cost를 찾는 알고리즘.


'공부 > 자료구조' 카테고리의 다른 글

Sorting (Bubble, Selection, Insertion Sort)  (0) 2018.09.30
트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15

Graph

트리는 그래프의 특수한 케이스

그래프는 다양한 문제를 모델링 하는 것과 문제를 해결하기 위해 알고리즘을 고안하는데 유용


용어

vertex, vertices(vertex의 복수형): 트리의 Node와 동일개념

  • root node와 leaf node가 아닌 모든 노드

edge: 트리의 link와 동일개념

  • undirected edge ( = undirected graph)
  • directed edge ( = directed graph)
    • 단방향, 양방향
    • in-degree (해당노드로 들어오는 방향성 있는 edge), out-degree (해당노드에서 나가는 방향성 있는 edge)
  • weighted edge ( = (directed or undirected) weighted graph)
    • 서울 - 제주도 와 서울 - LA의 weight는 다름

정의1

graph G=(V,E)


V(G): empty가 없는 vertex들의 유한한 집합

  • v1, v2, ..., vi, vj, ... ∈ V(G)

E(G): empty가 가능한 유한한 edge들의 집합

  • (vi, vj) ∈ E(G) 이면 vi, vj ∈ V(G)

undirected graph

  • (vi,vj) = (vj,vi)

directed graph ordered

  • <vi,vj> ≠ <vj,vi>

집합의 표현 예시

V(G1) = {0,1,2,3}; E(G1) = {(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}

V(G2) = {0,1,2,3,4,5,6}; E(G2) = {(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)}

V(G3) = {0,1,2}; E(G3) = {<0,1>,<1,0>,<1,2>}

예시

상세

degree (of a vertex): vertex에 인접한 edge의 수

in-degree (of a vertex v): 방향성 있는 edge가 vertex를 향하고 있는 edge의 수

out-degree (of a vertex v): 방향성 있는 edge가 vertex에서 나가고 있는 edge의 수

그래프 제한사항

vertex에 edge가 없거나 자기자신을 가리키는 edge는 없음

하나의 vertex에서 다른 vertex를 연결하는 edge가 중복인 경우는 없음 (<=> multigraph)

정의2

  • subgraph: 그래프의 한 부분

  • connected graph: 모든 vertex가 연결된 그래프

  • disconnected graph: 한개의 vertex라도 연결되어 있지 않는 그래프

  • adjacent nodes: 인접한 vertex간 연결되어 있는 node 관계

  • complete (connected) graph: 모든 vertex가 adjacent node로 표현이 가능한 그래프. 전부 연결되어 있으므로 connected graph임

예시

정의3

  • path: vertex X에서 vertex Y까지 가는 edge의 연결된 경로
    • 아래 그림에서 A에서 D까지 가는 경로는 (A,B), (B,C), (C,D) 이므로 length=3임
  • cycle: 출발한 노드 다시 도착할 수 있는 구조
    • 아래 그림에서 ABCDA는 cycle 구조
  • cyclic graph: cycle 구조가 존재하는 그래프
  • acyclic graph: cycle 구조가 존재하지 않는 구조 (=tree)

예시

그래프 표현방식

Adjacency Matrix

(n x n) 2차원 배열 - (vertex)(edge)로 표현

  • n은 그래프 안에 존재하는 노드의 개수

만약 v1가 v2가 adjacent하다면 1로 표현하고 그렇지 않으면 0으로 표현




예시

장점

공간절감

방향성이 없는 그래프일 때, 공간의 절반을 절약할 수 있음

저장할 때, 위 또는 아래의 삼각형모양의 데이터만 저장하면 됨

방향성이 없는 그래프일 때, vertex i의 degree를 구하는 공식은  임

그래프 탐색방법

그래프에서 모든 vertex를 방문하는 방법은 아래와 같음

  • depth-first traversal
  • breadth-first traversal

Depth-First Traversal

  1. 한 노드에서 더이상 새로운 인접한 노드가 없을 때까지, 인접한 노드를 재귀적으로 방문하는 방법
  2. 재귀적으로 실행한 다음, 뒤로 돌아갈 때, 다음 새로운 인접한 노드를 재귀적으로 방문
  3. 처음 시작한 노드에서의 인접한 노드를 재귀적으로 전부 방문했다면 종료

방문 순서의 방법은 preorder tree traversal 과 유사


재귀적으로 실행되는 순서는 stack을 사용하여 구현하면 쉽다!

adjacent matrix로 구현한다고 하면 시간복잡도는 O(n2)임

예시


방문경로

Breadth-First Traversal

  1. 시작노드에서 인접한 노드를 한번 방문함
  2. 그 다음, 한번도 방문하지 않은 모든 인접한 노드를 방문
  3. 모든 노드를 방문했다면 종료

방문 순서의 방법은 level-order tree traversal 과 유사함

queue를 사용하여 구현하면 쉽다!

adjacent matrix로 구현한다고 하면 시간복잡도는 O(n2)임

예시

방문경로

'공부 > 자료구조' 카테고리의 다른 글

트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13

+ Random Posts