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 구조가 된다. 이를 응용하여 시스템 스택을 ..

1959년 에드거 데이크스트라가 최단 경로 문제를 푸는 굉장히 흥미로운 알고리즘을 만들었다. 1. 시작 정점을 현재 정점으로 한다. 2. 현재 정점에 인접한 모든 정점을 확인해서 시작 정점으로부터 알려진 모든 위치까지의 가중치를 계산하고 기록한다. 3. 다음 현재 정점을 결정하려면 시작 정점으로부터 도달할 수 있는 방문하지 않은 가장 저렴한 알려진 정점을 찾는다. 4. 그래프 내 모든 정점을 방문할 때까지 1~3단계를 반복한다. 0에 갈 수 있는 정점은 4, 1, 5 이다. 이들의 최단 거리를 저장한다. 이어 가장 가까운 최단거리인 4를 다음 정점으로 한다. 4에서 갈 수 있는 6, 1, 3의 최단 거리를 0에서 시작하는 거리값으로 저장한다. 예를 들어 6인 경우는 3+5이니 8이다. 그러므로 8을 저장..

그래프는 데이터가 어떻게 연결되는지 쉽게 이해시키므로 관계에 특화된 자료구조다. 원 하나를 노드로 그 노드는 정점이라 부르고, 정점간 관계인 선은 간선이라 부른다. 또한 그래프는 트위터 팔로우 기능처럼 화살표로 표현된 것을 방향 그래프, 페이스북처럼 상호작용하는 그래프는 무방향 그래프라한다. 위 그림에서 앨리스는 밥과 직접 커넥션이 있으나 신시아와 직접 커넥션이 없다. 비직접적인 커넥션을 포함해 앨리스 전체 네트워크를 찾으려면 두가지 방법이 있다. 1. 너비 우선 탐색 2. 깊이 우선 탐색 여기선 너비 우선 탐색만 포스팅하고 깊이 우선 탐색은 차후 업데이트하거나 따로 비교포스팅하겠다. 너비 우선 탐색 1. 현재 정점과 인접한 각 정점을 방문한다. 이전에 방문한 적 없는 정점이면 방문했다 표시하고 큐에 추..

트리 - 트리에는 가장 상위 노드를 루트라 부른다. 여기선 2가 루트다 - 90은 50, 150의 부모고 반대로 50, 150은 90의 자식이다. - 트리는 레벨이 있다. 여기선 4 레벨이다 (맨위가 1 레벨) 이진 트리(+트리 특징) - 각 노드의 작식은 0개나 1개, 2개다. - 한 노드에 자식이 둘이면 한자식은 부모보다 작은 값을, 다른 자식은 부모보다 큰 값을 가져야한다. 검색 - 111을 찾는다고 가정하고 두 자식중 부모가 111보다 큰지 작은지 비교 후 조건에 맞는 자식에게 타고 들어가면서 찾고자하는 값을 찾는다. (여기선 111이 부모 90보다 크다 고로 우측 150으로 타고옴) - 이진 트리 검색은 O(log N) 단계이다. 삽입 - 100을 삽입한다고 가정하면 먼저 루트90부터 큰지 작은..

노드 연결 리스트는 서로 인접 하지 않은 메모리 셀 묶음으로 이뤄진다.. 컴퓨터 메모리 전체에 걸쳐 여러 셀에 퍼져 있을 수 있다. 서로 인접하지 않은 이러한 셀을 노드라 부른다. "a" 1652 "b" 1983 "c" null 1000 1001 1652 1653 1983 1984 배열 vs 연결 리스트 차이 - 연결 리스트를 다루는 코드는 항상 첫 번째 노드가 메모리 어디에서 시작하는지 알고 두번째 세번째 링크를 따라 나머지 리스트를 검색할 수 있다. - 연결 리스트가 배열보다 나은 점 중 하나는 프로그램이 데이터를 저장하기 위해 메모리 내에 나란히 이어진 빈 셀 묶음을 찾을 필요가 없다는 점이다. 연산 배열 연결 리스트 읽기 O(1) O(N) 검색 O(N) O(N) 삽입 O(N)(끝에서 하면 O(1)..