프로그래밍 기초/자료구조
-
인접 리스트를 통한 그래프 구현프로그래밍 기초/자료구조 2021. 5. 3. 09:37
인접 리스트 통한 그래프 구현 그래프 구현/인접 리스트 인접 리스트는 각각의 노드를 하나의 포인터로 하여 특정 노드에서 이동 가능한 노드를 표현하는 방법으로 다음과 같이 표현된다. 구현이 필요한 메서드 및 속성은 다음과 같다. 생성자 ArrayListGraph() 비어있는는 인스턴스 생성 속성 NodeCount 현재 노드의 개수 메서드 InsertNode() 노드 추가 InsertEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 에지 추가 RemoveNode(int) 지정된 인덱스의 노드 제거 RemoveEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 제거 Clear() 저장되어 있는 모든 데이터 삭제 GetDegreeIn(int) 노드의 진입 차수 반환 GetDegreeOut(i..
-
인접 행렬을 통한 그래프 구현프로그래밍 기초/자료구조 2021. 4. 22. 20:21
인접 행렬을 통한 그래프 구현 인접 행렬로 그래프를 표현하는 것은 다음과 같이 각각의 노드가 순서대로 존재하는 것으로 가정하여 표현하는 것이다. 구현이 필요한 메서드 및 속성은 다음과 같다. 생성자 ArrayGraph() 비어있고 기본 초기 용량을 가지는 인스턴스 생성 ArrayGraph(int) 비어있고 지정한 초기 용량을 가지는 인스턴스 생성 속성 NodeCapacity 노드의 최대 개수 NodeCount 현재 노드의 개수 메서드 InsertNode() 가능할 경우 노드 추가 InsertEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 에지 추가 RemoveNode(int) 지정된 인덱스의 노드 제거 후 모든 데이터 위치 조정 RemoveEdge(int, int) 앞의 노드에서 뒷 노드로 ..
-
그래프(Graph)프로그래밍 기초/자료구조 2021. 4. 8. 11:15
그래프 그래프는 연결되어 있는 원소 간의 관계를 표현하는 자료구조이다. 그래프의 구성요소 노드(또는 정점) 데이터 저장 및 표현 간선 데이터 간의 관계 표현 그래프의 종류 그래프는 방향성과 연결 정도에 따라 구분하며 추가로 간선에 가중치를 할당한 그래프가 존재한다. 무방향 그래프(Undirected Graph) 두 노드를 연결하는 간선의 방향이 없는 그래프 방향 그래프(Directed Graph) 노드를 연결할 때 간선에 방향이 있는 그래프 완전 그래프(Complete Graph) 정점이 모두 서로 연결된 그래프 부분 그래프(Subgraph) 완전 그래프에서 특정 간선이 제외된 그래프 가중 그래프(Weigh Graph) 간선마다 가중치가 할당된 그래프 그래프의 표현) 그래프는 방향성에 따라 다르게 표현된..
-
트리(Tree)와 이진 탐색 트리(Binary Search Tree)프로그래밍 기초/자료구조 2021. 3. 29. 19:33
트리 각각의 자료가 노드를 이루고 각 노드가 부모-자식 관계를 형성하는 자료구조를 말한다. 트리의 구성 요소 트리는 하나의 루트와 여러 개의 자식 노드로 구성된다. 노드 트리를 이루는 각각의 요소 루트 트리의 최상단 요소 리프 트리의 최말단 요소 차수 각 노드가 가진 자식의 수 트리의 차수 해당 트리에 존재하는 각 노드의 차수 중 가장 큰 값 높이 트리의 노드의 레벨 중 가장 큰 값 이진트리 리프 노드를 제외한 노드의 자식이 1개 혹은 2개로 이루어진 트리로 각 서브 트리는 다음과 같은 구조로 이루어진다. ※ 각 자식 노드를 왼쪽 자식 노드와 오른쪽 자식 노드로 구분하며 각각의 자식 노드가 자식 노드를 가진 경우 자식 노드를 루트로 하는 노드 집단을 서브 트리라고 한다. 이진 트리의 특징 n개의 노드를 ..
-
원형 큐(Circular Queue)프로그래밍 기초/자료구조 2021. 1. 8. 11:56
스택 순차 자료구조를 사용한 큐는 데이터를 인출할 때마다 모든 데이터를 이동시켜야 하는 오버헤드가 발생한다. 이를 방지하기 위한 자료구조가 원형 큐이다. 원형 큐는 기본적으로 시작 지점과 끝 지점을 연결해 계속해서 이어질 수 있도록 만든 것으로 논리적 구조는 다음과 같다. 이때 데이터를 삽입하는 위치와 인출하는 위치는 다음과 같다. 삽인 위치 front = (front + 1) % n 삭제 위치 rear = (rear + 1) % n 큐 구현 준비 큐는 선형 리스트와 연결 리스트에서 모두 구현할 수 있는 기본적인 자료구조 중 하나이다. 구현에 필요한 메서드 및 속성은 다음과 같다. 생성자 CircularQueue() 비어있고 기본 초기 용량을 가지는 인스턴스 생성 CircularQueue(Circular..
-
큐(Queue)프로그래밍 기초/자료구조 2020. 12. 18. 12:34
스택 스택과는 달리 하나의 입구와 하나의 출구를 가진 자료구조로 선입선출(First In Fist Out) 구조를 가진다. - 삽입 연산(EnQueue) 큐에 데이터를 삽입하고 삽입된 데이터를 마지막으로 표시한다. * 원본 데이터 인덱스 0 : FIRST 1 2 3 : REAR 4 데이터 10 20 30 40 인덱스 0 : FIRST 1 2 3 4 : REAR 데이터 10 20 30 40 50 - 인출 연산(DeQueue) 첫 데이터를 인출하고 해당 데이터 다음에 존재하는 데이터를 최상단으로 표시한다. 인덱스 0 1 : FIRST 2 3 4 : REAR 데이터 10 20 30 40 50 ┗→ 10 큐 구현 준비 큐는 선형 리스트와 연결 리스트에서 모두 구현할 수 있는 기본적인 자료구조 중 하나이다. 구현..
-
스택(Stack)프로그래밍 기초/자료구조 2020. 12. 2. 12:19
스택 데이터를 하나의 접근점을 통해 순차적으로 저장하는 자료구조로 마지막에 입력된 데이터가 가장 먼저 사용되는 후입 선출(Last In First Out) 구조를 가진다. - 삽입(Push) 연산 스택에 데이터를 삽입하고 삽입된 데이터를 최상단으로 표시한다. * 원본 데이터 인덱스 0 1 2 3 : TOP 4 데이터 10 20 30 40 인덱스 0 1 2 3 4 : TOP 데이터 10 20 30 40 50 - 인출(Pop) 연산 최상단에 존재하는 데이터를 인출하고 최상단의 다음에 존재하는 데이터를 최상단으로 표시한다. 인덱스 0 1 2 3 : TOP 4 데이터 10 20 30 40 50 ┗→ 50 스택 구현 준비 스택은 선형 리스트와 연결 리스트에서 모두 구현할 수 있는 기본적인 자료구조 중 하나이다. ..
-
연결 자료구조 - 원형 연결 리스트(Circular Linked List)프로그래밍 기초/자료구조 2020. 11. 11. 08:45
원형 연결 리스트 원형 연결 리스트는 마지막 노드가 처음 노드를 가리키는 환형 구조가 되는 연결 리스트로 단일 연결 리스트와 이중 연결 리스트에 모두 적용이 가능하다. - 단일 연결 리스트 적용 예 - 이중 연결 리스트 적용 예 ※ 리스트 순회 시 다음 노드가 첫 노드인 경우 순회를 종료하면 된다. 원형 연결 리스트 구현 준비 원형 연결 리스트는 단일 연결 리스트 혹은 이중 연결 리스트의 삽입과 삭제, 기능 연산에서 리스트의 끝을 확인하는 방식을 변경하여 구현할 수 있다. 단일 연결 리스트 혹은 이중 연결 리스트를 원형 연결 리스트로 변경하기 위해 다음의 메서드를 수정해야 한다. 생성자 복사 생성자 메서드 데이터 삽입 메서드 데이터 삭제 메서드 기능 메서드 단일 원형 연결 리스트 구현 SinglyLink..