jwlee

그래프의 개념 그래프는 노드(node)와 그 노드들을 연결하는 간선(Edge)을 하나로 모아 놓은 자료 구조입니다. 즉, 연결 되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조입니다. 이미 생활 속에서도 그래프 알고리즘이 적용되어 있습니다. 지도나 지하철 노선도를 확인하거나 최적의 경로를 찾아주는 데 사용한 것이 바로 그래프 알고리즘 입니다. 그래프와 트리의 차이 그래프 트리 정의 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조 그래프의 특별한 한 케이스('최소 연결 트리'라고도 불림), DAG(Directed Acyclic Graph. 방향성이 있는 비순환 그래프)의 한 종류 방향성 방향 그래프(Directed), 무방향 그래프(Undirected), 가중치 그래프(Weight), 부..

우선순위 큐는 이름 그대로 우선순위를 고려하여 만든 큐이다. 우선순위 큐의 규현 방법에는 '배열, 연결리스트, 힙' 으로 총 3가지가 있다. 이 중에서 우선순위 큐는 힙으로 구현하는게 가장 효율이 좋다. 그 이유는 배열과 연결리스트의 경우 데이터의 추가, 삭제의 시간 복잡도가 O(n)인 반면, 힙의 경우에는 추가, 삭제의 시간 복잡도가 log2(n)이기 때문이다. 힙은 배열과 연결리스트 중에서 배열로 구현을 한다. 그 이유는 연결리스트로 구현을 하면 새로운 노드를 마지막 위치에 추가하기가 쉽지 않기 때문이다. 힙에서의 데이터 저장과정 위 그림을 보면 새로운 데이터를 마지막 위치에 저장한 후 부모 노드와 비교연산을 통해 제자리를 찾아가는 것을 알 수 있다. 힙에서의 데이터 삭제과정 위 그림을 보면 우선순위..

수식 트리수식 트리의 이해수식 트리는 이진 트리를 이용해서 수식을 표현해 놓은 것을 말한다. 따라서 수식 트리와 이진 트리는 구분이 되는 별개의 것이 아니다. 일반적으로 7 + 4 * 2 - 1과 같은 인간이 보기 좋은 수식(중위 표기법)은 컴퓨터가 이해하기 어렵다. 따라서 컴파일러는 이와 같은 수식을 수식 트리로 재 표현한 다음에 계산한다. 왜냐하면 수식 트리는 연산 과정에서 우선순위를 고려하지 않기 때문에 해석이 쉽기 때문이다. 아래는 중위 표기법을 수식 트리로 재 표현한 모습이다. 수식 트리의 계산 순서는 다음과 같다. 이렇듯 수식 트리는 연산의 순서가 명확하고, 연산의 과정을 쉽게 파악할 수 있는 이진 트리의 일종이다. 중위 표기법을 수식트리까지 옮기는 과정은 아래와 같다. 중위 표기법 -> 후위..

큐(Queue)원형 큐(Circular Queue)원형 큐는 배열의 선형 큐의 머리와 꼬리를 연결한 큐이다. 기본적으로 원리는 다음과 같다. EnqueueDequeue 이렇듯 추가를 하면 R(Rear)이 다음 인덱스를 가리키고 그 곳에 데이터를 추가한다. 삭제를 할 경우에는 F(Front)가 다음 인덱스로 이동한다. 여기서 위의 경우에는 Empty와 Full을 구분하기가 어렵다. 그래서 배열의 길이가 n일 때 n-1개 채울 경우 꽉 찬 것으로 간주한다. 원형 큐의 구현 헤더파일1234567891011121314151617181920212223242526#ifndef __C_QUEUE_H__#define __C_QUEUE_H__ #define TRUE 1#define FALSE 0 #define QUE_L..

원형 연결 리스트개념단순 연결리스트는 마지막 노드는 NULL을 가리켰다. 이 마지막 노드를 다시 첫 번째 노드를 가리키게 하면 그게 바로 원형 연결 리스트이다.여기서 새 노드를 머리에 추가해 보겠다. 그러면 리스트는 다음의 형태가 된다. 이번엔 반대로 꼬리에 추가해보면 다음과 같다.두 경우를 비교해보면 머리에 추가하든 꼬리에 추가하든 둘 다 2가 저장된 노드를 가리킨다는 것을 알 수 있다. 이러한 특성 때문에 head를 없애고 tail만 둔 변형된 연결 리스트가 나왔다. 형태는 아래와 같다.(보통 원형 연결 리스트라고 하면 변형된 원형 연결 리스트를 뜻함)여기서 꼬리를 가리키는 포인터 변수는 tail이고, 머리를 가리키는 포인터 변수는 tail->next이다. 이로 인해 머리와 꼬리에 새로운 노드를 추가..

단순 연결 리스트리스트의 ADT와 구현리스트의 구현데이터 조회데이터 조회로 쓰이는 함수는 LFirst와 LNext이다. LFirst함수는 다음과 같다.1234567891011int LFirst(List * plist, LData * pdata){ if(plist->head->next == NULL) //더미 노드가 널을 가리키면 데이터가 없음 return FALSE; plist->before = plist->head; //before은 더미 노드를 가리킴 plist->cur = plist->head->next; //cur은 첫 번째 노드를 가리킴 *pdata = plist->cur->data; //첫 번째 데이터를 전달 return TRUE;}Colored by Color Scriptercs위 함수가 호..

단순 연결 리스트단순 연결리스트란 한 쪽 방향으로만 연결 조회 삭제 등이 가능한 자료구조를 말한다. 보통 자료를 저장하는 도구로는 배열이 대표적이지만 배열은 크기가 정적이기 때문에 처음에 선언한 크기보다 더 많은 양을 저장하기 어렵다. 그래서 동적으로 저장 가능한 연결 리스트가 나온 것이다. 연결 리스트의 ADT와 구현연결 리스트의 ADT정의● 리스트 초기화 ● 데이터 저장● 데이터 조회● 데이터 삭제● 리스트 정렬 이제 이 5개의 기능을 함수로 제시만 하고 구현하지 않으면 된다. 12345678910void ListInit(List * plist);void LInsert(List * plist, LData data); int LFirst(List * plist, LData * pdata);int LNe..

하노이 타워(The Tower of Hanoi)하노이 타워를 재귀를 이용해 코드로 구현해 볼 것이다. 하노이 타워의 패턴우선 원반이 3개인 경우를 설명해 보겠다.(젤 작은 원반이 번호도 작음) 1. 원반1을 A에서 C로 이동2. 원반2을(를) A에서 B로 이동3. 원반1을 C에서 B로 이동4. 원반3을(를) A에서 C로 이동5. 원반1을 B에서 A로 이동6. 원반2을(를) B에서 C로 이동7. 원반1을 A에서 C로 이동 위 과정의 패턴들이 원반의 수가 몇 개가 되든 계속 반복된다. 아래는 원반이 4개인 경우를 그림으로 표현한 것이다.여기서 원반 1,2,3을 A에서 B로 그리고 B에서 C로 이동시키는 과정이 없는 이유는 앞에서 이미 3개를 다른 막대로 옮기는 과정을 실행했기 때문이다. 따라서 위 내용들을 ..