justgo_developer

배열의 경우, 인덱스나 주소값을 통해서 한번에 해당값에 접근할수있다.대신에 길이가 가변적이지 못하다. 링크드리스트의 경우, 길이가 고정되지 않는 대신 원하는 값을 찾기 위해 각 노드를 일일이 순회해야 한다. 최악의 경우 O(n) 해시 테이블(hash table): 키 값의 연산에 의해 직접 접근이 가능한 구조: 데이터의 해시 값을 테이블 내의 주소로 이용하는 궁금의 탐색 알고리즘-> 탐색 성능이 향상됐지만 공간은 희생함 해싱(hashing): 해시테이블을 이용한 탐색: 자료를 검색할 때, 탐색이나 첨자가 아닌 내용에 의해 필요한 자료에 도달하는 기법 자료를 찾아주는 함수를 해싱함수라고 한다.서로 다른 자료가 해싱 함수에 의해 같은 값을 생성하는 경우 충돌(Collision)이라고 한다.탐색시간이 O(1)..

힙이란 최대값 및 최소값을 찾아내는 연산을 하기 위한 완전이진트리를 기본으로 한 자료구조- 완전이진트리- 부모노드의 키 값이 자식 노드의 키 값보다 크다(최대힙) or 작다(최소힙) 노드 삽입- 우선, 삽입하려는 노드를 완전이진트리의 맨 마지막 자리에 추가한 뒤,부모노드와 크기를 비교해가면서 대소관계아 따라 노드를 교환하여 힙으로 다시 만드는 과정을 거친다.노드 삭제- 힙에서 노드의 삭제는 루트노드를 삭제하면서 반환한다는 의미이다. 최대값이나 최소값을 찾아내는 연산을 하기 위한 트리이기 때문이다.노드에 노드가 하나도 남지 않을때까지 삭제연산을 반복해 반환된 노드들을 순서대로 늘어놓으면 오름차순 혹은 내리참순으로 정렬된 배열이 된다. 이를 힙정렬이라고한다. 루트노드와 맨마지막 노드의 자리를 바꾼다. 이렇게..

트리: 부모-자식 관계의 노드들로 이루어지며 계층적인 구조를 나타내는 자료구조부모는 여러 자식을 가질 수 있지만 자식은 하나의 부모를 갖는다.이진트리는 각 노드가 최대 2개의 자식을 가지는 트리위의 그림은 포화이진트리 구조이다. 모든 노드가 2개의 자식을 가지고 있다.트리의 최상단 노드를 루트(root)라고 한다.루트로부터 어떤 노드까지의 거리를 그 노드의 깊이(Depth)라 한다.깊이가 같은 노드끼리의 집합을 레벨(level)이라 한다.같은 부모를 가진 노드들을 형제(Sibling)노드라 한다. 트리의 표현배열표현법 : 각 노드에 인덱스를 부여하여 배열에 저장하는 방법링크표현법 : 다음 노드를 가리키는 포인터 변수를 이용하여 부모노드가 자식노드를 가리키는 방법트리의 순서가 배열의 인덱스가 되어 1번부터..

큐(Queue) 큐는 데이터의 제거는 가장 앞에서 수행되며, 데이터의 삽입은 가장 뒤에서 수행되는 제한된 리스트 구조가장 먼저 삽입된 데이터가 가장 먼저 제거되는 선입선출(FIFO- first in first out)형태의 자료구조이다. 가장 오래전에 입력된 데이터를 front라고 하며가장 최근에 입력된 데이터를 rear라고 한다. 삭제는 front에서 이루어지고삽입은 rear에서 이루어 진다. 삽입 - insert: 리스트 끝 부분을 가리키는 rear에서 발생하며데이터가 삽입 될때 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다.삭제(추출) - remove: front가 가리키고 있는 데이터를 꺼낸 후 front값을 하나 증가 시키도록 구현한다.front값이 rear를 추월하게 되면 더 이상 제거..

스택(Stack)-배열 이용: 가장 최근에 들어간 데이터가 먼저 나오는 구조후입선출(Last In First Out)이라고 한다. 배열은 사이즈가 정해져 있다.현재 데이터의 위치를 알기 위해 top이라는 변수를 사용(스택포인터) Push : 스택에 데이터를 넣는 작업Pop : 스택에 들어 있는 데이터를 빼내는 작업 실제로 배열을 이용한 스택 구조에서는 top의 위치를 변경함으로써데이터를 빼낸 것처럼 처리한다. Push: 스택에 데이터가 가득 찼는지 확인 후 가득차있지 않다면 데이터를 넣어주는 작업Pop : 스택에 데이터가 있는지 확인 후 데이터 배내는 작업 연결리스트를 이용한 스택: 연결리스트를 이용한 스택 구현은 스택의 크기가 정해져있지 않고 동적으로 늘어날 수 있다. 첫 노드를 head, 마지막 노드..