코딩스토리

목차 그래프 추상 데이터 타입 그래프의 기본 연산 최소 비용 신장 트리 최단 경로와 이행적 폐쇄 작업 네트워크 1. 그래프 추상 데이터 타입 그래프는 이산수학에서도 배웠다시피 오일러의 퀸즈 버그 다리 문제에서 처음 사용되었다고 한다. 그래프의 정의 : 그래프는 두 개의 집합 V와 E로 구성된다. V는 정점(vertex), E는 간선(edge)로 이루어진 유한 집합이다. 임의의 그래프 G = (V, E)로 나타낼 수 있으며, 간선을 나타내는 정점의 쌍에 순서가 있거나 없음을 통해 무방향, 방향 그래프로 나눌 수 있다. 예를 들어 트리구조도 그래프라 할 수 있는데 이는 무 방향 그래프라 할 수 있다. ex) (u,v) 는 무방향 그래프에서 표현, (v, u)와 같은 표현임. 는 유방 향 그래프에서 표현, 와..

목차 개요 이진트리 이진트리 순회와 트리 반복자 이진트리의 추가 연산 스레드 이진 트리 히프 이원 탐색 트리 선택 트리 포리스트 1. 개요 5강을 공부하기 위해선 트리에 대해 알아야 한다. 트리 구조란 정보의 항목들이 가지로 연결될 수 있게 데이터가 조직되는 구조이다. 예를 들면 족보 같은 경우 조상과 자손들, 부모와 자식들의 관계를 잘 보여준다. 정의 : 트리는 한 개 이상의 노드로 이루어진 유한 집합 (1) 노드 중에는 루트(root)라고 하는 노드가 있음 (2) 나머지 노드들은 n(>=0) 개의 분리 집합 T1,..., Tn으로 분할될 수 있다. 여기서 T1,..., Tn은 각각 하나의 트리이며 루트의 서브 트리(subtree)라고 한다. 트리의 차수 = max [노드의 차수] -> 쉽게 말해 자식..

목차 1. 단순 연결 리스트와 체인 2. C++에서의 체인 표현 3. 템플릿 클래스 체인 4. 원형 리스트 5. 가용 공간 리스트 6. 연결 스택과 큐 7. 다항식 8. 동치 관계 9. 희소 행렬 10. 이중 연결 리스트 11. 범용 리스트 12. 가상 함수와 동적 바인딩 1. 단순 연결 리스트와 체인 List = [ CAT, HAT, EAT, BAT, RAT, SAT,...] 다음과 AT로 끝나는 순서 리스트가 있다고 생각해보자. 지금까지 공부했던 배열은 삽입과 삭제에 불필요한 동작들이 많아 많은 시간이 소모되었었다. 이런 데이터들의 이동적인 측면에서의 문제점을 해결하기 위해서는 연결 리스트라는 자료구조가 도움이 된다. 연결 리스트의 표현 방법으로는 pointer(포인터)와 link(링크)가 연관되어 ..

목차 1. C++의 템플릿 2. 스택 추상 데이터 타입 3. 큐 추상 데이터 타입 4. C++의 서브타입과 상속 5. 미로 문제 6. 수식의 계산 1. C++의 템플릿 템플릿이란 클래스와 함수들의 재사용성을 증대시키기 위하여 C++에서 제공하는 기법으로 같은 알고리즘으로 문제를 해결할 수 있을 때, 인수(매개변수)의 타입만 교체하고 싶을 때 사용한다. 예를 들어보자. template void add (T& a, T& b){ T sum = a + b; } 위의 코드 add함수를 보면 원래대로라면 사용자가 int형으로 인수를 받을지, float형으로 받을지를 모르기 때문에 int형 인수를 갖는 add와 float형을 인수로 갖는 add를 두 번 정의해 줘야 한다. 하지만 template 클래스로 정의함으로써..

목차 1. 추상 데이터 타입과 C++ 클래스 2. 추상 데이터 타입으로서의 배열 3. 다항식 추상 데이타 타입 4. 희소 행렬 5. 배열의 표현 1. 추상 데이타 타입과 C++ 클래스 C++에서는 C언어의 struct 도 사용 가능하지만, 명세와 구현을 구별하고(데이터 추상화), 정보를 은닉(데이터 캡슐화) 하기 위해 class(클래스)라고 하는 명시적인 기법을 제공한다. class는 아래와 같이 네 부분으로 구성된다. 클래스 이름 : ex) Rectangle 데이터 멤버 : 클래스를 만드는 데이타 ex) xLow, height,... -> priavte 영역에 선언된다(for 데이터 캡슐화) 멤버 함수 : 클래스의 객체에 적용할 수 있는 연산의 집합 ex) GetHeight()... -> 주로 publ..