목록자료구조&알고리즘 (6)

카메라 개발자 공부방(SW)

레드블랙트리

////binary tree ////자료가 동적인 상태에서도 이진 탐색이 가능한 자료구조 ////이진 탐색은 메모리 중심 대해서도 직접 접근이 가능, 미리 주어지고 정렬된 데이터 셋에만 적용이 가능하다. //// ////# 규칙 ////현재 노드를 기준으로 왼쪽이 작은 값, 오른쪽이 큰 값인 규칙을 지닌다. //// ////# 용어 ////leaf(잎) 노드 자식이 없는 노드 ////root 최상단 노드 ////root에서 잎노드 까지의 깊이: height //// ////완전포화이진트리 ////: 잎 노드를 제외하고 완전하게 모든 노드가 자식이 있는 트리 ////포화이진트리 ////: 좌측 노드 까진 자식을 가지지만, 그 다음 부턴 자식이 없는 트리 ////불포화이진트리 ////: 포화이진트리가 아닌 ..
자료구조&알고리즘 2022. 1. 9. 20:34
이진 탐색 트리(Binary Search Tree)

오늘은 이진 트리에 대해서 작성해보겠습니다. 이진 트리는 일정한 규칙을 유지한 체 트리의 형태를 갖는 자료구조입니다. 현재 노드를 기준으로 왼쪽은 작은 값 오른쪽엔 큰 값이 배치되는데요! 미리 정렬 되어 있고 메모리 중앙에도 단번에 접근 가능해야 사용할 수 있는 이진 탐색과 달리 메모리가 동적으로 변해도 탐색이 가능한 자료구조입니다. 먼저 트리의 용어에 대해 볼까요? 노드의 크기: 자신을 포함한 노드가 갖는 자식의 수를 의미합니다. 노드의 차수(degree): 하위 (자식의 수)간선의 수를 의미합니다. 깊이: 루트 노드에서 해당 노드까지 거쳐야되는 간선의 수를 의미합니다. 레벨: 특정 깊이의 노드들의 집합을 의미합니다. 트리의 차수: 노드가 갖는 최대 간선의 수를 의미합니다. 트리의 높이: 루트 노드에서..
자료구조&알고리즘 2021. 12. 26. 23:05
무게 선별작업 자동화 프로그램

최근에 농사일을 하시는 분에게서 알고리즘 제작 의뢰를 요청받았습니다. 의뢰자분은 과일 농장을 운영하고 계셨고, 매 포장 때마다 수작업으로 과일의 무게를 재고 중량을 맞추는 선별 과정 때문에 어려움을 겪고 계셨는데요. 중량에 맞는 조합들의 과일만 자동으로 찾아주기만 해도 업무 개선에 큰 도움이 될 것입니다! 오늘 작성해볼 코드는 무게 선별작업 자동화 프로그램입니다. 참고할 만한 사이트 https://youtu.be/VbV5f23xmhM 자동 선별 기계는 과일의 무게를 재는 센서들이 (1 - 10) 번까지 있고, 작동 전 어떻게 동작할지에 대한 옵션을 선택할 수 있습니다. 1) 옵션에 따라 조합의 수를 조정할 수 있는 스위치 변수가 있습니다. 1번 스위치: 가능한 조합의 수 2개 2번 스위치: 가능한 조합의..
자료구조&알고리즘 2021. 12. 10. 17:50
큐(queue)

이번엔 queue에 대해 이야기해보겠습니다. queue는 먼저 들어온 데이터가 먼저 나가는 First In First Out 구조입니다. Stack과 마찬가지로 STL에선 deque로 대신할 수 있기 때문에 라이브러리 형태로 제공되진 않습니다. 대표적인 함수의 인터페이스는 아래와 같습니다. push: 데이터를 입력하면 맨앞단에 추가됩니다. pop: 맨앞단의 데이터를 삭제합니다. front: 맨앞의 데이터를 반환합니다. empty: 메모리가 비어있는지 확인하여 true or false를 반환합니다. full: 메모리에 데이터가 가득 차 있는지 확인하여 true or false를 반환합니다 queue의 경운 내부적으로 1차원 배열을 사용하지만 논리적으로 배열을 순환하게있게 작성을 해 circular queu..
자료구조&알고리즘 2021. 11. 28. 21:39
스택(Stack)

오늘은 stack에 대해 공부해보겠습니다. stack은 나중에 들어온 데이터가 먼저 나오는 Last In First Out 구조입니다. STL에선 deque로 stack을 대신할 수 있기 때문에 따로 stack이란 라이브러리를 제공하진 않습니다. Stack의 대표적인 함수 interface는 다음과 같습니다. push: 입력된 데이터가 맨 뒤에 추가로 입력이 됩니다. pop: 맨뒤의 데어터가 삭제됩니다. top: 맨 나중에 입력된 데이터를 반환합니다. empty: 데이터가 비워졌는지를 확인하여 true or false를 반환합니다. full: 데이터가 메모리에 가득 찾는지를 확인하여 true or false를 반환합니다. 다음은 코드를 작성해보겠습니다 #include using namespace std;..
자료구조&알고리즘 2021. 11. 28. 16:50
덱(Deque)

오늘은 deque에 대해 공부해보겠습니다. deque는 stack과 queue를 합쳐 놓은 자료구조입니다. 메모리 공간을 push/pop_front 함수를 이용해 First In First Out(FIFO) 형태로 사용할 수 있고, push/pop_back 함수를 통해 Last In First Out(LIFO) 형태로도 활용 될 수 있습니다. STL을 활용한 deque의 선언법과 정의되어있는 멤버함수는 다음과 같습니다. push_front: 데이터의 맨 앞쪽에 새로운 데이터를 넣습니다. push_back: 데이터의 뒷쪽에 새로운 데이터를 넣습니다. pop_front: 맨앞쪽의 데이터 하나를 제거합니다. pop_back: 맨뒷쪽의 데이터 하나를 제거합니다. empty: 메모리에 데이터가 비어있는지 확인하여..
자료구조&알고리즘 2021. 11. 27. 21:44
이전 Prev 1 Next 다음