bluish wolf

//Circular Linked List
//요셉의 문제

#include<stdio.h>
#include<stdlib.h>

typedef struct _node
{
    int data;
    struct _node* next;
}node;
node* head;

void step_del(int x);
void init_node(int x);

void main()
{
    int n, step;

    printf("사람의 수와 간격을 입력해 주세요 : ");
    scanf("%d %d", &n, &step);
    fflush(stdin);
   
    init_node(n);
    step_del(step);
}

void init_node(int x)
{
    int i;
    node* temp = (node*)malloc(sizeof(node));
    head = temp;
    temp->data = 1;
   
    for(i=2 ; i<=x ; i++)
    {
        temp->next = (node*)malloc(sizeof(node));
        temp = temp->next;
        temp->data = i;
    }
    temp->next = head;
}

void step_del(int x)
{
    int i;
    node *a, *del;
    a = head;
    while(a != a->next)
    {
        for(i=0; i<x-1 ;i++)
            a = a->next;
        printf("%5d", a->next->data);
        del = a->next;
        a->next = a->next->next;
        free(del);
    }
    printf("%5d\n",a->data);
    free(a);
}

typedef struct _node
{
    int data;
    struct _node* next;
}node;
node *head, *tail;

 void node_print(void);
void init_node(void);
void insert_node(int);
node* find_node(int);
void insert_after(int, node*);
void del_next_node(node*);
void insert_before(int, node*);
void del_node(int);
void del_all(void);

 void main()
{
    init_node();
    insert_node(1);
    insert_node(10);
    insert_node(5);
    insert_node(8);
    insert_node(3);
    insert_node(8);
    insert_node(7);

    puts("Inital Linked list is");
    node_print();

    printf("Finding 4 is %s\n", find_node(4)!=tail ? "successful" : "unsuccessful");
    printf("Finding 5 is %s\n", find_node(5)!=tail ? "successful" : "unsuccessful");
   
    puts("Inserting 9 after 5");
    insert_after(9, find_node(5));
    node_print();

    puts("Deleting next last node");
    del_next_node(find_node(10));
    node_print();

    puts("Deleting next 3");
    del_next_node(find_node(3));
    node_print();

    puts("Inserting 2 before 3");
    insert_before(2, find_node(3));
    node_print();

    puts("Deleting node 2");
    del_node(2);
    node_print();

    puts("Deleting node 1");
    del_node(1);
    node_print();

    puts("Deleting all node");
    del_all();
    node_print();

}

 //노드전체 삭제
void del_all(void)
{
    node *a, *temp;
    a = head->next;
    while(a != tail)
    {
        temp = a;
        a = a->next;
        free(temp);
    }
    head->next=tail;
}

 //선택한 노드 삭제
void del_node(int x)
{
    node *a, *b;
    a = head;
    b = head->next;
    while(b->data != x && b != tail)
    {
        a = a->next;
        b = b->next;
    }
    if(b != tail)
    {
        a->next = b->next;
        free(b);
    }
} 

//찾는 숫자 이전에 노드 삽입
void insert_before(int x, node* y)
{
    node *a, *b;
    node* insert = (node*)malloc(sizeof(node));
    a = head;
    b = a->next;
    while(b->data != y->data && b != tail)
    {
        a = a->next;
        b = b->next;
    }
    if(b != tail)
    {
        insert->data = x;
        insert->next = b;
        a->next = insert;
    }
}
   
//찾는 숫자 다음에 노드 삭제
void del_next_node(node* x)
{
    node* temp;
    if(x != tail)
    {
        temp = x->next;
        x->next = x->next->next;
        free(temp);
    }
}

 //찾는 숫자다음에 노드 삽입
void insert_after(int x, node* y)
{
    node* insert = (node*)malloc(sizeof(node));
    insert->data = x;
    insert->next = y->next;
    y->next = insert;
}

 //노드 찾기
node* find_node(int x)
{
    node* a;
    a = head->next;
    while(a->data != x && a!=tail)
        a = a->next;
    return a;
}

 //노드 출력하기
void node_print(void)
{
    node* a;
    a = head->next;
    while(a != tail)
    {
        printf("%-7d",a->data);
        a = a->next;
    }
    puts("");
}

 //head, tail 노드 초기화
void init_node(void)
{
    head = (node*)malloc(sizeof(node));
    tail = (node*)malloc(sizeof(node));
    head->next = tail;
    tail->next = tail;
}

 //노드 추가
void insert_node(int x)
{
    node *a, *b;
    node* insert = (node*)malloc(sizeof(node));
    a = head;
    b = a->next;
    while(b->data <= x && b != tail)
    {
        a = a->next;
        b = b->next;
    }  
    insert->data = x;
    a->next = insert;
    insert->next = b;
}

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<windows.h> 

#define MAX_SIZE 19
#define ROBOT1   38   // & 

#define UP      1  
#define RIGHT   2
#define DOWN    4
#define LEFT    8 

