Developer Cafe

- 완전 이진 틀리에 있는 노드 중에서 키값이 가장 큰 노드 또는 키값이 가장 작은 노드를 찾기 위해 만든 자료구조다. - 최대 힙은 [부모노드의 키값 >= 자식노드의 키값]의 관계를 가지는 노드들의 완전 이진 트리다. - 최소 힙은 [부모노드의 키값

탐색을 위한 자료구조로 이진 트리를 사용하기 위해서 저장할 데이터의 크기에 따라 노드의 위치를 정의한 것이 이진 탐색 트리다. (1) 모든 원소는 서로 다른 유일한 키를 갖는다. (2) 왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다. (3) 오른쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 크다. (4) 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리다. Select 예시 (11찾기) Insert 예시 (4삽입) Delete 예시 (8삭제) 왼쪽 서브 트리에서는 가장 오른쪽 링크필드가 후계자가 되고, 우측 서브 트리에서는 가장 왼쪽 링크필드가 후계자가 된다.

이진 트리에 있는 모든 노드를 한번식 모두 방문하여 노드가 가지고 있는 데이터를 처리하는 순회 방법에는 전위 순회와 중위 순회, 후위 순회의 세가지가 있다. 전위순회 (1) 현재 노드 N을 방문한다. : D (2) 현재 노드 N의 왼쪽 서브 트리로 이동한다. : L (3) 현재 노드 N의 오른쪽 서브 트리로 이동한다. : R 중위순회 (1) 현재 노드 N의 왼쪽 서브 트리로 이동한다. : L (2) 현재 노드 N을 방문한다. : D (3) 현재 노드 N의 오른쪽 서브 트리로 이동한다. : R 후위순회 (1) 현재 노드 N의 왼쪽 서브 트리로 이동한다. : L (2) 현재 노드 N의 오른쪽 서브 트리로 이동한다. : R (3) 현재 노드 N을 방문한다. : D

트리는 비선형 자료구조 중에서 자료들 간에 계층관계를 가진 계층형 자료구조이다. 이진트리 모든 노드의 차수를 2 이하로 정하여 전체 트리의 차수가 2 이하가 되도록 만든 이진 트리는 왼쪽 서브 트리와 오른쪽 서브 트리를 가지는데, 서브 트리 역시 이진 트리가 된다. n개의 노드로 구성된 이진 트리는 (n-1)개의 간선을 가지며, 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개며, 노드의 최대 개수는 (2^h+1 - 1)개가 되는 성질을 가진다. 이진 트리를 순차 자료구조 방식을 이용하여 표현하는 방법은 높이가 h인 포화이진트리의 노드 번호를 배열의 인덱스로 사용하여 1창원 배열로 표현하는 것이다. 1차원 배열에서 인덱스 계산을 간단히 하기 위해서 인덱스 0번은 실제로 사용하지 않고 비..

큐는 극장에 줄을 서는 사람들처럼 삽입된 순서대로 삭제되는 선입설출(FIFO, First In First Out)의 구조로 운영된다. 큐는 한쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행하도록 하고, 다른 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행하도록 제한한다. 스택 vs 큐 차이 삽입 연산 삭제 연산 연산자 삽입 위치 연산자 삭제 위치 스택 push top pop top 큐 enQueue rear deQueue front 큐를 프로그램으로 구현하는 방법은 배열을 사용하는 순차 자료구조방식과 참조변수를 사용하는 연결자료구조가 있다. 선형 큐 배열의 크기는 큐의 크기, 즉 큐에 저장할 수 있는 최대 원소의 개수가 된다. 초기 공백 큐의 상태는 front변수와 rear 변수 값이 -1 이..

스택은 접시처럼 시간순서에 따라 자료가 쌓이고, 삭제할 때는 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO, Last In First Out)의 구조를 갖는다. (삽입은 푸시, 삭제는 팝 이라 부른다.) 스택 구현 방법 1. 순차 자료구조방식을 이용한 스택의 구현 2. 연결 자료구조방식을 이요한 스택의 구현 순차 자료구조를 이용한 스택은 배열을 사용하여 구현하기는 쉽지만, 물리적으로 크기가 고정된 배열을 사용하기 때문에 스택의 크기를 변경하기가 어렵고, 메모리의 낭비가 생기는데 이는 연결 자료구조 방식을 이용해 해결가능하다. 프로그램 간의 호출과 복귀에 따른 수행 순서는 가장 나중에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 LIFO 구조가 된다. 이를 응용하여 시스템 스택을 ..

다항식 노드는 계수를 저장하는 coef와 지수를 저장하는 expo의 두 필드와 링크필드로 구성된다. coef expo link A(x) = 4x^3 + 3x^2 + 5x B(x) = 3x^4 + x^3 + 2x + 1 위의 두 식을 다항식 노드를 사용해서 표현하면 coef expo link coef expo link coef expo link 4 3 . 3 2 . 5 1 null coef expo link coef expo link coef expo link coef expo link 3 4 . 1 3 . 2 1 . 1 0 null

순차 선형 리스트는 논리적인 순서와 물리적이 순서가 같기 때문에 원소의 위치를 찾아 액세스하기 쉬우나, 삽인 삭제 후 원소들의 위치이동에서 많은 추가작업과 시간이 필요하다. 이러한 문제를 개선한 자료 표현 방식으로 연결자료구조(비순차 자료구조)가 있다. 연결자료구조는 노드를 사용하는데 노드는 데이터필드와 링크필드로 구성되어있다. data(원소) link(주소) 단순 연결 리스트 - 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진 연결리스트 ex) 다음 연결리스트 월, 금 사이에 150[수][null]를 연결하려면 100 -> 100[월][200] -> 200[금][300] -> 300[일][null] 100 -> 100[월][150] -> 150[수][200] -> 200[금][300..

○ 행의 개수가 m, 열의 개수가 n 일때 mn이 같은 행렬은 정방행렬이다. ○ 행렬의 행과 열을 서로 교환해 구성한 행렬을 전치행렬이라 한다. 1 2 3 4 5 6 1 4 2 5 3 6 ○ 실제 사용하는 공간보다 사용하지 않는 공간이 많아 기억공간에 대한 사용 효율성이 떨어지는걸 희소행렬 이라한다. 0 2 0 0 0 4 0 9 5 0 0 0 7 0 8 0 이는 배열로 0이 아닌 원소들에 대해 으로 추출가능하다.

만약 A(x) = 4x^3 + 3x^2 + 2 일때 아래와 같이 표현된다. 0 1 2 3 A 4 3 0 2 만약 A(x) = 3x^1000 + 1x^1 + 4 일때는 아래와 같이 표현된다. 0 1 2 3 4 ... 998 999 1000 A 3 0 0 0 0 ... 0 1 4 실제 사용하는 것은 3개뿐이고 998개의 배열 공간은 낭비된다. 그래서 아래와 같이 2차원 배열에 저장한다. [0] [1] [0] 1000 3 [1] 1 1 [2] 0 4 Ex) A(X) + B(X)을 구하는 식을 자바 코드로 나타내면 A(X) = 4x^3 + 3x^2 + 5x B(X) = 3x^4 + x^3 + 2x + 1 public class Ex { public static void main(String args[]) { f..