IT's me

[자료구조] 이진 트리의 순회(Traversal) (2)

오늘은 아진트리의 순회 방법에 있어서

좀 더 유연한 동작방식을 적용하기 위해서

함수 포인터를 이용해 보도록 하겠다.

저번 포스팅이 재귀의 개념이 핵심이었다면

이번 포스팅은 함수 포인터가 핵심이 된다.

가장 첫 줄을 보면 함수 포인터가 선언이 되어있다.

반환형은 void 그리고 매개 변수는 BTData타입이다.

이 함수 포인터를 순회 함수의 두 번째 매개변수로 넣어준다.

그리고 데이터를 다루는 부분을 이 함수 포인터로 대체한다.

이제는 인자로 들어온 함수에 따라 데이터를 다루는 방식이 달라진다.

ShowIntData(int Data) 함수를 인자로 전달해주고 실행

이로써 이진 트리의 순회가 좀 더 유연성을 가지게 되었다.

데이터를 다루는 방식이 달라지더라도 함수를 재 선언할 필요가 없고

함수를 하나 선언해서 넘겨주기만 하면 되는 것이다.

이는 STL의 알고리즘에 쓰이는 콜백 메커니즘의 기본이다.

이러한 동작 원리를 잘 이해해서 좀 더 유연한 프로그래밍을 할 수 있도록하자.

[자료구조] 이진 트리의 순회 (Traversal) (1)

앞서 이진 트리를 만드는 도구에 대해 알아보고,

간단하게 이진 트리를 만들어보기까지 했다.

그렇다면 만들어진 이진 트리의 정보를

가져오기 위해 어떠한 방법을 써야할까?

이진 트리의 순회를 이용하여 트리의

루트부터 단말노드까지 모든 데이터를

순회하며 정보를 가져올 수 있다.

이진 트리의 순회를 하기 위해서는 재귀의 개념이 필요하다.

들어가기에 앞서 순회의 세가지 방법에 대해 알아보도록 하자.

위 그림 처럼 노드가 세개밖에 없는 경우는 매우 간단하다.

하지만 트리의 깊이가 깊은 경우에는 상당히 복잡할 수도 있다.

만약 중위순회 방법으로 순회를 구현했다면

트리의 깊이가 얼마가 되었든간에 순차적으로

중위 순회를 하며 모든 데이터를 가져올 수 있어야 한다.

ex) 중위 순회의 구현

여기서 재귀의 개념이 사용되는데,

처음 루트노드의 주소값이 전달이되고

함수가 시작이 되면

1. 종료 조건을 체크한다.

현재의 노드가 아무런 데이터를 가지고 있지 않으면 리턴하여 함수를 종료한다.

2. 데이터를 가진 노드라면 (공집합 노드가 아니라면)

자신의 왼쪽 트리를 함수의 인자로 전달하여 순회 함수를 또 한번 호출한다. (재귀의 개념)

3. 자신의 왼쪽 트리의 순회가 끝나고 (2에서 실행했던 함수가 끝나면)

자신이 가진 데이터를 출력한다.

3. 데이터를 출력한 후 (중위 순회이기 때문에 왼쪽에서 오른쪽)

자신의 오른쪽 트리를 함수의 인자로 전달하여 순회 함수를 또 한번 호출한다. (재귀의 개념)

4. 함수 종료

ex) 중위 순회

이진 트리의 중위 순회 결과

위의 중위 순회 동작 순서

오늘은 이진 트리의 순회에 대해 알아보았다.

재귀의 개념이 들어가다 보니까 살짝 어렵게 느껴지기도 한다.

다음에는 함수포인터를 이용하여 이진 트리의 순회를

좀 더 세련되게 표현해보도록 하겠다.

[자료구조] 이진 트리의 이해

연결 리스트는 대표적인 선형 구조의 예이다.

오늘 포스팅할 이진 트리는 비선형 구조의

대표적인 예라 할 수 있겠다.

일단 이진 트리는 

1. 배열 기반

2. 연결 리스트 기반

으로 나눌 수 있는데 연결 리스트 기반으로 알아보자.

이진 트리에 들어가기 앞서 알아둘 내용은

1. 2개의 자식 노드를 가질 수 있다는 점과

2. 하나의 노드도 이진 트리라는 점이다.

자식 노드가 없는 노드는 공집합 노드를 가지게 되는데

자식이 하나 혹은 하나도 없는 노드 또한 이진 트리라고

기대할 수 있게 하기 위함이라고 한다.

이진 트리를 표현한 구조체

헤더 파일에 선언된 함수들

구현

예시

짚고 넘어가야할 부분

구현 부분의 MakeLeftSubTree() 함수를 보면

추가하려는 자리에 기존 데이터가 있으면

삭제하고 대체하게 되는데 이 과정에서

