언어 자료구조 알고리즘/디딤돌 C언어

66. 구현

언제나휴일 2016. 1. 1. 12:44
반응형

 

실습 시나리오

도메인(Domain) 분석
함수명 결정
함수 원형 결정
테스트 로직 작성
구현


이제 하나 하나 구현해 보세요.
여러분은 먼저 함수를 구현해 본 후에 책을 보세요.
어렵고 귀찮아도 구현 전에 논리를 의사코드(pseudo code)나 플로우 차트UML 등을 이용해서 정리해 보세요.
그리고 구체적으로 구현하는 것이 전체 비용을 줄이는 데 도움을 줄 거예요.
 
a. 범위 내의 정수 합계를 구하는 함수
int GetSumInBoundary(int start, int end)
start에서 end 구간까지의 정수 합계를 구하기 위해 반복문이 필요하겠죠.
여기서는 for 문을 사용할게요.
반복문에서는 현재 어디까지 더했는지 기억하기 위한 루프(반복문) 카운터 변수와 합계를 기억할 변수가 필요해요.
그리고 반복문에서는 루프 카운터를 1씩 증가하면서 합계에 루프 카운터를 더하면 되겠죠.
물론 반복문을 탈출한 후에는 더한 합계를 반환해야죠.
 
함수 GetSumInBoundary(start:구간의 시작, end: 구간의 끝)
    sum 0으로 초기화
    lcnt 0으로 초기화
    lcnt start로 대입(for문의 초기 구문)
    반복: lcnt end보다 작거나 같다면
        sum sum+lcnt를 대입
        lcnt 1 증가(for문의 후처리 구문)
    sum 반환
 
int GetSumInBoundary(int start,int end)
{
    int sum = 0;
    int lcnt = 0;
    for( lcnt = start; lcnt <= end; lcnt++)
    {
        sum += lcnt;
    }
    return sum;
}
 
 
b. 특정 수가 소수(Prime Number)인지 판단하는 함수
int IsPrime (int number)
소수는 1과 자기 자신만을 약수인 자연수죠.
따라서 2부터 전달받은 number보다 작은 수들이 약수인지 확인하는 코드를 반복하면 되겠죠.
반복문에서는 피젯수를 2부터 number보다 작을 때까지 1씩 증가해야 하므로 지역 변수(lcnt)가 필요해요. 
반복문 내부에서는 numberlcnt 변수로 나누었을 때 나머지가 0이면 lcnt가 약수이므로 소수가 아님을 반환하세요.
반복문을 탈출하였다면 약수를 만나지 않았으므로 소수임을 반환하하세요.
여기서는 소수일 때 1, 아닐 때 0을 반환할게요.
 
함수 IsPrime(number:판별할 정수)
    lcnt 2로 초기화(for문의 초기 구문)
    반복: lcntnumber보다 작을동안
        조건: number lcnt로 나누었을 때 나머지가 0이면
            0 반환
    lcnt 1 증가(for문의 후처리 구문)
    1 반환
 
int IsPrime(int number)
{
    int lcnt = 0;
    for( lcnt = 2; lcnt < number; lcnt++)
    {
        if( (number % lcnt) == 0)
        {
            return 0;
        }
    }
    return 1;
} 
 
 
c. 범위 내의 정수중에 소수(Prime Number)의 개수를 구하는 함수
int GetCountIsPrime(int start, int end)
여기에서는 start에서 end 사이의 수가 소수인지 확인하여 소수일 때 카운터를 증가시키는 작업을 수행하면 되겠죠.
특히 특정 수가 소수인지 판별하는 함수는 이미 IsPrime 함수로 작성하였으니 이를 호출하여 구현하세요.
 
함수 GetCountIsPrime(start: 구간의 시작, end: 구간의 끝)
    count 0으로 초기화
    lcntstart로 초기화(for문의 초기 구문)
    반복: lcntnumber보다 작을동안
        조건: lcnt가 소수이면
            count 1 증가
        lcnt 1 증가(for문의 후처리 구문)
    count 반환
 
int GetCountIsPrime(int start, int end)
{
    int lcnt = 0;
    int count = 0;
    for(lcnt = start; lcnt < end; lcnt++)
    {
        if(IsPrime(lcnt))
        {
            count++;
        }
    }
    return count;
}
  
