언제나 휴일

8. 정점과 간선 집합으로 표현한 그래프 그래프를 표현하는 방법은 다양합니다. 이차원 배열을 이용해서 인접 행렬로 표현하는 방법도 있고 정점과 간선의 집합으로 표현하는 방법도 있습니다. 이차원 배열을 이용해서 인접 행렬로 표현하는 방법은 정점의 개수가 n일 때 행과 열이 n인 이차원 배열을 만들고 두 개의 정점 사이의 거리를 배열의 항목 값으로 설정하는 형태로 작성합니다. 이 방법은 다른 책과 인터넷 검색 등을 통해 어렵지 않게 찾아볼 수 있을 것입니다. 하지만 그래프의 정점의 개수가 많으면 실제 정점과 정점 사이에 존재하지 않는 간선을 위한 부분이 전체의 많은 부분을 차지하여 메모리 효율과 수행 속도가 나빠질 수 있습니다. 이 책에서는 정점과 간선의 집합을 이용하여 그래프를 나타내는 방법을 사용할게요...

현재 완료, 과거완료현재완료과거부터 현재까지 이어지는 상태나 동작을 표현할 때 사용합니다."have/has + 과거분사" 형태로 표현합니다. He has been in the hospital. (그는 입원 중입니다.)It has been a long time. (그것은 오래 전의 일이죠.)I has lived in Seoul for seven years. (서울에 7년째 살고 있어요.)She has played the piano since she was five. (그녀는 다섯살 때부터 피아노를 연주했어요.) 과거 시제는 과거의 일이나 상태로 현재는 그렇지 않다는 의미를 내포하고 있습니다.He was in the hospital.(그는 병원에 있었어요. - 과거시제이므로 현재는 병원에 있지 않다는 의미를..

지나친 자만으로 충신(득래, 밀우, 유유)들을 잃은 동천왕 고구려의 11대 왕은 동천왕(227~248)입니다. 형사취수(형을 죽은 뒤에 동생이 형수와 결혼)한 산상왕은 왕후 우씨와 자식을 얻지 못했다고 합니다. 이에 주통촌 출신의 용녀로부터 얻은 자식이 동천왕입니다. 동천왕이 왕위에 올랐을 때는 오나라와 우호관계를 유지하였고 충신들과 평안한 나라를 만드는데 힘을 쏟았다고 하네요. 하지만 234년에 위와 화친하면서부터 정세는 180도 바뀌기 시작합니다. 238년 위가 요동의 공손연을 토벌할 때 군사 천여명을 보내 위를 도았지만 이는 두 나라의 국경이 맞닿는 것을 의미하였습니다. 30대의 젊은 기상으로 위나라와 싸워 서안평을 함락하였고 이 기세를 몰아 계속 전쟁 준비를 하였습니다. 하지만 대장이었던 득래는 ..

두 번의 국모 우씨, 남편 고국천왕을 죽이고 산상왕과 재혼하다. 고구려의 9대 왕은 고국천왕(179~197)이며 10대 왕은 산상왕(197~227)입니다. 그런데 고국천왕과 산상왕은 부인이 같습니다. 바로 두 번 국모를 한 우씨입니다. 고국천왕은 가난한 사람들에게 곡식을 빌려 주었다가 가을 추수가 끝난 후에 되갚게 하는 ‘진대법’을 실시한 왕입니다. 진대법은 농민 출신 재상인 을파소가 의견을 낸 것을 다른 신하들의 반대에도 불구하고 고국천왕이 힘을 실어 진행할 수 있었던 것입니다. 이러한 고국청왕은 그의 아내 왕후 우씨에 의해 비명횡사합니다. 왕후 우씨는 귀족들이 권력에서 멀어지고 을파소 등의 재야출신이 힘을 얻는 것을 시기하여 반란을 일으킵니다. 197년 5월 봄에 비명횡사한 고국천왕의 죽음은 후계자였..

7.6 진입 차수, 진출 차수 소스 코드//Program.c #include #include #include typedef struct{//그래프 형식 정의 int vn; //정점 개수 int **matrix;//그래프 인접 행렬 } Graph; Graph *NewGraph(int max_vertex);//그래프 동적 생성 void DeleteGraph(Graph *graph);//그래프 소멸 void AddEdge(Graph *graph, int start, int goal);//간선 추가 void ViewGraph(Graph *graph);//그래프 정보 출력 void ViewIndegree(Graph *g);//진입차수 확인 void ViewOutdegree(Graph *g);//진출차수 확인 in..

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

7.4 인접 행렬로 방향성 있는 그래프 소스 코드//Program.c #include #include #include typedef struct{//그래프 형식 정의 int vn; //정점 개수 int **matrix;//그래프 인접 행렬 } Graph; Graph *NewGraph(int max_vertex);//그래프 동적 생성 void DeleteGraph(Graph *graph);//그래프 소멸 void AddEdge(Graph *graph, int start, int goal);//간선 추가 void ViewGraph(Graph *graph);//그래프 정보 출력 int main(void) { Graph *graph; graph = NewGraph(6);//그래프 동적 생성 AddEdge(gra..

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

7.2 인접 행렬로 방향성 없는그래프 소스 코드 //Program.c //방향성 없는 그래프 #include #include #include typedef struct{//그래프 형식 정의 int vn; //정점 개수 int **matrix;//그래프 인접 행렬 }Graph; Graph *MakeGraph();//그래프 만들기 void ViewNeighbors(Graph *g);//이웃 정점 보여주기 void DeleteGraph(Graph *graph);//그래프 소멸 int main(void) { Graph *graph; graph = MakeGraph();//그래프 만들기 ViewNeighbors(graph); //이웃 정점 보여주기 DeleteGRaph(graph);//그래프 소멸 return 0..

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