삭제하려는 노드의 서브트리가 존재하게 되면

메모리 누수로 이어지게 된다.

이 해결책으로 순회라는 방법이 있는데

다음 포스팅에 계속 이어 가보도록 하겠다.

이진 트리를 이해하기 위해 간단한 구현을 해보았다.

앞으로 이진 트리에 대한 어마어마한 내용이 남아 있기 때문에

꼭 마스터 하고 넘어가도록 하자.

[자료구조] 연결 리스트의 이해(3)

더미 노드 기반의 연결 리스트에 대해 알아보자.

그 전 포스팅에서 보았듯이, 삽입, 삭제, 참조 시에

첫 노드와 그 이외의 노드의 처리과정이 차이가

나는 것을 볼 수 있었다. 모든 노드들을 일관되게

처리를 해주는 것이 좋은 코드라고 말했는데,

이는 더미 노드를 이용하면 쉽게 해결할 수 있다.

더미 노드란?

유요한 데이터를 저장하지 않는 노드이다.

즉, 헤드가 데이터를 가지지 않는 껍데기(?) 뿐인

노드를 물고있는 것이다. 아래 그림을 보자

기존의 연결 리스트

더미 노드 기반 연결 리스트

왜 이렇게까지 해야할까 의문이 들수도 있지만

연결 리스트의 구현이 더욱 복잡해 졌을 때, 코드의

일관성은 무시할 수 없기 때문이다. 때문에 현재

더미 노드 기반의 연결 리스트가 표준에 더욱 가깝다.

더미 노드를 통해 구현한 삽입, 삭제, 참조를 보도록 하자.

첫 노드를 할당했지만, 아무런 데이터를 물고 있지 않다.

데이터는 이 더미노드 뒤부터 추가되게 된다.

01. 삽입

더 이상 head를 다루지 않아도 된다.

head는 더미 노드이고 실제 데이터는 그 후로 저장되어 있기 때문

02. 참조

03. 삭제

기존의 연결 리스트와 다른 차이점이 보이지 않는다.

다만 처음에 head가 데이터를 저장하지 않는 노드를 물고 있다.

즉, 첫 노드는 아무런 데이터가 없다.

첫 노드를 제외한 모든 코드를 다루는 것이기 때문에

기존의 코드에서 첫 노드를 다루는 부분만 삭제해주면 된다.

[자료구조] 연결 리스트의 이해(2)

오늘은 연결 리스트의 초기화, 삽입, 조회, 삭제가 어떻게

동작하는 지에 대해 알아보고 가는 시간을 갖도록 하겠다.

자료구조란 학문은 그림을 그리면서 이해하는 것이 가장 중요하다.

아래의 포스팅은 코드만 나와있지만, 공부를 제대로 하고자 한다면

자신이 직접 그림을 그리면서 이해를 해야한다.

01. 초기화

02. 삽입

03. 조회

04. 삭제

연결 리스트가 어떻게 동작하는지 간단한 코드 예시를 보았다.

앞서 말했듯이 자료구조라는 학문은 그림을 그리면서 이해하는

것이 무엇보다 중요하다. 그림도 같이 올려서 포스팅 하고 싶지만

많은 시간이 걸리기 때문에 소스 코드만 포스팅하게 되었다.

위의 소스 코드를 보면 연결 리스트의 삽입, 조회, 삭제의 과정에서

첫 노드와 첫 노드 이외의 모든 노드의 처리과정이 분리되어

있다는 것을 알 수 있다. 이 보다 좀 더 좋은 코드가 되기 위해서는

모든 처리가 while(1){ .. } 안에 들어가야 할 것이다.

하지만 이는 좀 더 복잡한 코드가 나오게 할 뿐이다.

이에 대한 해결책은 더미 노드라는 것인데,

이렇게 첫 노드와 나머지 노드를 나누어 처리하는 이유와

더미 노드란 무엇이며 어떻게 적용되는 지에 대해서는

다음 포스팅에서 계속 이어 가도록 하겠다.

[자료구조] 연결 리스트의 이해(1)

연결 리스트는 크게 배열 기반 연결 리스트와

연결 리스트 기반 연결 리스트가 있는데

우리가 흔히 사용하는 연결리스트는 후자이기 때문에

연결 리스트 기반의 연결 리스트에 대해 알아보도록 하겠다.

들어가기에 앞서 배열과의 비교가 우선시 되어야 할 것같다.

배열이라 함은 기본 제공되는 상당히 훌륭한 자료구조이다.

배열의 가장 큰 장점 중 하나는 index를 통한 순차접근이다.

배열의 가장 큰 단점 중 하나는 크기가 결정되어야 한다는 것인데

이는 매우 큰 부담으로 작용한다. 물론 크기를 바꿀 수 있는 방법이 없는 것은

