그래프(Graph)란? 그래프는 객체 사이의 연결 관계를 표현하는 자료구조이다. 지금까지 설명한 자료구조 중에서 가장 현실 세계의 다양한 문제들을 효과적으로 모델링 할 수 있을 정도로 표현 능력이 매우 우수하다. 다음 그림은 우리나라의 고속도로 지도이다. 각 도시를 연결하는 고속도로를 자료구조로 나타낼 수 있을까? 앞서 소개한 자료구조 중에서 선형 자료인 리스트,스택,큐 같은 경우는 객체들의 선,후 관계 밖에 나타내지 못하기 때문에 1:1인 관계가 아닌 것이 존재하는 고속도로를 표현하기에는 적합하지 못하다. 하나의 객체가 여러개의 객체와의 관계를 나타낼 수 있는 자료구조인 트리는 부모 자식 간의 관계만 나타낼 수 있고 일반적인 관계는 나타내지 못한다는 한계가 있다. 각 도시를 연결하는 고속도로 같은 경우..

dsbook.tistory.com/270 C로 만드는 자료구조 - 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리 (Binary Search Tree)란? 이진 탐색 트리는 이진 트리에서 탐색(Search)란 단어가 들어가 있다. 탐색이 뜻하는 바와 같이 이진 트리에서 '자료의 검색'이 주된 기능이 된다. 이진 탐색 트 dsbook.tistory.com 연결 리스트를 이용한 이진 탐색 트리 구현 소스 파일 구성은 다음과 같다. 파일 이름 내용 binsearchtree.h 구조체 및 함수 선언 binsearchtree.cpp 함수 구현 binsearchtreemain.cpp main 함수 실행 1.binsearchtree.h 구현하기 앞서 힙의 추상자료형을 다시 한번 보자 이름 입력 출..

이진 탐색 트리 (Binary Search Tree)란? 이진 탐색 트리는 이진 트리에서 탐색(Search)란 단어가 들어가 있다. 탐색이 뜻하는 바와 같이 이진 트리에서 '자료의 검색'이 주된 기능이 된다. 이진 탐색 트리는 효율적인 자료 검색을 목적으로 기존 이진 트리에 몇 가지 제약 사항을 추가한 트리이다. 위 설명만 보면 앞서 설명 했던 힙(Heap)과 비슷하다. 힙 또한 이진 트리에서 최댓값 또는 최솟값을 빠르게 반환하도록 이진트리에서 몇가지 제약 사항을 추가했기 때문이다. 이진 탐색 트리는 힙과는 다르게 특정 값에 해당하는 노드를 빠르고 효율적으로 찾는 것을 목적으로 한다. 이진 탐색 트리는 다음 특성을 만족해야 한다. 1. 트리의 모든 노드는 유일한 값을 가진다. 2. 왼쪽 서브트리에 있는 ..

이글은 이전글과 이어집니다. dsbook.tistory.com/255 C로 만드는 자료구조- 힙(Heap)이란? 힙 (Heap)이란? 힙은 이진 트리의 하나이다. 힙의 특징은 루트 노드가 언제나 그 트리의 최댓값 또는 최솟값을 가지는 것이다. 힙의 루트 노드가 최댓값을 가지면 최대 힙, 최솟값을 가지면 최소 dsbook.tistory.com 위 글에서는 힙이란 무엇인지, 힙의 추상 자료형과 그 중 핵심인 삽입과 삭제 연산에 대해 다루었다. 이제는 실제로 코드 구현은 해볼려고 한다. 이글에서는 배열을 이용해 구현하려고 한다. 배열을 이용한 이진 트리 이진 트리는 자식 노드가 최대 2개 이기 때문에 규칙을 만들어 배열의 인덱스를 이용하여 부모,자식 노드간의 관계를 나타낼 수 있다. 규칙은 다음과 같다.( 편..

힙 (Heap)이란? 힙은 이진 트리의 하나이다. 힙의 특징은 루트 노드가 언제나 그 트리의 최댓값 또는 최솟값을 가지는 것이다. 힙의 루트 노드가 최댓값을 가지면 최대 힙, 최솟값을 가지면 최소 힙이라고 한다. 최대 힙은 모든 부모 노드가 자식 노드보다 큰 값을 가지느 최대 트리의 특성을 가지고 있고 최소 힙은 모든 부모 노드가 자식 노드 보다 작은 값을 가지는 최소 트리의 특징을 가지고 있다. 마지막으로 힙은 항상 완전 이진 트리이다. 힙이 되기 위한 조건을 정리하면 아래와 같다. 1. 완전 이진 트리여야 한다. 2. 최대 트리 혹은 최소 트리의 특징을 가진다. 아래는 최대 힙과 최소 힙의 예시이다. 두 개의 이진 트리 모두 완전 이진 트리이며 최대 힙은 모든 부모 노드가 자식 노드의 값보다 크기 때..

이전글에서 이진 트리의 순환을 다루었다. dsbook.tistory.com/245(이전 글) C로 만드는 자료구조- 이진 트리의 순회 트리의 순회란? 트리의 순회란 트리의 모든 모드를 한 번씩 방문 하는 것을 의미한다. 트리를 사용하면서 트리의 내용을 출력하거나 트리에서 원하는 노드를 찾고자 한다면 트리의 노드를 한 dsbook.tistory.com 이번 글에서는 이진 트리의 함수들을 다루고자 한다. 1) 복사 2) 동일성 검사 3) 노드 개수 구하기 4) 단말 노드 구하기 5) 이진 트리의 높이 구하기 위 함수들은 이진 트리의 구조와 순환 알고리즘들을 정확하게 이해하고 있다면 별다른 어려움 없이 구현이 가능하다. 이때 중요한점은 각 전위 순환, 중위 순환 ,후위 순환 알고리즘 중에서 함수에 적합한 순환..

