1. 개요 [그림 1] 분할 정복법 ( Divide and conquer ) 알고리즘 방법론중 하나인 분할정복 ( Divide and conqeur ) 알고리즘은 하나의 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 분할 정복 알고리즘은 보통 재귀함수 ( Recursive function )을 이용해서 구현하는 것이 일반적이나 빠른 실행이나 부문제 해결 순서 선택을 위해 재귀호출을 사용하지 않고 스택(Stack), 큐(Queue) 등의 자료구조를 이용하여 분발 정복법을 구현하는 것도 가능하다. 분할 정복의 설계전략으로는1. 분할 (Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.2. 정복 (Conquer) : 나눈 작은 문제를 각각 해결한다.3. 통합 (Combine) : 해결된..
1. 개요 [그림 1] 재귀호출의 과정 재귀적 호출 함수 ( Recursive call ) 란 작업을 작은 단위로 쪼개서 재귀 호출된 함수 내에서 이 조각중에 하나를 해결하고, 나머지 조각들은 자기 자신을 또 호출해서 해결하는 방식으로 처리되는 함수로 간단히 말해서 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수이다.재귀호출함수를 구현하려면 2가지 부분이 필요하다. 하나는 기본 부분 (Base part)와 유도 부분 (Inductive part)이다. 기본 부분은 재귀호출이 나중엔 결국 끝이 나야하므로 종결조건을 위한 부분이고 유도 부분은 새로운 집합의 원소를 생성하기 위해 재귀하는 부분이다. 재귀적 프로그래밍은 일반 반복 ( for,,while...등 ) 프로그래밍에 비해 간결하다는 점이..
1. 개요 [그림 1] 가중치배열 ( Weight Array ) 다익스트라 알고리즘 ( Dijstra Algorithm ) 은 가중치가 부여된 그래프에서 두 정점 사이의 최단 경로를 찾을 때 사용하는 알고리즘이다. 이 알고리즘에서는 어떤 시작점 S가 주어졌을 때, 그 정점에서 시작하여 다른 모든 정점으로 가는 최단 경로를 찾을 수 있기 때문에 결과적으로 어떤 최종 목적지 T로 가는 최단 경로를 구할 수 있다. 다익스트라 알고리즘에서 가장 중요하고 핵심이 되는 "가중치 배열 (Weight Array)"은 시작점 S를 기준으로 각 정점의 최단거리를 가리키는 배열이다. 2. 다익스트라 알고리즘 (Dijstra Algorithm) 코드 구현 및 설명 /*--------------------------------..
1. 개요 [그림 1] 인접리스트로 표현한 그래프 이전에는 인접행렬이 아닌 링크드리스트를 이용하여 인접리스트로 그래프를 표현하는 방법에 대해 알아보겠다. 인접행렬이 최소그래프에 있어서 메모리 낭비가 심했다면, 인접리스트는 정점의 갯수, 간선의 갯수만큼 메모리를 할당하므로 메모리적인 측면에 있어 인접행렬법보다 좋다. 따라서 최소그래프 표현에 적합하다. 그림과 같이 각 정점에서 간선으로 연결된 정점들을 리스트 형태로 연결해 놓는 기법이다. (※ 인접리스트법도 당연히 무방향 그래프에서의 대칭성을 고려하여 코드를 구현하여야 한다) 2. 그래프 구현 1. 구조체 및 함수 선언 typedef struct _node { int vertex; struct _node *next; }Node; typedef struct ..
1. 개요 [그림 1] 인접행렬로 나타낸 그래프 그래프 자료구조를 나타내는 방법으로 두 가지가 있다. 하나는 인접 행렬 (adjacent Matrix) 이고 하나는 인접 리스트 (adjacent List)법이있다. 이번 글에서는 인접행렬로 그래프를 나타내는 방법을 알아보겠다. 인접행렬법은 배열로 그래프를 나타내는 것이므로 밀집그래프 (완전그래프)를 표현하는데 적절하다. 2차원 배열 특성상 한번에 메모리를 잡아햐 하기때문에 빈 공간이 생기면 메모리 낭비가 생기므로 밀집그래프를 표현하는데 있어 좋은 방법이다. (※무방향 그래프를 표현 시 대칭성을 고려해야 한다.) 2. 그래프 구현 1. 구조체 및 함수 선언 extern int check[]; /*----------------------------------..
1. 개요 [그림 1] 트리 (Tree) "트리 (Tree)" 자료구조란 나무를 뒤집은 모습으로 계층구조를 표현하기에 적합한 자료구조이다. 맨 위의 노드가 "루트노드 (Root Node)" 라고 하며 이 노드 아래에 있는 노드들은 다시 트리 구조가 된다. 이런 구조를 "서브 트리 (Sub Tree)"라고 한다. 또한, 임의의 노드의 조상과 자손을 지칭 할 수 있는데, 임의의 노드 바로 위에 있는 노드를 "부모 노드 (Parent Node)" 라고 하고 그 바로 아래 노드들을 "자식 노드 (Children Node)"라 한다. [그림 2] 이진 트리 (Binary Tree) 이런 트리구조에서 파생된 자료구조를 "이진트리 (Binary Tree)"라고 부르는데, 이진트리는 모든 노드들의 자식 노드가 두 개 ..
1. 개요 선형 큐 (Linear Queue) 의 삽입 및 삭제 과정 스택(Stack)자료구조와 달리 선입선출(先入先出, First In First Out; FIFO)의 자료구조로써, 데이터가 나가는 위치, 큐의 첫번째 위치를 Front 라고 하고 데이터가 삽입되는 지점, 큐의 마지막 데이터의 한 칸 다음 위치를 Rear 혹은 Back이라고 한다. 큐에 데이터를 삽입하는 과정을 Enqueue, 빼는 과정을 Dequeue라고 한다. 선입선출 형태이므로 주로 대기열, 줄서기 같은곳에 쓰이는 구조이다. 1. 선형 큐 (Linear Queue) 예를들어 큐 사이즈가 5인 큐가 있다고 하자. 초기에는 Front와 Rear 둘다 0을 가리키고 있는상태이다. 데이터를 하나 삽입하면 Front값을 그대로 Rear값은 ..
1. 개요 후입선출(後入先出, Last In First Out; LIFO) 의 자료구조로, 상자의 형태를 한 자료구조이다. 데이터의 삽입을 Push, 데이터의 출력을 Pop이라고 하며, 스택을 크게 두 가지로 나누면 Ascending Stack VS Descending Stack으로 나눌 수 있다. 스택은 배열과 링크드 리스트로 구현할 수 있는데, 여기서는 링크드리스트를 이용한 스택을 구현해 보겠다. 2. 코드 구현 2-1 ) 구조체 구현 typedef struct _stacknode Snode; struct _stacknode { DataType data; Snode *next; }; typedef struct _stack { Snode *head; Snode *tail; Snode *cur; }Sta..
1. 개요 자료구조의 일종인 링크드리스트는 각 노드당 데이터를 저장하는 데이터필드 영역과 다음 노드를 가리키는 노드 포인터 영역으로 구성된 자료구조이다. 비슷한 방식으로 배열이 있지만 배열은 처음부터 메모리를 할당하고 시작하기 때문에, 링크드리스트에 비해 데이터의 삽입이나 삭제가 어렵다. 반면, 링크드리스트는 노드를 데이터를 삽입할 때마다 메모리를 할당하고 데이터를 이어주는 형식이라 배열에 비해 메모리 낭비가 덜 하다는 장점이 있다. 단일 연결 리스트 (Single LinkedList) 단순 연결 리스트 (Single LinkedList)는 단 방향 연결 리스트로 다음 노드에 대한 참조만을 가지는 가장 단순한 형태의 연결 리스트이다. 단순 연결 리스트는 단 방향이기 때문에 Head 노드의 주소를 잃어버릴..