언제나 휴일

[C언어 알고리즘] 6.동적 프로그래밍 커다란 문제를 해결하는 과정을 여러 단계로 나누어 해결하는 알고리즘들이 있어요. 그 중에 동적 프로그래밍은 현재 단계에서 다음 단계로 진행하면서 알 수 있는 정보를 학습해요. 그리고 이 학습 정보를 이용하여 다음 단계로 진행하여 전체 문제를 해결하는 알고리즘이예요. 이전 단계에서 다음 단계로 진행할 수 있는 경우의 수가 고정일 때는 간단하게 문제를 해결할 수 있어요. 하지만 이전 단계에서 다음 단계로 진행할 수 있는 경우의 수가 많을 때는 스택을 이용해서 문제를 해결하여 비교적 간단하게 만들 수 있어요. 하지만 수행 성능은 떨어질 수 있어요. 먼저 이전 단계에서 다음 단계로 진행할 수 있는 경우의 수가 고정인 문제로 대표적인 것이 피보나치 수열을 구 문제예요. 여기..

[C언어 알고리즘] 5.3 진입 차수, 진출 차수이번에는 그래프에서 중요하게 생각하는 특징 중에 진입 차수와 진출 차수를 알아보아요. 특정 점정으로 갈 수 있는 간선의 수를 해당 정점의 진입차수(In degree)라고 불러요. 그리고 특정 정점에서 갈 수 있는 간선의 수를 진출차수(Out degree)라고 부르죠. 이번에는 그래프의 이와 같은 정보를 확인하는 기능을 구현해 보아요. 그래프 구현은 앞에서 소개한 것을 참고하세요. 이번에 추가할 기능은 진입 차수와 진출 차수를 확인하는 기능이예요. void ViewIndegree(Graph *g);//진입차수 확인 void ViewOutdegree(Graph *g);//진출차수 확인 먼저 진입 차수를 구하는 기능을 작성하기로 해요. 진입 차수는 상대 정점에서..