아니지만, 그에 따른 비용이 만만치 않기 때문에 큰 단점이라 할 수 있다.

때문에 배열보다 좀 더 유연하고 순차 접근을 훌륭히

 수행할 수 있는 것이 필요한데 이것이 바로 연결 리스트이다.

malloc를 이용한 동적할당이 기본이 되어야하고,

할당된 메모리를 어떻게 접근하고 관리할 것인가가

연결 리스트를 이해하는 것의 가장 큰 이슈가 될 것이다.

1. 구조체의 이해

2. 동적 할당 (malloc)

3. 어떻게 연결할 것인가?

4. 어떻게 순차 접근할 것인가?

1. 구조체의 이해

힙에 할당되어 저장되는 자료를 우리는 노드(node)라고 부른다.

노드는 C에서 구조체 변수이다. (기본 제공 타입이 아님)

이렇듯 노드에는 데이터를 담을 공간과

다음 노드를 가리킬 구조체 포인터를 가지고 있다.

2. 동적 할당

malloc, free는 C언어 기본서 참고

3. 어떻게 연결할 것인가?

들어가기에 앞서 노드의 연결과 참조를 위한 핵심을 훑어보자.

next는 현재 노드의 다음 노드를 가리키고 있다.

이렇게 노드들을 쭉 연결 한다면 비엔나 소시지처럼

연결된 모양이 될 것이고, 결과적으로는 첫 노드의

주소값만 알고 있다면 모든 노드를 탐색할 수 있다.

n1,n2는 노드이고 각각의 데이터를 가지고 있다.

next라는 구조체 포인터는 자신의 다음 노드를 가리키도록 한다.

( 주의할 점은 꼭 현재 노드의 뒤에만 새로운 노드가 올 수 있는 것은 아니다. )

현재 노드의 앞 뒤 어느 곳에서든 노드가 추가될 수 있어야 한다.

4. 어떻게 순차 접근을 할 것인가?

n1의 next는 자신의 다음 노드를 가리키고 있기 때문에

*를 사용한다면 자신의 다음 노드에 접근할 수 있다.

연결 리스트와 배열과의 차이점 그리고 연결 리스트를

구현하기에 앞서어떠한 핵심을 공략해야하는지에 대해

간단하게 알아보았다. 다음 포스팅부터는 이슈들을 하나하나

 해결해가며 연결 리스트를 구현해 보도록 하겠다.

[자료구조] 단순 정렬 알고리즘

1. 버블 정렬

2. 삽입 정렬

3. 선택 정렬

정렬 알고리즘을 자료구조로 보기는 힘들지만

자료구조의 구성에 있어 꼭 필요한 부분이기 때문에

정렬 알고리즘에 대해 간략하게 알아보는 시간을 가지겠다.

그 중에서도 단순 정렬 알고리즘

1. 버블 정렬

가장 널리 알려진 정렬방법이 아닌가 한다.

대학교수님이 굉장히 강조를 하셔서 아직 기억에 남아있다.

하지만 n^2 이라는 어마어마한 시간복잡도를 보이기 때문에

정렬 대상이 소규모일 경우에만 사용하도록 한다.

정렬 알고리즘은 개인적인 생각으론 그림으로

이해하는 것이 가장 좋다고 생각하는데, 그림을

그릴 시간이 없는 관계로 ㅜㅜ 

잘 정리해놓은 포스팅을 소개하도록 하겠다.

http://prosto.tistory.com/161

2. 삽입 정렬

선택 정렬과 엄청 유사하다.

키(key)값을 가지고 비교를 해나가며

정렬을 하는 것이 특징이다.

이 또한 밑의 포스팅을 보면 이해가 갈 것이다.

http://prosto.tistory.com/163

3. 선택 정렬

처음부터 마지막까지 해당 자리에

적절한 값을 잡아가는 것이 특징이다.

무척 단순하다. 따라서 구현을 하는 것이

상당히 쉽다. 하지만 단순 정렬 알고리즘은

모두 n^2의 시간복잡도를 보인다는 것.

http://prosto.tistory.com/159

Prosto님의 힘을 빌려 단순 정렬 알고리즘인

버블 정렬, 삽입 정렬, 선택 정렬에 대해 알아보았다.

구현이 간편하다는 장점말고는 딱히 다른 장점을

찾아볼 수가 없다. 때문에 STL의 sort 알고리즘을 보면

위의 단순 정렬 알고리즘이 아닌퀵 소트로 구현이 되어

있다는 것을 볼 수 있다. 퀵 소트는 상당이 복잡한 알고리즘인데

 그 만큼 성능상의 이점이 있기 때문이다.

재귀 함수

재귀 함수의 기본적 이해

-> 자기 자신을 다시 호출하는 형태의 함수

