BLOG. 2won0

Ubuntu 11.04 에서 텍스트에디터인 sublime text 2를 설치해보자.

직접 sublimetext 홈페이지 (www.sublimetext.com) 에 들어가서 파일을 받은뒤에 압축을 풀고 사용해도 되지만

콘솔창에서 직접 apt-get 명령어를 통해서 설치할 수 도 있다.

콘솔창을 열고 다음과 같이 순서대로 진행한다.

#sudo -i

#add-apt-repository ppa:webupd8team/sublime-text-2

#apt-get update

#apt-get install sublime-text

설치가 완료 된 후에 설치된 Application을 보면 아이콘이 생성되어 있을 것이다.

다음과 같다.

프로그램을 실행시켜보면 다음과 같이 잘 돌아가는 모습을 확인할 수 있다.

2차원 배열을 쓰기 위해서는 먼저 더블포인터를 이용해야 하고, 이를 할당하기 위해서는 반복문을 이용해야 한다.

위의 예제 코드에서는 10 x 10 사이즈의 배열을 생성하여 모든 값에 1을 저장후 출력해본뒤 free 시키는 단계로 작성된 것이다.

그리고, 마지막으로 free 시켜줄 때에도 반복문을 이용해서 free 시켜줘야 하는데 이때 순서가 malloc 할때와 반대로 free 됨을 주의해야 한다.

랜덤하게 2진트리를 생성하고, 각각의 방식 (Preorder, Inorder, Postorder) 으로 출력하는 프로그램을 만들어 보았다.

먼저 랜덤하게 생성되는 트리는 중복되지 않는 20개의 숫자를 랜덤하게 생성하여 이진트리로 만들었다.

랜덤하게 생성된 이진트리의 구조는 다음과 같다.

이를 각각의 방식으로 출력해주는 함수를 만들어 출력해 주었다.

출력함수는 다음과 같다.

Preorder 방식

Inorder 방식

Postorder 방식

다음과 같이 제대로 출력되는 모습을 확인 할 수 있다.

Binary Tree Traversal, 즉 2진트리 탐색에 대해 알아보자.

정보처리기사 시험문제에도 나오는 이론이기 때문에 중요할듯 싶다 ㅋ

이진트리탐색에서 항상 나오는 3가지 방법, Inorder Traversal, Preorder Traversal, Postorder Traversal이 있고,

한가지 더 추가적으로 보자면 Levelorder Traversal을 이야기 할 수 있을 것이다

이들의 방법은 각각 이렇다.

먼저 그림을 보고 이해하자면

다음과 같은 Binary Tree, 즉 2진트리가 있을 때

Inorder는 Left child -> Root -> Right child 순으로,

Preorder는 Root -> Left child -> Right child 순으로,

Postorder는 Left child -> Right child -> Root 순으로 탐색을 하는 방식이다.

각각 Root를 기준으로 Root가 언제 탐색되는지에 따라서 기억 하면 쉬울 것 같다.

그리고 Level Order방식은 트리의 레벨에 따라서 차례대로 탐색하면 된다.

각각의 방식으로 탐색을 하게 되면 결과는 다음과 같을 것이다.

Tree와 비교하면서 순서를 따져보면 쉽게 이해할 수 있을 것이다.

전체 소스 및 보고서 다운받기

다항식을 Linked LIst를 이용하여 표현하기 위해 다음과 같은 node를 구성하였다.

즉 2x^3 이라는 항이 있다면 node에 coef = 2; exp = 3; 이 저장되는 방식이다.

이러한 다항식을 List로 표현해 보았다.

값으로 0, 0을 가지는 header노드와 -1, -1을 가지는 tail 노드를 포함하여 List형태로 표현한다.

makePolynomial() 이라는 node* type의 함수를 이용하여 다항식을 생성해 보았다.

여기서 조건은 메인함수에서 최고차항의 지수를 입력받고, 항이 생성되는 조건은 70%의 확률로 항의 존재유무를 결정한다.

또한 SelectPlusMinus() 라는 함수를 이용하여 랜덤하게 항의 계수가 양수가 될수도있고, 음수가 될수도 있게 하였다.