트리의 순회란? 트리의 순회란 트리의 모든 모드를 한 번씩 방문 하는 것을 의미한다. 트리를 사용하면서 트리의 내용을 출력하거나 트리에서 원하는 노드를 찾고자 한다면 트리의 노드를 한 번씩 방문해야 한다. 근데 트리는 리스트,스택,큐와 같은 선형 자료구조가 아니라 계층 구조이기 때문에 순회 알고리즘을 잘 이해해야 하고 알고리즘에 방향성에 따라 다양한 순회 방법이 가능하다. 트리의 다양한 함수,알고리즘들은 기본으로 순회를 기반으로 하기 때문에 순회 알고리즘을 이해하고 사용용도에 따른 순회 알고리즘을 선택하는 것이 중요하다. 이진 트리의 순회 이 글에서 다루는 것은 이진 트리의 순회를 다룰 것이다. 이진 트리는 최대 차수가 2이기 때문에 구성요소를 크게 3가지로 (L: 왼쪽 서브트리 R: 오른쪽 서브트리 V..

지난 포스팅에서는 클라우드 컴퓨팅이 무엇인지와 특징에 대해서 다루어 보았다. 이번에는 클라우드 컴퓨팅이 사람들에게 제공하는 서비스의 종류와, 어느 상황에서 클라우드 컴퓨팅을 사용하게 되는지에 대해서 알아보자. 클라우드 컴퓨팅의 서비스 종류 - IaaS : Infrastructure as a Service의 줄임말이다. 여기에서 Infrastructure(인프라)의 의미는 CPU, 메모리 등의 리소스 자체와 응용체제와 같은 기본적인 프로그램만 설치된 상태로 사용자에게 제공하는 것을 말한다. 즉, 클라우드 서비스를 제공하는 업체에서는 해당 리소스만 제공하고, 나머지는 사용자가 알아서 사용해야 하는 것이다. 사용자가 직접 자신이 원하는 환경을 설정해야해서 번거롭다는 단점이 있지만, 그만큼 자신의 환경에 최적화..

이진트리 (Binary Tree)란? 이진트리는 모든 노드의 차수가 2 이하인 트리를 말한다. 다시 말해 하나의 노드가 가질 수 있는 자식 노드는 최대 2개라는 뜻이다. 이진트리의 종류 이진트리는 형태에 따라 3가지로 분류할 수 있다. 1) 포화 이진 트리(Full Binary Tree) 포화 이진 트리는 모든 레벨의 노드가 가득 차 있는 이진트리를 말한다. 한 노드가 자식 노드를 가지게 된다면 무조건 자식 노드가 2개라는 뜻이다. 이러한 특징 덕분에 포화 이진트리에서 모든 노드의 개수는 다음과 같다. 아래 그림은 포화 이진 트리의 예시이다. 2) 완전 이진트리(Complete Binary Tree) 완전 이진 트리는 높이가 h인 이진트리 일 때 h-1단계까지는 포화 이진트리와 동일하지만 h단계에서 노드..

컴퓨터에 관심이 있는 사람이라면, 이 용어들을 많이 들어보고, 어렴풋이 의미를 짐작할 수도 있다. 사람들이 이 개념들을 어디에 왜 사용하는지 알기 위해서는 우선, 이 용어들을 탄생시킨 배경부터 알아야 한다. 이해하기 쉽게 얘기하자면, 스마트폰의 탄생과 네트워크의 발전으로, 여러 네트워크와 하드웨어(기기)들이 일상속으로 들어왔다. 또한, 이런것들로 인해서 여러 서비스업들이 인터넷 상에서 웹을 기반으로 서비스를 제공하기 시작했다. 기존에는 큰 회사에서는 여러 사람이 많이 쓸 수 있는 서비스를 개발하고, 중소기업에서는 회사 장비의 규모에 맞게 서비스를 제공할 수 밖에 없었다. 하지만, 당연히 큰 회사에서 진행하는 여러 사업들이 100% 성공할수는 없었다. 이렇게 되니, 많고 다양한 하드웨어 자원(CPU, 메모..