재귀를 공부해야 하는 이유

자료구조나 알고리즘을 공부할 때

재귀 함수가 유용하게 사용되어 진다.

탈출 조건의 필요성

 - 무한 재귀 호출을 피하기 위해서 (무한 루프)

 - 무한 재귀 호출 -> stack overflow

 탈출 조건의 이해

void Re(int n){

...

if(n==1)

return;

Re(n-1);

}

int main(){

int a= 5;

Re(5);

}

--> return은 값의 반환 뿐만 아니라

      함수를 빠져나올 때 쓸 수 있다.

재귀 함수 Design

- 팩토리얼 계산을 위한 알고리즘

int factorial(int n){

if(n==1) return 1;

else return n * factorial(n-1);

}

재귀함수의 효율성

속도나 메모리의 절약을 의미하는 것이 아니다.

오히려 잦은 함수 호출로 인한 속도 저하와 

stack overflow, 즉 다룰 수 있는 범위를

초과하는 문제가 발생 할 수 있다.

논리적 사고를 그대로 옮기거나

코드를 단순화 하기에 적합하다!

static 변수

1. 함수 내부 및 외부에 선언 가능하다.(전역, 지역)

2. 한번만 초기화 된다. (전역 변수의 특징)

3. 함수 내부에서 선언될 경우 함수 내에서만

    접근이 가능하다. (지역 변수의 특징)

void fct(){

static int val = 0;

val++;

printf("%d ", val);

}

int main(){

int i;

for(i = 0; i<5; i++)

fct();

}

1. fct() 함수가 끝나도 static 변수는 

메모리 상에서 지워 지지 않는다.

2. static 변수의 초기화는 단 한번.

때문에 함수가 다시 호출되도

초기화 부분은 무시하게 된다.

따라서 출력 결과는

1 2 3 4 5

가 된다.

프로그램 실행 전 컴파일 과정에서 메모리 공간을 할당 받고

전체 프로그램이 종료될 때까지 동일 메모리 공간을 보유한다.

--> 전역 변수의 특징과 같다. 전역 변수도 static 변수이다.

전역 변수와 static 변수의 차이점?

누구나 접근 가능한 전역 변수와는 달리

선언된 지역 내에서만 접근이 가능하다는 장점이 있다.

함수 포인터와 void 포인터

함수포인터와 void 포인터

이것들이 도대체 무엇인지에 대해

정말 간만보는 포스팅을 진행하겠다.

함수는 CPU에 의해서 실행된다.

CPU에 의해 실행되려면 메모리에 올라와 있어야한다.

(메인 메모리)

함수의 몸체가 메모리 상에 올라가고

그 놈이 어딨는지를 알아야 한다.

고로 함수의 이름이 함수의 몸체가 

메모리의 어디에 있는지 가리키는 포인터가 된다.

void fct(int n, int n2){

..

..

}

함수 포인터의 구성 = 몸체의 주소 + 자료형

함수의 포인터 타입을 결정짓는 요소

1. 리턴 타입

2. 매개 변수 타입

함수 포인터의 선언

void (*pfct)(int n, int n2) = fct;

리턴 타입과 매개 변수의 타입이 같다!

fct는 포인터이기 때문에 선언된 함수포인터에

자신이 가리키는 함수의 주소값을 넘겨줌.

int n = 10;

int * p = &n;

int *fp = p;

위와 같은 형태이다.

사용법 또한 같다

pfct(1,2);

fct(2,4);

pfct = fct ==> 주소값도 같다

void형 포인터

포인터는 주소값을 저장할 수 있는 변수

하지만 자료형에 대한 정보가 제외된 형태.

void* p;

 int, char 구분 없이 저장 가능하다.

int n = 10;

char c = 'c';

void* vp;

vp = &n;

vp = &c;

가능한 이유?

자료형에 대한 정보가 제외되어 있기 때문.

하지만 기능이 제한된다.

포인터 연산, 메모리 참조와 관련된 일에 활용 할 수 없다.

왜?

포인터 연산을 했을 때 메모리를 얼마나 참조할 것인가에 대한 정보 --> 자료형

void 포인터는 어떠한 데이터 특성을 지니는지의 정보가 없다

메모리를 어떻게 참조할지 모른다.(타입에 대한 정보가 없기 때문)

int main(){

int n = 10;

void * vp = &n;

*vp = 20;

 --> 1바이트를 참조할지 4바이트를 참조할지 모른다.

vp++;

--> 이 또한 마찬가지

}

함수 포인터와 void 포인터의

정말 기본적인 내용에 대해 알아보았다.

활용법에 대해서도 충분히 알아야 할 것 같으니

다음 포스팅에서 좀 더 자세히 알아보도록 하겠다.

GoodBye~