Stack and Queue 구현 C++을 통해서 Stack과 Queue를 구현했다. 이전 실습과 마찬가지로 ItemType, Stack(Queue), Application을 세 파트로 나누어 코드를 구현했다. ItemType과 Application은 Unsorted list와 크게 다른 부분이 없기에 이는 이전 포스팅을 참고하면 좋을 것 같다. 2022.05.11 - [강의 내용 정리/자료구조] - 자료구조 구현 (1), Unsorted list 자료구조 구현 (1), Unsorted list Unsorted list 구현 C++을 통해서 Unsorted list를 구현했다. 특히 ItemType, Unsorted list, Application을 세 파트로 나누어 코드를 구현했다. Unsorted l..

Sorted list 구현 C++을 통해서 Sorted list를 구현했다. Unsorted list와 마찬가지로 ItemType, Sorted list, Application을 세 파트로 나누어 코드를 구현했다. ItemType과 Application은 Unsorted list와 크게 다른 부분이 없기에 이는 이전 포스팅을 참고하면 좋을 것 같다. 2022.05.11 - [강의 내용 정리/자료구조] - 자료구조 구현 (1), Unsorted list 자료구조 구현 (1), Unsorted list Unsorted list 구현 C++을 통해서 Unsorted list를 구현했다. 특히 ItemType, Unsorted list, Application을 세 파트로 나누어 코드를 구현했다. Unsorted..

Sorting and Searching Algorithm - 배열에 저장된 값에는 관계 연산자가 정의된 유형의 키가 있다. 이를 오버로딩해서 사용한다. - 오름차순 또는 내림차순으로 재배열을 한다. 1. Selection Sort(Straight) - 1 iteration에서 두 개의 키 값을 찾아서 뒤집는데 최대 1개만 바꾸게 된다. - 정렬되지 않은 요소 중 가장 작은 요소를 작은 요소를 찾아 바꾼다. 정렬이 되지 않았기에 순차탐색을 사용해 정렬되지 않은 값 중 가장 작은 값을 찾아서 이를 정렬되지 않은 인덱스 중 가장 작은 인덱스의 값과 바꿔준다. - 소트에서의 단위연산은 두 가지로 이뤄질 수 있다. 키 값의 비교가 몇 번 일어나는가. 이게 제일 중요해서 제일 많이 쓰이지만 스왑을 몇번 하는가?도 ..

Graph 1. 그래프 1) 그래프란? - 노드들의 연결관계를 표시하는 엣지의 집합으로 포함되는 자료구조이다. - 트리는 노드와 엣지의 연결관계가 있고, 한 노드에서 다른 노드로 갈 때의 경로가 유일해야한다. 그래프는 그보다 더 상위의 개념으로 연결관계만 있으면 된다. vertex는 노드와 같은 개념이다. - n은 대부분 입력되는 데이터의 개수를 의미한다. - 방향성을 가지냐는 것도 중요하다. 이를테면 a, b가 입력됐을 때 a에서 b로 갈 수 있는지, b에서 a로 갈 수 있는지, 양방향으로 모두 갈 수 있는지를 알아야지 그래프의 모양을 그릴 수 있다. undirect 그래프는 양방향이다. 일반적으로 undirect는 링크라는 표현을 direct는 엣지라는 표현을 많이 사용한다. - direct 그래프는..

Heap 1. Heap 1) Heap이란? - Heap은 Priority Queue와 밀접한 관계가 있다. Priority Queue 내부에 Heap을 사용하는 경우가 많다. 힙은 노드에는 우선순위에 관한 자료를 추가적으로 가지고 있다. - 힙은 이진트리이지만 BST는 아니다. BST는 크기의 대소 관계에 따라 데이터를 삽입한다. - 이진트리는 자식이 최대 두개까지 있는 것을 의미한다. 또한 가장 깊은 노드에 있는 것을 제외한 노드는 모두 2개의 자식이 있고, 가장 하단에 있는 노드는 좌하단부터 노드를 채워간다. 최대힙은 모든 노드는 자기의 자식보다 더 크거나 같은 트리를 가지게 된다. 따라서 루트에 있는 값만 확인하면 된다. - 왼쪽의 예시는 힙은 아니지만 오른쪽은 최대힙이다. 2) Heap의 특징 -..

Binary Search Tree 1. Tree 1) Graph와 Tree (1) Graph - 노드간의 연결관계가 표현된 것 - Tree는 여기에 해당된다. 따라서 트리는 그래프의 특성에 더하여 추가적인 특징을 가지고 있다. (2) Tree - 한 노드에서 시작해 다른 노드로 도달하는 모든 연결이 유일하게 있어야한다. (3) Binary tree - 이는 트리의 특성과 더하여 추가적인 특성이 존재한다. - 자식이 최대 2개까지 오는 트리 - 리프를 제외한 모든 노드가 풀로 가지고 있는 경우 complete binary tree라고 한다. 이때 2의 높이 승 -1개만큼 노드의 개수를 가진다. 2) Tree의 특징 (1) Level - Root node는 0 Level - 아래로 한 단계 내려갈수록 Lev..