드디어 벼르고 별러 보여준다는 영화를 함께 봤다
“쿵푸팬다”
진짜 재미도 있고 좋았지만…영화보다는
으하하……
오늘 하루 종일 같이 있느라
심장터질뻔……
장난으로 어깨에 손올리고 막 얼굴 앞으로 얼굴 들이밀고!!
아놔… 이렇게 순진하고 착한남자한테
그런 장난치면 심장떨려서 미친다구!!
이제 한동안 못본다는게 너무 아쉽다…
아놔 이거 어쩔꺼야!!? 이 아가씨야!
자꾸 맘 가잖니ㅎㅎ
아놔 왜 이렇게 이쁘삼?!!
이 글 보면 또 도끼병 도질라 ㅋㅋ
아 밤세 잠안오겠네 ㅋㅋㅋ
이래저래 많은 일이 있었고
방학은 이래저래 우리를 찾아왔다
하하하 사랑해 방학아~~
시험치고 나오자마자 자료구조보강이 역습해왔고
끝나자마자 신평에 원형이형 우섭이형과 함께 고기를 구워먹으러 갔다
호필이를 데리고 옥상으로 갔는데 자꾸 보일러실로 호필이가 가길래
가봤더니?!
이건뭥미?! 어익후ㅋㅋ
보고 깜놀ㅋㅋㅋ
이거 어쩔?!
범안은 일단 원룸안에 있을것이고
가장 의심스러운건 중보?!!!!
누가 이렇게 훔쳐다놨는지는 모르겠지만
만화에나 나올법한 변태가 우리 주변에도 있구나 싶은게;;;
뭐 어쨌든 고기는 잘 구워먹었다는거~!?
히히 잘 먹었습니다!?
이거 어쩌다보니 에어컨 빵빵한 곳에서
공부하려다가 하라는 공부는 안하고
라면이나 끓여먹으면서 놀고있다
허허허
이게 춰하는건지…덕분에
오늘 논리회로 시험은 저멀리 안드로메다로…
사이좋은??진아랑 진동이 풉?
뭔가 좀 오붓한걸?
어느센가 후룩후룩 잘도먹고 있구나?!
빨간티가 이쁘다는?!>_<
언제나 불만가득한 갈매기!!
잔혹하게 라면을 잡아먹은 잘잔당군
이러고나니 시간은 어느세 12시…
연경이는 젭싸게 집으로 가버렸고
나는 지원이랑 만나서 코인노래방
갔다와서 떡실신!!으하하…
부끄럽다
새로 발매된 브라운 아이즈
엘범을 듣는 모습…우왕!
너무 귀여워! 히히
히히 4650으로 블로깅이라니+_+멋지다
며칠전에찍은 연경이 사진……업로드가 잘되려나? 근데 화질이 시궁창;;;;
언제까지 이렇게 살텐가??????
스스로에게 부끄럽지 말자
어느센가 너라는 늪에 빠져서 어느센가 허우적 허우적……
빠져나오거나 & 빠져나올수 없거나.
혹은 빠져버리던가
이번에는 퀵 정렬 알고리즘이다
물론 역시 이산수학 과제로 나온 녀석이다
정렬은 뭐니뭐니해도 간만한 버블정렬 만한게 없다는..?!;;;;;
임은기 교수님이 들으면 싸닥션 맞을 소리를 덜덜;;
자세한 소스는 밑에서 +_+ㅋ
[spoiler]
// 이산수학 퀵소트 알고리즘 구현
#include <stdio.h>
#define ELEMENT int // 입력받을 자료형
#define MAX_LIST_SIZE 8 // 입력 받을 자료의 수
// 함수 프로토 타입
void quick_sort(ELEMENT list[], int left, int right); // 퀵정렬 함수
int partition(ELEMENT list[], int left, int right); // 퀵정렬 함수 안에서 피벗기준 왼쪽과 오른쪽으로 나누는 함수
void swap(int *row, int *high); // 값을 서로 교환해주는 함수
void display_list(ELEMENT list[]); // 리스트를 출력하는 함수
// 함수 본체
void display_list(ELEMENT list[])
{
int i;
for (i = 0; i < MAX_LIST_SIZE; i++) {
printf(”%d “, list[i]);
}
printf(”\n”);
}
void swap(int *row, int *high)
{
int temp;
temp = *row;
*row = *high;
*high = temp;
}
void quick_sort(ELEMENT list[], int left, int right)
{
int q; // 파티션 함수에서 반환되는 피벗 값을 저장
if (left < right) { // left가 right 와 만날때까지 제귀 호출
q = partition(list, left, right); // partition 함수 호출해서 피벗기준으로 2개의 리스트로 분할
quick_sort(list, left, q-1); // left 값에서 피벗 바로 앞 값까지 호출
quick_sort(list, q+1, right); // 피봇 바로 다음부터 right까지 호출
}
}
int partition(ELEMENT list[], int left, int right)
{
int pivot; // 피벗 값을 저장할 변수
int low, high; // low 값과 high 값을 저장할 변수
low = left; // low는 왼쪽에서부터
high = right + 1; // high 는 오른쪽부터
pivot = list[left]; // 피벗은 리스트의 가장 처음 값을 가진다
do { // low와 high가 만날때까지 반복한다
do {
low++; // list[low]값이 피벗보다 작으면 low 값을 계속 증가시킨다
}
while (low <= right && list[low] < pivot);
do {
high–; // list[high]값이 피벗보다 크면 high 값을 계속 감소시킨다
}
while (high >= left && list[high] > pivot);
if (low < high) swap (&list[low], &list[high]); // low가 high 보다 작을때 list[low]값과 list[high]값을 교환한다
display_list(list); // 중간과정 출력
}
while (low < high);
swap(&list[left], &list[high]); // 피벗을 리스트의 중앙에 위치시킨다
return high; // 피벗의 위치를 반환
}
void main ()
{
ELEMENT list[MAX_LIST_SIZE];
int i;
printf(”값을 입력해주세요\n”);
for (i = 0; i < MAX_LIST_SIZE; i++) {
printf(”%d 번째 값 : “, i+1);
scanf(”%d”, &list[i]);
}
display_list(list); // 사용자가 입력한 리스트를 우선 출력한다.
quick_sort(list, 0, MAX_LIST_SIZE-1); // 입력한 값을 정렬
}
[/spoiler]
이번에 이산수학 과제로 나온 최소 비용 신장 트리……
그래프 알고리즘에서 꽤나 많이 쓰인다는데……
(물론 다양하게 응용 가능?!)
이게 꽤나 머리를 써야 만드는 알고리즘이라서
일단 이해 하면서 외우는 방향으로 코딩하였다.
에휴 이런 알고리즘을 듣자마자 바로 짤수 있다면 얼마나 좋을까?
신이시여 나에게 천재적 재능을 제발;;;;;
자세한 소스는 밑에서 계속~
[spoiler]
#include <stdio.h>
#include <malloc.h>
typedef struct edge // 간선을 나타내는 구조체
{
int vertex[2]; // 시작점과 끝점
int cost; // 가중치
}Edge;
int **make_array(int n);// 배열 만들기
void read_array(FILE *file, int *G[], int n);// 파일에서 배열값 읽기
void convert_array_to_edge(int* G[], Edge E[], int n);// 배열을 간선으로 변환
void convert_edge_to_array(int* G[], Edge E[], int n, int m);// 간선을 배열로 변환
void print_edgy(Edge E[], int n);// 간선 집합 출력
void kruskal(int n, int m, Edge E[], Edge F[]);// 크루스칼 알고리즘
void bubble_sort(Edge E[], int m);// 거품 정렬
void find_merge(int p, int q, int U[]);// 집합을 합치는 함수
int find_set(int i, int U[]);// 해당 정점이 어떤 집합에 속하는지 찾는 함수
int main()
{
int n, m; // n개의 정점과 m개의 간선을 저장할 변수
int **G; // 더블 포인터로 동적 배열을 생성할 변수 선언
int **result; // 최소신장 트리를 인접배열로 나타내기 위한 변수 선언
Edge *E, *F;
FILE* file;
file = fopen(”kruskal_array.txt”, “r”);
if(file == NULL) {
perror(”File open error”);
return 0;
}
fscanf(file, “%d %d”, &n, &m); // 파일로부터 m, n을 입력 받는다
E = (Edge *) malloc(sizeof(Edge)*(m-1)); // 처음 입력 받은 배열을 간선으로 저장하기 위한 Edge
F = (Edge *) malloc(sizeof(Edge)*(n-2)); // 최소비용 신장트리 결과를 저장할 Edge
G = make_array(n); // 배열 만들기
result = make_array(n);
read_array(file, G, n); // 파일에서 배열 정보 읽기
convert_array_to_edge(G, E, n); // 배열 정보를 간선 정보로 변환
printf(”\n## Kruskal 최소 비용 신장 트리 ##\n”); // 크루스칼 알고리즘을 돌린 최소 비용 신장 트리를 F 간선 집합에 삽입
kruskal(n, m, E, F); // 최소 비용 신장 트리 결과 출력
printf(”\n최소 비용 신장 트리 결과\n”);
print_edgy(F, n);
printf(”\n최소 비용 신장 트리 결과(인접 배열)\n”);
convert_edge_to_array(result, F, n, m); // n-1개의 간선이 F에 포함되므로
fclose(file);
return 0;
}
void print_edgy(Edge E[], int n) // 간선 집합 출력
{
int i;
for(i = 0; i < n; i++) {
if(E[i].cost != 0)
printf(”v%d -> v%d, 가중치 = %d\n”, E[i].vertex[0]+1, E[i].vertex[1]+1, E[i].cost);
}
}
int** make_array(int n) // N x N 배열 만들기
{
int i, j;
int** array; // N x N 동적 배열을 할당받을 더블 포인터 변수를 선언
n–;
array = (int**)malloc(sizeof(int*)*n);
for(i = 0; i <= n; i++) {
array[i] = (int*)malloc(sizeof(int)*n);
}
for (i = 0; i <= n; i++) {
for (j = 0; j <= n; j++) {
array[i][j] = 0;
}
}
return array; // array의 주소값을 반환해준다
}
void read_array(FILE *file, int *G[], int n) // 파일에서 배열 값을 읽어 배열 G에 저장
{
int i, j;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
fscanf(file, “%d”, &G[i][j]);
}
}
}
void convert_array_to_edge(int *G[], Edge E[], int n)// 배열 정보를 간선 정보로 변환
{
int i, j, num = 0;
for(i = 0; i < n; i++) { // 배열의 정보를 간선 구조체에 삽입
for(j = i; j < n; j++) {
if( G[i][j] != 0 && G[i][j] != 99 ) { // 가중치의 값이 1에서 99 사이로 존재할때
E[num].vertex[0] = i; // i를 배열 첫번째 요소에 넣는다(간선의 시작점)
E[num].vertex[1] = j; // j를 배열 두번째 요소에 넣는다(간선의 끝점)
E[num].cost = G[i][j]; // 가중치를 넣는다
num++; // E의 다음배열을 증가시켜준다
}
}
}
}
void convert_edge_to_array(int* G[], Edge F[], int n, int m)
{
int i, j;
int sum = 0;
int num = 0;
while (num < m) {
for (i = 0; i < n; i++) {
if (F[num].vertex[0] == i) {
for (j = 0; j < n; j++) {
if (F[num].vertex[1] == j) {
G[j][i] = F[num].cost;
G[i][j] = F[num].cost;
sum += F[num].cost;
continue;
}
}
}
}
num++;
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf(”%2d “, G[i][j]);
}
printf(”\n”);
}
printf(”총비용 : %d\n”, sum);
}
void kruskal(int n, int m, Edge E[], Edge F[]) // 크루스칼 알고리즘
{
int start_vertex, end_vertax, i, current_edge;
int p, q; // 서로소 체크를 위한 집합을 가리키는 변수
int num = 0;
int* U = (int*)malloc(sizeof(int)*(n-1)); // 집합 선언
Edge edge_temp;
printf(”\n정렬 전 Edge E\n”);
print_edgy(E, m);
bubble_sort(E, m); // E에 속한 m개의 간선을 가중치가 작은 것부터 차례로 정렬
printf(”\n정렬 후 Edge E\n”);
print_edgy(E, m);
for (i = 0; i < n; i++) {// 집합 Initialize
U[i] = i;
}
current_edge = 0;
while(num < n-1) { // 간선의 수가 n-1보다 작을 동안
edge_temp = E[current_edge]; // 아직 고려하지 않은 간선 중 가중치가 최소인 간선
start_vertex = E[current_edge].vertex[0]; // i, j = e에 연결된 정점
end_vertax = E[current_edge].vertex[1];
p = find_set(start_vertex, U); // start_vertax가 속하는 집합을 p에 저장
q = find_set(end_vertax, U); // end_vertax가 속하는 집합을 q에 저장
if(p != q ) { // p와 q 가 서로 속한 집합이 다르다면
find_merge(p, q, U); // p, q가 속한 집합을 합침
F[num] = edge_temp; // edge_temp를 F에 추가
num++;
}
current_edge++;
}
}
int find_set(int i, int U[]) // i가 집합 U의 어느 집합에 속하나?
{
int j;
j = i;
while(U[j] != j) {
j = U[j];
}
return j;
}
void find_merge(int p, int q, int U[]) // p, q를 집합 U에 합칩
{
if (p < q) { // p는 합병된 집합을 가리키는 포인터
U[q] = p; // q는 더 이상 집합을 가리키는 포인터가 아님
}
else {
U[p] = q;
}
}
void bubble_sort(Edge E[], int m) // E 엣지 집합의 가중치를 정렬하기 위한 함수
{
int i, Sorted = 0;
Edge tmp;
while( !S
orted ) {// 정렬이 완료되지 않았으면
Sorted = 1;
for(i = 1; i < m; i++) {
if( E[i-1].cost > E[i].cost ) {
tmp = E[i-1];
E[i-1] = E[i];
E[i] = tmp;
Sorted = 0;
}
}
}
}
[/spoiler]
하하 ㅋㅋ
이녀석들 입대 한다고 난리치던게 엊그제 같은데
벌써 휴가까지 나오네 ㅋㅋ 요즘에는 100일 휴가 없어져서
좀 늦게 나온 감이 없지 않아 있지만……
그래도 휴가 나온게 어디임?! ㅋ
다음달이면 일병 단다던데.. 어휴 언제 병장 달고
언제 제대 하려나?ㅋㅋ 불쌍한 녀석들~~~~
그래도 오랜만에 봐서 재미도 있고 ㅋ
갈수록 줄어가는 내 통장 잔고 어쩔…=_=;; 허허허허…
한번에 같이 좀 나와라;; 따로 나오지 말고;;; 형 힘들다;;
[spoiler]
[/spoiler]