자료구조 (10) 썸네일형 리스트형 자바 자료구조 보호되어 있는 글입니다. 트리의 종류 트리란 무엇인가? 배열, 리스트, 스택, 큐와 같은 선형구조가 아닌 부모 자식의 관계를 갖는 계층형 그래프 1. Binary Tree(이진 트리) 노드가 하나 이상의 자식을 갖게 되면 트리라고 부르는데 자식 노드가 최대 2개까지만 허용하는 트리를 이진트리라고 부릅니다. 2. Ternary Tree 노드가 2개 이상 붙는 트리도 당연히 존재하게 되는데 3개가 붙으면 ternary tree라고 부릅니다. 3. Binary Search Tree(이진 탐색 트리) 다른 특별한 조건 없이 노드의 자식이 최대 2개씩만 붙으면 이진 트리라고 부르게 되는데, 이진 탐색 트리는 왼쪽 노드와 그 이하의 자식 노드들은 현재의 노드보다 작아야 하며 오른쪽 노드와 그 이하의 자식들은 현재의 노드 보다 큰 조건을 만족하게 된다... Hash Tale! 해시 테이블(hash table), 해시 맵(hash map), 해시 표는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 해시 함수 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 이름을 0~15 사이의 정수값으로 매핑하는 해시 함수의 예. “John Smith”와 “Sandra Dee”라는 두 키 사이에 충돌이 존재한다. 해시 함수(hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. 그 .. 연결리스트로 구현한 스택(Stack), 큐(Queue) 지금까지 스택과 큐를 구현할 때 배열을 이용하여 구현하였다. 배열을 이용하여 구현하게 되면 간단하다는 장점은 있지만 용량이 고정된다는 단점도 존재한다. 배열은 동적으로 크기를 늘리거나 줄일 수 없기 때문에 처음 할당한 공간이 가득 차면 더 이상 데이터를 더 추가할 수 없기 때문이다. 용량이 자동으로 변할 수 있는 보다 자유로운 방법을 구현하기 위해 연결된 표현(linked representation)을 사용한다. 연결된 표현은 데이터와 링크로 구성되고 링크가 노드들을 연결하는 역할을 하게 된다. 용량이 고정되지 않는 장점 덕분에 스태이나 큐 뿐만 아니라 리스트나, 덱, 트리, 그래프 등 여러가지 자료구조를 구현하는데 널리 사용 된다. 연결된 표현(linked representation)의 특징 1. 데이.. 전역 변수와 객체지향 프로그래밍 지금 까지 스택과 큐를 구현하면서 많은 전역 변수를 사용했다.사실 프로그램에서 전역변수를 무절제하게 사용하는 것은 매우 좋지 않은 프로그래밍 습관이다.전역변수는 함수들 사이에 관련성을 만들어 모듈화 된 프로그래밍을 방해할 수 있다. 즉, 어떤 함수가 오류 없이 동작하는가를 그 함수의 코드만으로 검증할 수 있어야 하는데, 전역변수를 사용하면 그 함수의 코드만 봐서는 오류의 유무를 판단할 수 없고 관련된 다른 함수들을 모두 확인해야 한다.또 하나의 중요한 문제는 전역변수는 하나이기 때문에 스택이나 큐를 하나만 만들 수 있다는 것이다. 만약 스택이나 큐를 두 개 이상 사용하고 싶다면 지금까지의 코드들은 문제가 잇다.자료구조의 핵심 기능에 집중하기 위해 전역변수를 사용했다. 전역변수와 관련된 함수들은 C++이나.. 덱(Deque)응용 미로 탐색 프로그램 미로에서 출구를 찾기 위한 다양한 탐색 방법을 사용할 수 있다. 이것은 그래프 탐색 문제와 유사하며 다양한 방법들이 있다. 가장 간단한 탐색 방법은 시행착오를 이용하는 것으로 하나의 경로를 선택하여 시도해 보고 막히면 다시 다른 경로를 시도하는 것이다. 이때 현재의 경로가 막혔을 때 다시 선택할 수 있는 다른 경로들을 어딘가에 저장해야 한다. 저장된 경로를 모두 선택할 수 있는 방법이라면 경로를 어디에 저장하든지 출구를 찾을 수 있다. 전통적으로 그래프 탐색에서는 대표적인 두 가지 방법을 제공한다. 깊이 우선 탐색(DFS, Depth First Search) 전략: 가장 최근에 저장한 경로를 순서대로 선택하여 시도하는 방법. 스택을 이용해서 구현 너비 우선 탐색(BFS, Breadth First Sear.. 큐(Queue)응용 은행 시뮬레이션 은행 시뮬레이션 프로그램 대기행렬은 큐로 구현하고, 큐에 들어있는 고객들은 순서대로 서비스를 받는다. 한 고객의 서비스가 끝나면 다음(가장 먼저 들어온) 고객이 서비스를 받는다. 단순화를 위해 은행 창구는 하나라고 가정한다. 시뮬레이션에서는 난수 발생이 많이 사용된다. 고객들이 은행에 오는 것이 일정하지 않고 서비스에 필요한 시간도 각기 다를 것이기 때문이다. 시뮬레이션에서는 이러한 이벤트 발생을 조절하기 위해 다양한 값(파라미터)들이 사용된다. 여기서는 다음 세 값을 사용자가 입력하도록 한다. 1. 시뮬레이션 할 최대 시간(예: 10 [단위시간]) 2. 단위시간에 도착하는 고객 수 (예: 0.5 [고객수/단위시간]) 3. 한 고객에 대한 최대 서비스 시간 (예: 5 [단위시간/고객]) 고객들은 단위시간.. 스택(Stack) - 괄호 괄호의 알맞은 짝을 찾을 때 스택을 이용하면 편리하다. (), [], {} 같은 유형의 괄호들이 사용 되어야 하고 쌍을 이루어야 한다. 다음 3가지 조건을 맞추어 구성되어야 한다. 조건 1 : 왼쪽 괄호의 개수와 오른쪽 괄호의 개수는 같아야 한다. 조건 2 : 같은 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 조건 3 : 서로 다른 타입의 괄호 쌍이 서로를 교차하면 안된다. 괄호 검사 프로그램 구현 #include #include #include #define MAX_STACK_SIZE 100 typedef int Element; Element data[MAX_STACK_SIZE]; int top; void error(char str[]) { printf("%s\n", str); ex.. 이전 1 2 다음