[C언어 알고리즘] 5.2 인접 행렬로 방향성 있는그래프방향성 있는 그래프는 간선의 출발지와 목적지가 정해져 있는 그래프를 말해요. 방향성 있는 그래프를 표현하는 방법 중에 간단한 그래프에는 인접 행렬을 많이 사용해요. 먼저 그래프 형식을 정의하기로 해요. 그래프 형식은 방향성 없는 그래프와 차이가 없어요. 정점의 개수와 인접 행렬을 멤버를 추가하세요. typedef struct{//그래프 형식 정의 int vn; //정점 개수 int **matrix;//그래프 인접 행렬 } Graph; 그래프를 생성하고 소멸, 추가, 정보 출력하는 기능을 제공하기로 해요. Graph *NewGraph(int max_vertex);//그래프 동적 생성 void DeleteGraph(Graph *graph);//그래프 소..

[C언어 알고리즘] 5.1 인접 행렬로 방향성 없는그래프방향성 없는 그래프는 정점 A에서 정점 B로 이동할 수 있으면 언제나 정정 B에서 정정 B로 이동할 수 있음을 보장하는 그래프예요. 방향성 없는 그래프를 표현하는 방법 중에 간단한 그래프에는 인접 행렬을 많이 사용해요. 인접 행렬로 방향성 없는 그래프를 표현하면 좌상단에서 우하단으로 이어지는 대각선에 대칭 형태죠. 먼저 그래프 형식을 정의하기로 해요. 인접 행렬로 그래프를 표현할 때 그래프에는 정점 개수와 인접 행렬이 필요하겠죠. typedef struct{//그래프 형식 정의 int vn; //정점 개수 int **matrix;//그래프 인접 행렬 }Graph; 여기에서는 그래프 생성, 소멸, 간선 추가, 이웃 정점을 보여주는 기능을 제공하기로 해..

[C언어 알고리즘] 4.3.2 병합 정렬 알고리즘 구현 이제 병합 정렬 알고리즘을 구체적으로 구현합시다. 병합 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) ah:= n/2 bh:= n - ah; 조건(n이 1보다 작거나 같으면) 종료 병합정렬(base,ah,compare) 병합접열(base+ah,bh,compare) tbase에 동적 메모리 할당(원소크기*원소개수) 메모리 복사(tbase,base) ai:=0 bi:=ah i:=0 반복(ai가 ah보다 작으면서 bi가 n보다 작다) 조건(tbase[ai]가 tbase[bi]보다 작거나 같으면 base[i] := base[ai] ai:= ai+1 아니면 base[i]:= base[bi] bi:= bi+1 i:=i+1 반복(..

[C언어 알고리즘] 4.2 이진 탐색 알고리즘 이번에는 이진 탐색 알고리즘을 알아봅시다. 이진 탐색 알고리즘은 특정 키순으로 정렬 상태의 배열에서 원하는 값의 요소를 빠르게 검색하는 알고리즘입니다. 순차적으로 비교하여 검색한다면 자료의 개수가 N개인 배열에서 최악의 경우 N번 비교해야 합니다. 하지만 이진 탐색 알고리즘으로 검색하면 logN 번이면 검색할 수 있습니다. 이진 탐색 알고리즘은 배열의 중간에 있는 요소와 비교해서 배열의 요소가 크면 재귀적으로 앞쪽 배열에서 검색하고 배열의 요소가 작으면 재귀적으로 뒤쪽 배열에서 검색합니다. 만약 같은 값이면 해당 인덱스를 반환합니다. 그리고 배열의 원소 개수가 0이면 재귀를 탈출하기 위해 인덱스 -1을 반환합니다. 이진 탐색 알고리즘(base:배열, asiz..

선형 자료구조에 보관한 자료 중에 최소값을 찾는 방법은 많습니다. 그 중에 분할 정복 알고리즘으로 해결하는 방법을 알아봅시다. 분할 정복 알고리즘에서는 모집합을 부분 집합으로 나누는 작업을 선행합니다. 원하는 기준에 맞게 부분 집합으로 분리한 후에 부분 집합에서 원하는 결과를 구합니다. 그리고 해결한 부분을 합쳐서 다시 커다란 집합에서 원하는 결과를 구하는 과정을 반복합니다. 최소값(최대값) 찾기 알고리즘도 분할 정복 알고리즘으로 문제를 해결할 수 있습니다. 배열의 원소 중에 최소값을 찾기 위해 원소 개수가 2보다 크면 배열의 앞 부분에서 최소값을 찾기 위해 재귀함수를 호출하고 마찬가지로 뒷 부분에서 최소값을 찾기 위해 재귀함수를 호출합니다. 그리고 배열의 앞 부분의 최소값과 뒷 부분의 최소값을 비교하여..

[C언어 알고리즘] 3.5.3 힙 정렬 알고리즘 구현 이번에는 힙 정렬 알고리즘을 구현해 보기로 해요. 힙 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 초기 힙 구성 루트와 맨 마지막 자손 교환 n을 1 감소 반복(n: n->1) 힙 구성 루트와 맨 마지막 자손 교환 n을 1 감소 초기 힙 구성(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복(i:1->n) j:=1 반복(j>0) pa:=PARENT(j) 조건: compare(base[j], base[pa])이 0보다 크면 base[j], base[pa] 교환 j: = pa 아니면 내부 루프 탈출 힙 구성(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복 lc:=..

[C언어 알고리즘] 3.4.4 이진 탐색 트리 소스 코드 테스트 로직을 구현합시다. 테스트 로직은 단순히 이진 탐색 트리를 생성한 후에 다양한 도서 정보를 추가하고 검색과 삭제 기능 등을 호출하여 잘 동작하는지 확인하는 것입니다. 이 부분에 관한 별도의 설명은 생략할게요. //common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제 //Book.h #pragma once #include "common.h" #define MAX_TIT_LEN 200 #define MAX_AUT_..

[C언어 알고리즘] 3.4.3 이진 탐색 트리 구현 이제 이진 탐색 트리를 구현합시다. 이진 탐색 트리는 자료를 보관하는 컬렉션 중에 탐색 효율성을 높인 자료구조입니다. 여기에서는 도서를 보관하는 이진 탐색 트리를 구현하기로 할게요. 먼저 노드를 정의합시다. 이진 탐색 트리의 노드는 데이터와 왼쪽 자식 노드의 위치, 오른쪽 자식 노드의 위치로 구성합니다. 이 책에서는 삭제 편의성을 위해 부모 노드의 위치도 포함할게요. 그리고 동적으로 노드를 생성하는 함수를 제공합시다. typedef struct _Node Node; struct _Node { Book *book; Node *lch; Node *rch; Node *pa; }; Node *New_Node(Book *data); 이진 탐색 트리에는 root ..