그래프 비선형적 자료구조. 회사 조직도와 같은 계층을 표현한다던가 친구 관계도를 표현하는 것처럼 말이다. 그래프(graph)는 관계에 특화된 자료구조로 정점(Vertex)과 간선(Edge)으로 구성되어 있다. 각 정점은 고유하게 식별되는 객체이고, 간선은 정점 간의 관계를 표현한다. 종류 그래프의 종류에는 간선이 방향성을 가는것으로 그래프를 판단해서 알수있는 방향 그래프와 무방향 그래프로 구분할수있으며 간선이 단순 연결 이상의 정보를 가지는 가중치 그래프도 있다. 용어 정점끼리는 인접(Adajcent)하다고 한다. 부속(Incident)되어 있다고 한다. 정점에 부속되어 있는 간선의 수를 차수(Degree)라고 하며 정점으로 들어오는 방향인지, 나가는 방향인지 구분해 진입 차수(In-degree), 진출..

트리는 그래프의 일종으로 계층형 자료구조 트리는 데이터가 저장된 노드(Node)와 노드 간 관계를 표현하는 간선(Edge)으로 구성된다. 용어 트리에는 여러가지 용어가 있다. 그림을 참고하자 루트(Root) : 첫 노드 조상(Ancestor) 노드 : 한 노드에서 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드 자손(Descendant) 노드 : 조상 노드의 반대 차수(Degree) : 한 노드가 가지는 서브 트리의 수. 노드의 차수 중 최댓값을 트리의 차수라 한다. 내부(Internal) 노드 : 단말 노드를 제외한 나머지 노드 ex) A , B , C , D , E 포레스트(Forest) : 트리의 집합 레벨(Level) : 높이 순회 전위 순회 DFS 방식과 비슷하다 A - B - D - ..

(선형리스트) 순차 자료 구조 (배열을 이용) 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식 모든 데이터가 메모리에 연속적으로 저장된다. 데이터 저장을 위해 정확하게 데이터 크기만큼 메모리를 사용한다. 읽기 선형 리스트는 임의 접근이 가능하기 때문에 O(1)의 시간이 걸린다. 검색 하나하나 원소를 비교해가야 하므로 O(n)의 시간이 걸린다. 정렬되어 있다면 이진 검색을 사용할 수 있으며 이 경우 O(logn)이다. 삽입 원소를 어디에 삽입하냐에 따라 시간이 달라진다. 맨 끝에 데이터를 추가할 경우 O(1)이지만, 처음이나 중간이라면 모든 데이터를 이동해야 하기에 O(n)이 걸린다. 삭제 삽입과 마찬가지로 원소를 어디에서 삭제하냐에 따라 시간이 달라진다. 맨 끝의 데이터를 삭제할 ..

학습목표 ● 자료구조에 대해서 이해하고 적절하게 사용할 수 있다. ● 기초 알고리즘을 이해하고 적절하게 사용할 수 있다. ● 알고리즘은 분석할 수 있다. ● 프로그래밍 능력을 증진시킨다. 재귀 재귀는 함수가 자신을 호출하는것을 의미함. 재귀함수 : 자기 자신을 호출하는 함수. '분할 정복(divide & conquer)' 방식 문제에 따라 전체를 한 번에 해결하기보다 같은 유형의 하위 작업으로 분할하여 작은 문제부터 해결하는 방법이 효율적*일 수 있기 때문이다. 잘못된 재귀함수 -> 스택 오버플로 재귀의 구조는 중단시키는 기저 조건과 기저 조건을 수렴하게되는 재귀 조건으로 구성되어있음. 자료구조 자료구조는 크게 선형 구조와 비선형 구조로 나누어 진다. 선형 구조에는 리스트,스택,큐가 있다. 비선형 구조에..