d. n 개의 정수의 합계를 구하는 함수
int GetSum(int *base, int n)
먼저 합계를 기억할 변수(sum)이 필요하겠죠.
그리고 반복문을 수행하면서 현재 어느 원소까지 더했는지 기억할 변수(lcnt)가 필요해요.
lcnt 변수는 0부터 n보다 작을 때까지 1씩 증가시키면 되겠죠.
그리고 반복문에서는 현재 합계에 base에서 상대적 거리 lcnt에 있는 원소의 값을 더하세요.
반복문을 탈출한 후에 합계를 반환합시다.
 
함수 GetSum(base: 더할 정수들이 있는 시작 위치 n:원소 개수)
    sum0으로 초기화
    lcnt0으로 초기화(for문의 초기 구문)
    반복: lcntn보다 작을동안
        현재 sum base에서 상대적 거리 lcnt의 원소를 더함
    lcnt 1 증가(for문의 후처리 구문)
    sum 반환
 
int GetSum(int *base, int n)
{
    int sum = 0;
    int lcnt = 0;
    for(lcnt = 0; lcnt < n; lcnt++)
    {
        sum += base[lcnt];
    }
    return sum;
}
 
e. 두 수를 바꾸는 함수
void Swap(int *p1, int *p2)
C언어는 함수 호출할 때 인자를 값에 의한 전달 방식을 사용하기 때문에 변수의 주소를 전달하여 간접 연산을 이용하여 두 수를 바꿀 수 있다고 얘기했었죠.
여기에서는 별도의 설명을 하지 않을게요.
 
void Swap(int *p1, int *p2)
{
    int temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}
 
f. n 개의 정수에서 제일 큰 정수가 있는 메모리 주소를 구하는 함수
int *GetMaxPos(int *base,int n)
n개의 정수에서 제일 큰 정수를 구하기 위해서는 모든 원소의 값을 비교해야겠죠.
일단 맨 앞의 원소를 제일 큰 정수라고 설정하세요.
여기에서는 위치를 찾는 함수이므로 제일 큰 정수가 있는 인덱스를 기억할 거예요.
그리고 다음 원소부터 반복해서 기억하고 있는 제일 큰 정수와 비교하세요.
만약 더 큰 수를 발견하면 제일 큰 정수가 있는 인덱스를 변경하세요.
반복문을 탈출하였을 때 인덱스가 제일 큰 수가 있겠죠.
따라서 base에서 제일 큰 값이 있는 인덱스를 더한 메모리 주소를 반환해야겠죠.
 
함수 GetMaxPosbase: 정수들이 있는 시작 위치 n:원소 개수)
    max_index 0으로 초기화
    index 1로 초기화 (for문의 초기 구문)
    반복: indexn보다 작을동안
        조건: base[index] base[max_index]보다 크다면
    index 1 증가(for문의 후처리 구문)
    base에서 max_index를 더한 위치를 반환
 
int *GetMaxPos(int *base,int n)
{
    int max_index = 0;
    int index = 0;
    for(index=1 ;index< n; index++)
    {
        if(base[index] > base[max_index])
        {
            max_index = index;
       }
    }
    return base+max_index;
}
 
 
g. n 개의 정수를 크기 순으로 정렬하는 함수(내림 차순으로 정렬, 선택 정렬 알고리즘으로 정렬)
void SelectionSort(int *base, int n)
선택 정렬은 제일 큰(작은) 값의 위치를 찾아 맨 앞의 요소를 찾아 교환한 후에 맨 앞의 요소를 제외한 나머지 구간의 요소를 같은 방법을 반복하여 정렬하는 알고리즘이예요.
 
따라서 정렬할 구간이 남아있다면 반복해서 구간 내에서 최대 값이 있는 위치를 찾아 구간 맨 앞의 요소와 교환하세요.
교환한 후에는 구간 내의 요소 개수를 1 감소하고 구간의 시작 위치를 다음 위치로 이동하세요.
제일 큰 값의 위치를 찾는 부분과 두 수를 교환하는 부분은 이미 작성한 함수를 호출하세요.
 
함수 SelectionSort: 정수들이 있는 시작 위치 n:원소 개수)
    반복: n 0보다 클 동안
        base에서 n 개의 원소 중에 제일 큰 위치를 찾아 max_pos에 대입
        max_pos base 위치의 원소를 교환
    n 1 감소, base를 다음 위치로 이동(for문의 후처리 구문)
 
void SelectionSort(int *base, int n)
{
    int *max_pos=0;
    for (   ; n>0 ;  n--, base++)
    {
        max_pos = GetMaxPos(base,n);
        Swap(max_pos, base);
    }
}

반응형