이와 같은 방식으로 두개의 다항식을 생성한 뒤 두 다항식을 더해주었다.

다항식의 덧셈을 할 때에는 각각의 다항식에서 현재 위치를 저장할 포인터 변수가 필요하다.

덧셈과정은 다음과 같다.

A와 B라는 다항식이 있다면 제일먼저 P와 Q라는 포인터 변수가 제일 첫번째 항을 가르키고 있게 만든다.

그리고 P위치의 exp값과 Q위치의 exp값, 즉 각 현재위치 항의 차수를 비교하여 연산을 다르게 해준다.

1. P->exp == Q->exp 일때 (같은 차수의 항일 때)

두 계수를 더해서 0이 아니면 더한값을 새로운 다항식인 C에 저장하고, 만약 0이 된다면 항이 사라지는 것이기 때문에

P와 Q포인터를 다음 포인터로 증가시켜준다.

2. P->exp < Q->exp 일 때, 현재 P와 Q위치에서 B항의 차수가 더 클 때

Q가 가리키고 있는 항을 C에 노드로 만들어 주고 연결한다. 이후에 Q만 다음 포인터로 이동시킨다.

3. P->exp > Q->exp 일 때, 현재 P와 Q위치에서 A항의 차수가 더 클 때 

P가 가리키고 있는 항을 C에 노드로 만들어 주고 연결한다. 이후에 P만 다음 포인터로 이동시킨다.

위와 같은 과정을 통해 프로그램을 실행시켜 확인해 보면 다음과 같은 결과를 제대로 얻어 낼 수 있었다.

전체 소스 및 보고서 다운받기

Linked List란 다음 그림과 같은 구조로 포인터를 이용하여 List를 만들어 내는 것이다.

즉 데이터와 link를 이용하여 하나의 배열 형태로 이루어 져 있지만 실제로는 List형태로 연결되어 있는 것이다.

List를 사용하면 Array를 이용할 때 정적인 방법으로 코드 작성시에 Array 사이즈를 지정해 주던것을 동적인 방법으로 만들어 줄 수 있고,

구조체의 내용에 따라 다양한 data를 이용하여 List를 만들어 낼 수 있다.

위의 구조대로 node를 만들어 낸다면 구조체의 선언을 위와 같이 해주면 되고, 만약에 int형 data말고도 추가적으로 더 넣고 싶은게 있다면

구조체에 넣어주기만 하면 된다. 그렇게 되면 node 타입의 노드들이 List형태로 연결되는 자료구조를 만들어 낼 수 있다.

삽입시에도 원하는 노드 다음노드에 포인터를 연결해 주면 되고, 삭제시에도 원하는 노드에 연결되어 있는 포인터를

그다음 노드로 연결시켜주면 된다.

그렇다면 기본적인 Linked List를 생성하는 코드를 보도록 하겠다.

코드는 파일로 저장되어있는 20개의 정수를 읽어와 Linked List로 연결하는 프로그램 이다.

List를 생성할 때에는 기본적으로 두가지 기능을 할 수 있는 함수를 만들어 주었는데

하나는 새로운 노드를 생성하는 함수, 그리고 하나는 생성된 노드를 원하는 List의 마지막 노드에 연결시키는 함수 이다.

동적할당인 malloc을 이용해서 node* type의 메모리를 allocation해주고, 초기 data는 0, next link는 Null로 초기화 시켜준다.

다음과 같은 두개의 함수를 이용해서 만들어 주었다.

main함수 내에서 node* 형식의 변수를 하나 만들어 주고 그 포인터변수에 makeLL() 함수를 붙여 주었다.

makeLL() 함수 내에서는 fscanf()를 통해 파일로 부터 정수를 읽어오고, 매번 newnode()와 LinkNode() 를 Call하는것을 볼 수 있다.

파일에서 읽어온 정수인 buf를 파라미터로 넘겨 새로운 노드를 생성하고, 생성된 노드를 header 포인터 정보와 함께 넘겨

제일 마지막에 연결시키는 구조이다.