int get_shape(int, int);
void draw_maze(void);
void gotoxy(int , int);
void right_hand(int, int, int);
int wall_ahead(int, int, int);
void right(int*);
void left(int*);
int still_in_maze(int, int);
void foward(int*, int*, int);
void shortest_path(void);
void del_path(int, int);
void record(int, int);

int maze[MAX_SIZE][MAX_SIZE]={
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1},
        {1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1},
        {1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1},
        {1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1},
        {1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1},
        {1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1},
        {1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
        {1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
        {1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
        {1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
        {1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1},
        {1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1},
        {1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1},
        {1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1},
        {1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1},
        {1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1},
        {1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

int* save;  // 이동경로 저장

void main()
{
    save = (int*)malloc(MAX_SIZE * MAX_SIZE);  // 배열 생성
    if(save==NULL)
    {
        printf("Memory allocation error !!!!\n");
        exit(1);
    }
    draw_maze();  // 미로 그리는 함수 호출
    gotoxy(40, 5);
    cputs("Simulation of Micro Mouse");
    gotoxy(40, 10);
    cputs("\t Press any key to start...");
    getche();

    right_hand(MAX_SIZE-2, MAX_SIZE-1, LEFT);  // 미로 이동 실행   
    gotoxy(40, 10);
    cputs("\t Press any key to see shortest path...");
    getche();

    shortest_path();  // 최단거리 함수 호출
    gotoxy(40, 20);
} 

// 최단거리 함수 출력
void shortest_path(void)
{
    int init_x, init_y;
    int i, j;  
    for(i=0 ; save[i]>-1 ; i++)
    {
        init_x = save[i++];
        init_y = save[i];
        for(j=i+1 ; save[j]>-1 ; j++)
        {
            if(save[j++] == init_x && save[j] == init_y)
                del_path(i-1, j-1);
        }
    }

    // 출력
    i=0;
    while(save[i]>-1)
    {
        gotoxy(save[i+1]+1, save[i]+1);
        putchar(ROBOT1);
        Sleep(100);
        gotoxy(save[i+1]+1, save[i]+1);
        putchar(' ');
        i+=2;
    }
} 

// 필요없는 경로 삭제 함수
void del_path(int x, int y)
{
    int i;
    for(i=0; save[y+i]>-1 ; i++)
        save[x+i] = save[y+i];
    save[x+i] = -1; // 배열의 끝을 선언
}

 // 이동경로 저장 함수
void record(int x, int y)
{
    static int i = 0;
    save[i++] = x;
    save[i++] = y;
} 

// 미로 이동 함수
void right_hand(int x, int y, int dir)
{
    gotoxy(y + 1, x + 1);
    putchar(ROBOT1);
    Sleep(100);
    record(x, y);

    foward(&x, &y, dir);
    while(still_in_maze(x, y))
    {
        right(&dir);
        while(wall_ahead(x, y, dir)) // 앞에 벽이 1이 없을때 까지
        {          
            left(&dir);
        }
        foward(&x, &y, dir);
    }
    record(-1, -1); // 배열 마지막을 선언
} 

//다음 경로값 1 확인 함수
int wall_ahead(int x, int y, int dir)
{
    switch(dir)
    {
        case UP     : --x; break;
        case RIGHT  : ++y; break;
        case DOWN   : ++x; break;
        case LEFT   : --y; break;
    }
    return maze[x][y];
} 

// 오른쪽으로 회전
void right(int* dir)
{
    *dir = *dir << 1;
    if((*dir) > LEFT)
        *dir = UP;
}

//왼쪽으로 회전
void left(int* dir)
{
    *dir = *dir >> 1;
    if((*dir) < UP)
        *dir = LEFT;
}

//미로 안에 있는지 판별 함수
int still_in_maze(int x, int y)
{
    if(x>0 && x< MAX_SIZE-1 && y>0 && y<MAX_SIZE-1)
        return 1;
    else
        return 0;
}

//방향에 따라 전진 하는 함수
void foward(int* x, int* y, int dir)
{
    gotoxy((*y)+1, (*x)+1);
    putchar(' ');

    switch(dir)
    {
        case UP     : --(*x); break;
        case RIGHT  : ++(*y); break;
        case DOWN   : ++(*x); break;
        case LEFT   : --(*y); break;
    }
    gotoxy((*y)+1, (*x)+1);
    putchar(ROBOT1);
    Sleep(100);
    record(*x, *y);
} 

// 미로글 그리는 함수
void draw_maze(void)
{
    int i, j;

    for(i=0 ; i<MAX_SIZE ; i++)
        for(j=0 ; j<MAX_SIZE ; j++)
        {
            gotoxy(j+1 , i+1);
            putchar(get_shape(i ,j));
        }
}

 //미로의 값에 따라 형태를 리턴하는 함수
int get_shape(int x, int y)
{
    static int shape[]= { 32, 5, 6, 3, 5, 5, 1, 25, 6, 4, 6, 21, 2, 23, 22, 16};
    int s=0;

    if(maze[x][y])
    {
        if(x>0 && maze[x-1][y])
            s = s | UP;
        if(x<MAX_SIZE-1 && maze[x+1][y])
            s = s | DOWN;
        if(y>0 && maze[x][y-1])
            s = s | LEFT;
        if(y<MAX_SIZE-1 && maze[x][y+1])
            s = s | RIGHT;
    }

    return shape[s];
}

 //VC 6.0 에서 사용할수 없는 gotoxy()함수 구현
void gotoxy(int x, int y)
{
    COORD Pos = {x-1,y-1};
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),Pos);
}

//atof() 만들기
//입력은 char str[MAX]; scanf("%s",str);
//출력은 printf("%d",num);
//1) str[0]가 음수인지 check
//2) 소수점 이상, 이하 분리 해서 처리
//1-2)결과 종합해서 출력

#include<stdio.h>
#include<string.h>
#define MAX 100

void main()
{
    char str[MAX];
    double num1=0, num2=0;
    int i=0, flag=0;

    printf("숫자형의 문자열을 입력하시오 : ");
    scanf("%s",str);
    fflush(stdin);

    if(str[0] == '-')
    {
        i++;
        flag++;
    }

    for( ; str[i]!='.' ; i++)
    {
        if(i != flag)
            num1*=10;
        num1 += (str[i] - '0');
    }
    for(i=strlen(str)-1 ; str[i]!='.' ; i--)
    {
        num2 += (str[i] - '0');
        num2 *= 0.1;
    }
    printf("==== Result :%f ====\n", !flag ? (num1 + num2) : -(num1 + num2));
}

 

모토로라 68010 마이크로프로세서와 함께 사용되었던 68451 MMU. 예전에는 MMU가 이와 같이 따로 분리된 하드웨어였지만 최근의 아키텍처에서는 프로세서와 같은 칩에 회로로 삽입된다.

메모리 관리 장치(Memory Management Unit, 줄여서 MMU)는 CPU가 메모리에 접근하는 것을 관리하는 컴퓨터 하드웨어 부품이다. 가상 메모리 주소를 실제 메모리 주소로 변환하며, 메모리 보호, 캐시 관리, 버스 중재 등의 역할을 담당하며 간단한 8비트 아키텍처에서는 뱅크 스위칭을 담당하기도 한다.

최신 아키텍처에서 MMU는 가상 주소공간을 2^N비트 크기의 페이지들로 나눈다. 그 가운데 일부 페이지는 실제 메모리 주소의 한 페이지에 대응되는데, 대부분의 경우 가상 주소공간은 실제 메모리의 주소공간보다 크기 때문에 모든 페이지가 실제 메모리에 대응되는 것은 아니다. CPU가 가상 메모리 주소를 MMU에 넘겨주면 MMU는 그 주소를 받아 뒤쪽의 N비트는 바꾸지 않고 앞쪽의 나머지 비트를 그에 해당하는 실제 메모리 주소로 바꾼다. 이때 가상 메모리 주소와 실제 메모리 주소 사이의 변환을 위해 MMU는 변환 참조 버퍼(Translation Lookaside Buffer, TLB)라는 고속의 보조기억장치를 참조한다. 이 보조기억장치에 원하는 변환 정보가 없을 때는 더 느린 다른 방법으로 페이지 변환 정보를 얻어오는데, 이 페이지 변환 정보가 담겨 있는 자료구조를 페이지 테이블(Page Table)이라 한다. 페이지 테이블의 동작은 아키텍처와 운영체제에 따라 서로 다르다.

TLB나 PTE는 또한 그 메모리 주소가 캐시에 저장되었는지, 페이지가 쓰여졌는지(dirty bit), 프로세스에게 메모리에 접근할 권한이 있는지 등의 정보를 저장하기도 한다.

TLB나 페이지 테이블이 실제 메모리 주소를 가져오지 못하는 경우가 있는데, 이를 페이지 실패(page fault)라 한다. 대부분의 경우 페이지 실패는 가상 주소공간의 페이지가 실제 메모리에 없기 때문에 발생한다. 이 경우 운영체제가 그 처리를 담당하는데, 비어 있는 메모리 공간에 페이지를 할당하거나, 비어 있는 메모리 공간이 없을 경우 실제 메모리의 한 페이지를 빼내 하드 디스크에 저장하고 (이를 페이징이라 한다) 그 자리에 요구 받은 페이지를 할당한다.

페이지 실패는 메모리 보호의 목적으로도 사용될 수 있다. 어떤 프로그램이 접근이 금지된 주소공간에 접근하려 하면 MMU는 페이지 실패를 일으킨다. 이 때 운영체제는 금지된 공간에 접근하려 하는 페이지 실패를 처리하지 않고 프로그램을 중지시킴으로써 악의가 있는 프로그램이나 버그가 있는 프로그램이 중요한 데이터를 읽거나 쓰는 것을 막을 수 있다.

--------------------------------------------------------------------------------------------------

MMU는 가상 메모리 시스템을 관리하는 하드웨어 요소이다. MMU는 설계에 따라 별도의 칩으로 되어 있는 경우도 있지만, 일반적으로 CPU의 일부가 된다. MMU는 가상 메모리를 실제 메모리로 사상시키는데 필요한 표를 유지할 수 있도록 소량의 메모리를 가진다.

데이터를 읽기 위한 모든 요청들은, 그 데이터를 램에서 즉시 읽을 수 있는지 또는 하드디스크 등으로부터 가져와야 하는지를 결정하기 위해 일단 MMU로 보내어진다. 만약 그 데이터가 메모리에 있지 않다면 MMU는 페이지 부재에 관한 인터럽트를 발생시킨다.

MMU는 또한 메모리의 단편화 문제를 해결하기도 한다.       [출처] MMU (memory management unit)

//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
//  [ 해 쉬 (Hash) ]
//
//    1. 해쉬
//    2. 해쉬의 전략
//    3. 해쉬 함수의 작성
//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓

/*
//─────────────────────────────────
   1. 해쉬
//─────────────────────────────────
 
  자료수에 상관없이 상수의 검색 길이를 가진다.
  내부검색(메모리)과 외부검색(디스크)을 빠른 속도로 검색해주는 알고리즘
//─────────────────────────────────
   2. 해쉬의 전략
//─────────────────────────────────

  1) 해쉬 용어
     ex) 우체국에서 편지를 다루는 방법

 - 편지 : 주소, 우편번호
   우체국 --> 우편번호에 따라 통(bucket)에 정리

    - key    : 주소      // 데이터
   hash value  : 우편번호     // 실제로 저장되는 장소
   hash table  : 편지를 넣는 통들의 집합
   bucket      : 각 통들
   slot        : 통들에 들어가는 편지의 갯수

      hash function : key(주소)를 hash value(우편번호)로 바꾸어 주는
                   함수
     - 해쉬 검색법의 성능 좌우
       key 값을 해쉬 함수에 넣어 얻어진 hash value의 위치에
      레코드를 저장하는 방법

          => 이상적인 경우 단 한번의 계산으로 삽입과 삭제, 그리고
       검색이 가능하다.

      ex) 간단한 해쉬 함수 구현
       - key     : 세 글자의 문자
       - hash value : 세 글자 중의 첫 글자

 // 소스 작성 ------------------------------------------------
 #define TABLE_SIZE 256
 char hash_table[TABLE_SIZE][3]

 // 해쉬 함수
 int hash1(char str[])
 {
  int h;
  h = str[0];
  return h;
 }
 key   : 저장하고자 하는 값 char str[](3개의 문자)
 hash Value  : 3개의 문자 첫번째 문자
 hash table  : hash_table --> 편지를 넣는 통들의 집합, 크기?? 256
 bucket  : hash_table[0].... 각 통들...
 slot  : 통들에 들어가는 편지의 갯수, 자료의 갯수
 hash function : hash1

 ==> 3글자의 키는 hash_table[hash1(key)]에 저장된다.

 만약)
 ABC, BCA, CBA : 모두 다른 해쉬값을 갖는다... 서로 다른 곳에 저장된다.

 ABC, ACD, AXY : 같은 곳에 저장된다.(충돌)

 --> 이 충돌해결 방법 : 선형탐사법, 이중 해쉬법, 연결법등으로 세분화된다.
  
 ---------------------------------------------------------------

//─────────────────────────────────
   3. 해쉬 함수의 작성
//─────────────────────────────────

  (1) 가장 좋은 함수는?
   - 평균적인 입력에 대해 해쉬값 분포를 고르게 작성...
   - 특정 해쉬값이 많이 나올 경우 : 부가적인 작업이 필요해진다.

   => 따라서 해쉬 함수는 고른 분포여야 하는데 입력 자료에 따라
   적절한 해쉬 함수도 다르게 된다.(그때 그때...)

     ex)
     ABC, ACD, AXY등의 문자가 대부분의 경우일 경우?
  첫번째 문자가 아니라 2번째 문자를 hash값으로 하는 등 방법적인 부분 고려...
 

  해쉬 함수가 사용할 수 있는 형태
     나머지, 제곱, 쪼개기, 합치기

  1) 가장 많이 사용하는 해쉬 함수의 형태는 나머지 연산
    - % 연산자로 쉽게 할 수 있으며 속도가 빠르다.
    - 키값을 수치화시킨 후에 M으로 나머지 연산을 하면 해쉬값은
      0 ~ (M-1)의 분표를 갖는다.

   => M : 소수를 사용 or
          20이하의 인수를 가지지 않는 수
    => M이 인수 2를 가진다면(2의 배수라면)
       //답변)두곳의 버킷에 모든 수가 들어간다.

  2) 그 다음 형태는 거듭 제곱
     - 키값을 제곱 또는 세제곱하면 구성하는 비트의 형태가 확연히
    달라지게 된다.

     3) 키를 쪼개고 합치는 방법
 
   ex) 만약 입력 자료들의 첫 글자가 한쪽에 편중되어 있다면
       해쉬값 역시 편중될 우려가 있다.
       -> 거듭 제곱, 쪼개어 합치기, 너머지 이용등의 방법들을 사용

  int hash2(char str[])
  {
  int h;
  h = str[0]^((str[1]*str[1] + str[2]))%TABLE_SIZE);
  return h;
  }

     - 고른 분포
  - 해쉬 테이블의 크기를 넘어서는 안된다.
  - 해쉬 테이블 크기 또한 해쉬 함수의 범위에 합당하게 설정
  ==> 즉 상황에 따라 해쉬 함수는 다르게 된다.
 
*/

//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
//  [ 해 쉬 (Hash) ]
//
//    4. 충돌의 해결 방법
//       4.1 선형 탐사법(Linear Probing)
//           4.1.1 선형 탐사법(Linear Probing) 구현
//           4.1.2 선형 탐사법의 개선
//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓

/*

//─────────────────────────────────
   4. 충돌의 해결 방법
//─────────────────────────────────
   해쉬 테이블의 한곳에 여러개의 key들이 들어 갈 경우

//─────────────────────────────────
   4.1 선형 탐사법(Linear Probing)
//─────────────────────────────────

     정적인 해쉬 검색법 규칙
  정적인 해쉬 테이블 사용 :
  배열과 같이 소스 코드상 크기가 정해져 있슴.
  입력자료의 수는 해쉬 테이블의 버킷을 초과 할 수 없슴

     사용 시점
     --> 자료의 변동이 별로 없는 경우 적합, 구현 간단    
  --> 자료 검색은 해쉬 함수에 의해 구해진 해쉬값으로 해쉬 테이블을 참조
  --> 충돌시 가장 널리 사용하는 방법임
    

    선형 탐사법
 1) 현재 삽입하려는 키의 해쉬값에 의한 버킷이 이미 다른 레코드가
       들어있다면 단순히 다음의 버킷에 새로운 레코드를 기입하는 방법
 2) 만일 다음 버킷에도 다른 레코드가 들어있다면 그 다음 버킷을
    찾고 하는 과정 반복

    < 삽입 알고리즘 >
 1. 삽입할 레코드의 해쉬값을 해쉬 함수를 이용하여 구하여 try에 저장
 2. while(해쉬 테이블[try]가 비어있지 않을 동안...)
    2.1 try = (try+1) % TABLE_SIZE
 3. 해쉬 테이블[try]에 레코드 기입

    [ex] 해쉬 함수 작성
     레코드는 단순한 정수형
  해쉬 테이블의 크기 10
  해쉬 함수는 키값을 TABLE_SIZE로 나눈 나머지를 리턴

 #define TABLE_SIZE 10
 int hash_func(int key)
 {
  int h;
  h = key % TABLE_SIZE;
  return h;
 }

    10의 크기를 해쉬 테이블에 A C E O F P I K U 차례로 삽입
 
 1. A(아스키 : 65)%10 = 5  => 5번 버킷에 A를 기입
 2. C(아스키 : 67)%10 = 7  => 7번 버킷에 B를 기입
 3. E(아스키 : 69)%10 = 9  => 9번 버킷에 E를 기입
 4. O(아스키 : 79)%10 = 9  => 9번 버킷에 O를 기입 ??

 5. F(아스키 : 80)%10 = 0  => 0번 버킷에 F를 기입 ??

 6. P(아스키 : 90)%10 = 0  => 0번 버킷에 P를 기입 ??

 7. I--> 3, K-->6, U--> 4

 <검색 알고리즘>
 1. 검색할 키의 해쉬값을 구하여 try에 저장
 2. while(해쉬 테이블[try]가비었지 않을 동안)
     해쉬 테이블[try]가 찾고자 하는 레코드이면 리턴
  아니면 try = (try+1)%TABLE_SIZE
 3. 여기까지 오면 찾지 못한 것이므로 실패

    [ 위의 저장 예에서의 검색 ]

    1. A나 C나 E를 찾는 것은 한번의 해쉬값으로 충분
 2. O, F, P를 찾는 것은 선형 탐사 필요
    
 [ 용어 ]
    cluster(덩어리)
   해쉬 테이블에서 연속된 공간을 차지하는 것
   덩어리가 크느냐 작느냐에 따라 삽입과 검색을 위해 선형 탐사를
   하는 횟수가 결정됨
 Loading density(적재밀도)
   전체자료수에다 전체 버킷수를 나눈 수
   적재 밀도는 1보다 작다.
   적재 밀도가 커질수록 큰 덩어리가 생길 확률이 높다.

    ex) D까지 삽입한 상태에서 U를 삽입할 경우
     최고 9번의 선형 탐사 후에야 삽입할 곳을 찾게 된다.

 <삭제 알고리즘>

    --> 만약 10번 상태에서 p를 삭제하여 빈 곳으로 만들면
     U를 찾을 수 있을까?
  U를 찾기 위해 선형 탐사를 하던 도중 P가 있던 곳이
  빈 곳이 되므로 탐사를 멈추게 된다.

 --> 삭제 표시와 빈 곳이라는 표시를 따로 해줄 필요 존재함
  검색시 삭제된 버킷이 존재해도 계속 검색
  삽입시 삭제된 버킷에 삽입 가능...
   

    [ 선형 탐사법의 단점 ]
 1. 동적 자료의 검색시 매우 취약(최초 테이블의 크기를 크게 잡아야 함)
    - 적재 밀도(Loading density)가 매우 작아져 효율적이다.

 2. 해쉬 테이블이 꽉 찬상태에서 존재 안하는 키를 검색시 ??
    - 무한 루프
   해결) 시작위치(최초 해쉬값) 기록 후 try값이 원래의 값이 되었을 경우 종료

 3. 해쉬 테이블이 꽉찬 상태면 최대 N의 검색길이를 갖는다.
    - 해결방법???
      120% 정도 크게 잡아주는 것이 효율적...

//─────────────────────────────────
  4.1.1 선형 탐사법(Linear Probing) 구현
//─────────────────────────────────
*/
// 구현 : 초기화, 삽입, 삭제, 검색 함수

//─────────────────────────────────
//  1) 빈 곳과 삭제된 곳을 표시할 상수 정의
//─────────────────────────────────
#define EMPTY  -1  // 빈곳을 표시
#define DELETED  -2  // 삭제된 곳을 표시
 

//─────────────────────────────────
//  2) 선형 탐사를 하기 위해서 해쉬 테이블 초기화
//─────────────────────────────────
// 테이블을 모드 EMPTY로 채운다.

// 인자값 : 테이블... 채워진 갯수
int HlpInit(int a[], int *np)
{
 int i;
 for (i=0; i < TABLE_SIZE; i++)
  a[i] = EMPTY;
 *np = 0;
 return 1;
}

//─────────────────────────────────
//  3) 해쉬 함수 구현
//─────────────────────────────────
#define TABLE_SIZE 10
int Hash_Func(int key)
{
 int h;
 h = key % TABLE_SIZE;
 return h;
}

//─────────────────────────────────
//  4) 해쉬 테이블에 자료 삽입
//─────────────────────────────────
// 초기의 해쉬값... try1와 try2 저장
// try2 : 해쉬 테이블이 꽉 찼을 경우 무한 루프에 빠지는 것을 방지...
// - try1 가 해쉬 테이블을 한바퀴 돌고 제자리로 돌아온 것을 확인하기 위해
//  마련한 변수

// [ 자료 삽입 장소는???]
// - EMPTY로 표시된 곳... DELETED로 표시된 곳

// 인자값 : 저장할 키, 테이블, 실제 저장 갯수
int Hlp_Insert(int key, int a[], int *np)
{
 int try1, try2;

 // 초기 무한 루프 방지...
 try1 = try2 = HashFunc(key);

 // 빈 곳이나 삭제된 곳을 찾음
 while ( a[try1] != EMPTY || a[try1] != DELETED) {
  try1 = (try1 + 1) % TABLE_SIZE;  // 선형 탐사
  if ( try1 == try2)     // 꽉 차 있는 상태
   return -1;
 }
 // 찾은 곳에 key를 수록
 a[try1] = key;
 // 자료수 증가
 (*np)++;
 // 삽입한 곳 리턴
 return try1;
}

//─────────────────────────────────
//  5) 해쉬 테이블에서 자료 삭제
//─────────────────────────────────
// 자료 삭제 후에 삭제된 곳이라고 표시
int Hlp_Delete(int key, int a[], int *np)
{
 int try1;
 // 자료수가 0이면 리턴
 if ( *np == 0 )
  return -1;
 // 삭제할 키를 찾음
 if (( try1 = Hlp_Search(key, a, np)) < 0 )
  return -1;
 // 찾았을 경우
 a[try1] = DELETED;
 // 자료수 감소
 (*np)--;
}

//─────────────────────────────────
//  6) 해쉬 테이블 검색 함수(핵심 함수)
//─────────────────────────────────
// 빈 곳을 만나면 실패를 리턴
// 키를 찾으면 그 위치를 리턴
// 빈 곳은 없지만 찾는 키도 없는 경우는 실패를 리턴
int Hlp_Search(int key, int a[], int *np)
{
 int try1, try2;
 try1 = try2 = Hash_Func(key);

 while ( a[try1] != EMPTY ) {
  // 키를 찾았으면 성공
  if ( a[try1] == key )
   return try1;
  // 선형 검색
  try1 = (try1 + 1) % TABLE_SIZE;

  // 찾고자 하는 키가 없음
  if ( try1 == try2 )
   return -1;
 }
 return -1;
}

//  ==> 선행 탐사법은 기본적으로 배열을 이용 => 프로그램이 쉽다.
//      해쉬 테이블을 충분히 크게 잡으면 => 검색 효율이 좋다.(자료수에 관계없이 상수 검색 길이)
//     해쉬 테이블을 작게 잡으면 => 평균 검색 길이가 길어진다.
//              적재 밀도가 높아짐 : 큰 덩어리가 생김..
//

/*
//─────────────────────────────────
    4.1.2 선형 탐사법의 개선
//─────────────────────────────────

   한 버킷에 들어올 값을 인접한 곳에 두기 때문에 큰 덩어리가 생길 확율이
   많다.         

   앞의 예는 해쉬 테이블의 크기가 10이라고 가정하고,
     충돌이 일어난 경우 아래와 같이 작성하여 다음 버킷을 찾음

   try = (try+1) % TABLE_SIZE;

   // 어떻게 하면 좋을까??
   // [ 답변 ]
   꼭 1을 더하라는 법은 없다.
   try = (try + i) % TABLE_SIZE;
   i를 적절히 선택
   만약 3이라면??
   ==> 덩어리가 적어진다.
*/

〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
//  [ 해 쉬 (Hash) ]
//
//    4. 충돌의 해결 방법
//       4.3 연결법(Separate chaining)
//           4.3.1 연결법(Separate chaining) 구현
//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓

/*
//─────────────────────────────────
   4. 충돌의 해결 방법
//─────────────────────────────────
   해쉬 테이블의 한곳에 여러개의 key들이 들어 갈 경우

//─────────────────────────────────
   4.3 연결법(Separate chaining)
//─────────────────────────────────

   연결법(동적인 해쉬법)
    - 동적 할당을 통하여 해쉬 테이블의 크기보다는 큰 자료를 저장할 수 있다.
 - 기본적인 해쉬 테이블과 단순 연결리스트를 이용하여 동적인 자료를 빠르게 검색
 - 매우 큰 자료 집합에 대해서 유용

   ( ex ) 양의 정수 자료 검색

   해쉬 테이블의 크기 TABLE_SIZE 10
   배열로 10 크기의 해쉬 테이블 생성
     - 단순히 레코드를 저장하는 것이 아니라 버킷에 저장될 레코드를
    가리킬 포인터를 가지고 있어야 한다.

   // 노드 구성
   typedef struct _node
   {
  int key;
  struct _node *next;
   }node;

   -> 이 노드 구조를 TABLE_SIZE크기의 배열로 잡고
      내용을 초기화(next = NULL)

   -> 이후 모든 삽입과 삭제, 검색은 연결 리스트에서 순차 검색을
      하던 것과 매우 유사하다.
  
   -> 연결법은 간단히 해쉬법과 연결 리스트의 순차 검색을 혼용한 방법

   ex) A C E O F P I K D U 자료 연속 삽입

  < 연결법에서의 삽입 알고리즘 >
  1. 키에 해당하는 해쉬값을 해쉬 함수를 이용하여 찾아서 try에 저장
  2. 삽입할 레코드를 동적 저장
  3. 해쉬 테이블[try]의 연결 리스트의 앞에 레코드를 끼워 넣는다.
 
  ------------ 
  버 킷
  ------------
  0 --> F --> p
  1
  2
  3 --> I
  4
  5 --> A --> k --> U
  6
  7 --> C
  8 --> D
  9 --> E --> O

   < 연결법에서의 검색 알고리즘 >
   1. 찾을 키의 해쉬값을 해쉬 함수를 이용하여 구하고 try에 저장
   2. 해쉬 테이블[try]에 연결된 리스트에서 순차 검색

   < 연결법에서의 삭제 알고리즘 >
   1. 찾을 키의 해쉬값을 해쉬 함수를 이용하여 구하고 try에 저장
   2. 해쉬 테이블[try]에 연결된 리스트에서 삭제할 레코드를 검색
   3. 포인터 조작으로 삭제할 레코드를 연결 리스트에서 제외
   4. 삭제할 레코드를 메모리에서 해제

  => 연결법을 이용할 경우 적재 밀도 1보다 커질 수 있다.
  => 레코드 검색시 시간이 더 걸릴 수도 있다.

  => 동적인 해쉬 방법이기 때문에 융통성이 있고 많은 자료 저장 가능

//─────────────────────────────────
   4.3.1 연결법(Separate chaining) 구현
//─────────────────────────────────
 

// 구현 : 초기화, 삽입, 삭제, 검색 함수
*/

//─────────────────────────────────
//  1) 해쉬 함수 구현
//─────────────────────────────────
#define TABLE_SIZE 10

int Hash_Func(int key)
{
 int h;
 h = key % TABLE_SIZE;
 return h;
}

//─────────────────────────────────
//  2) 선형 탐사를 하기 위해서 해쉬 테이블 초기화
//─────────────────────────────────

// 모든 해쉬 테이블의 next를 NULL로 설정
// 인자 : 테이블, 갯수, 전체 크기
int Hsc_Int( node a[], int *np, int N)
{
 // N은 전체 해쉬 테이블 크기
 int i;
 // NULL 로 초기화
 for (i=0; i < N; i++)
  a[i].next = NULL;
 *np = 0;
 return 1;
}

//─────────────────────────────────
//  3) 자료 삽입 함수 
//─────────────────────────────────
int *Hsc_Insert(int key, node a[], int *np)
{
 int try1;
 node *t;
 // 새로운 노드 할당
 t = (node *)malloc(sizeof(node));

 // 해쉬값을 찾음
 try1 = HashFunc(key);

 // 연결리스트의 선두에 t를 삽입
 t->next = a[try1].next;
 t->key = key;
 a[try1].next = t;

 // 자료수 증가
 (*np)++;
 return 1;
}

//─────────────────────────────────
//  4) 자료 삭제 함수 
//─────────────────────────────────
node *HscDelete(int key, node a[], int *np)
{
 // 삭제할 노드의 앞 노드를 가리킴
 node *p;

 // 삭제할 노드
 node *t;

 if ( *np > 0 ) {
  // p와 t의 초기화
  p = &a[Hash_Func(key)];
  t = p->next;

  // 삭제할 노드를 찾음
  while ( t != NULL && t->key != key ) {
   p = t;
   t = t->next;
  }
  // 찾지 못하면 실패
  if ( t == NULL )
   return NULL;
  // 연결리스트에서 t를 제외
  p->next = t->next;
  // t를 메모리에서 해제
  free(t);
  // 자료수 감소
  (*np)--;
  return p;
 }
 return NULL;
}

//─────────────────────────────────
//  5) 자료 검색 함수 
//─────────────────────────────────
node *HscSearch(int key, node a[], int *np)
{
 node *t;
 // 연결리스트 처음
 t = a[HashFunc(key)].next;

 // 순차 검색
 while ( t != NULL && t->key != key)
  t = t->next;
 // t 리턴...
 // 검색을 실패했을 경우 NULL...
 return t;
}

//─────────────────────────────────
//  6) 전체를 삭제하는 함수
//─────────────────────────────────
// 해쉬 테이블의 각 버킷에 연결되어 있는 연결 리스트 순회
// 하면서 메모리 삭제
int HscDeleteAll(node a[], int *np, int N)
{
 node *t, *p;  // p 는 임시 저장용
 int  i;

 for ( i = 0; i < N; i++) {
  // 버킷에 연결된 리스트의 선두
  t = a[i].next;
  while ( t != NULL ) {
   // 삭제를 위해 물려둠
   p = t;
   // t 는 다음 노드를 가리킴
   t = t->next;

   // p를 삭제
   free(p);
  }
 }
 // 자료수 =0
 *np = 0;
 return 1;
}
}

//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
//  [ 해 쉬 (Hash) ]
//
//    5. 해쉬 검색의 분석
//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓

/*
//─────────────────────────────────
   5. 해쉬
//─────────────────────────────────

  1) 종류
     정적 해쉬법 : 선형 탐사법, 이중 해쉬법
    - 해쉬 테이블의 고정적 크기
      동적 자료 처리에 부적절
    - 큰 덩어리가 생길 확률이 연결법에 비해서 높다. (비효율적)
    - 구현 처리는 간단하다.

  동적 해쉬법 : 연결법
    - 연결 리스트와 동적 할당 이용
      고정적인 해쉬 테이블의 크기보다 큰 자료를 저장 검색 가능
    - 해쉬 함수를 잘만 설정하면 큰 덩어리가 생길 확률은 거의 없어
      효율적이다.

  2) 성능
     - 두 이론 모두 O(1)의 성능을 가진다.
     즉 자료수에 관계없이 일정한 검색과 삽입과 삭제 속도를 나타낸다.
  순차 검색, 이진나무검색의 실행시간이 N의 증가 함수인 것에 비하면
  매우 높은 효율이다.
  하지만 해쉬 테이블이 충분히 커야만 O(1)의 성능을 가진다.

  3) 메모리 내부 검색 방법
     - 두 이론 모두 방법이 국한되지 않는다.
    대량의 자료를 검색할 경우 가장 널리 사용되는 검색방법이다.

  4) 해쉬 테이블의 단점
     - 만일 검색과 동시에 정렬된 리스트를 얻어야 한다면 해쉬 검색법은
    재고의 대상이 된다.

*/

...쌕이라고 하면 학생 분들이 매고 다니는 가방 같은것을 말하죠.

...Greedy(욕심쟁이) 알고리즘을 배우신 분들이시라면 다시 한번

...회상에 잠기시는 기회가 되시길 바랍니다.

http://www.koiz.net/algo/greedy-2.htm

Knapsack Problem