포인터(6)

(이 책 기준)포인터의 기초적인 부분과 1차원 배열까지 모두 배웠다. 배웠으면 써먹는게 좋다. 마침 이 책의 14강까지 끝나 포인터와 1차원 배열에 관한 개념이 끝나고 15강으로 들어와 도전문제들이 나온다.

 

이 책의 필자는 문제 5번이 정렬에 관한 문제라고 하여 제일 먼저 푸는 것을 추천했으므로 5번먼저 풀고 1번부터 풀겠다.(아니 그럴거면 그냥 1번에 정렬문제를 놓지)

 

도전 5.

내림차순의 버블정렬을 구현하여 길이 7의 1차원 int형 배열을 내림차순으로 정렬한 후 출력하는 문제.

 

책의 저자는 이 문제를 내기전에 오름차순의 버블정렬을 설명 및 구현해놓았으니 구현한건 보지말고 설명만 보고 만들어 보자.

 

버블정렬의 큰 틀은, (오름차순 기준)인접한 두 수를 비교하여 큰 수를 오른쪽으로 계속 밀어내는 것이다. 

 

배열 4, 2, 3, 1이 있다고 치자. 맨 처음의 원소와 인접한 원소를 비교하여 처음의 원소가 큰 경우, 위치를 바꾸고 이를 반복하는 작업이다. 

 

4와 2중에서 4가 더 크기 때문에 다음과 같이 될 것이다.

 

4 2 3 1 >> 2 4 3 1

 

이를 반복하면, 다음과 같이 될 것이다.

 

2 4 3 1 >> 2 3 4 1 >> 2 3 1 4

 

이렇게 1단계가 끝났다. 2단계를 보자.

 

2보다는 3이 크기 때문에 바꾸지 않고, 이제 3과 인접한 수를 비교한다. 3은 1보다 크기 때문에 바꾼다.

 

2 3 1 4 >> 2 1 3 4

 

이제, 마지막 단계이다. 2는 1보다 크기 때문에 바꿔준다.

 

2 1 3 4 >> 1 2 3 4

 

이렇게 하면 오름차순의 버블정렬의 과정을 모두 살펴보았다.

 

이를 C언어로 구현해보았다.

#include <stdio.h>

void bubble_sort (int * arr, int len) {
    int temp;
    for (int i = 0; i < len-1; i++) { // 맨 마지막 숫자의 바로 전까지 비교해야 한다. 인접한 두수를 비교하기 때문
        for (int j = 0; j < len - i -1 ; j++) { // 맨 마지막 부분들은 정렬하다보면 정렬이 된 수들이기 때문에, 범위를 점점 좁힌다.
            if (arr[j] > arr[j+1]) { // 정렬
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }	
        }
    }
}

구현하면서 생각이 들었지만, 버블정렬은 알고리즘 및 구현이 정말 쉽지만, 시간적인 부분에서 효율적인 알고리즘은 아닌 것 같다. 그래서 이에 대해 좀더 알아보니 생각이 확실해졌다. 버블 정렬 알고리즘은 데이터가 어떻게 들어오든간에 이중반복문을 완전히 통과해야 하므로 시간복잡도가 O(n^2)로 고정이 된다. 그리 효율적인 알고리즘은 아니라는 것.

 

버블정렬에 관한 것은 나중에 정렬 알고리즘에 관해 더 공부할 때 자세히 알아보는걸로 하고, 이제 문제를 살펴보자.

 

길이 7의 정수형 배열을 입력받고, 이를 내림차순으로 정리하여 출력하는 문제이다.

 

입력:

1

2

3

4

5

6

7

 

출력:

7 6 5 4 3 2 1

 

오름차순 정렬에서는 인접한 수를 비교할 때 앞의 수가 큰 경우에 바꾼다면, 내림차순은 이를 반대로 하면 될 것이다. 이를 적용하여 풀어보자.

#include <stdio.h>

void bubble_sort (int * arr, int len) {
    int temp;
    for (int i = 0; i < len-1; i++) {
        for (int j = 0; j < len - i -1 ; j++) {
            if (arr[j] < arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }	
        }
    }
}

int main () {
    int arr[7];

    for (int i = 0; i < 7; i++) {
        scanf("%d", &arr[i]);
    }
    
    bubble_sort(arr, sizeof(arr)/sizeof(int));
    
    for (int i = 0; i < 7; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

멀쩡히 잘 돌아가는걸 볼 수 있다.

 

도전 1

길이 10의 배열을 선언하고 10개의 정수를 입력받은 후 홀수 짝수를 구분하여 출력한다. 이때 배열 입력은 main에서, 홀수 짝수를 출력하는 것은 각각의 함수를 만들어 호출하는 방식으로 해결하라.

 

문제대로 하면 끝

#include <stdio.h>

void even_num (int arr[], int len);
void odd_num (int arr[], int len);

int main () {
    int arr[10];

    for (int i = 0; i < 10; i++) {
        scanf("%d", &arr[i]);
    }
    even_num(arr, 10);
    odd_num(arr, 10);

    return 0;
}

void even_num (int arr[], int len) {
    printf("짝수 출력: ");
    for (int i = 0; i < len; i++) {
        if (!(arr[i] % 2)) printf("%d ", arr[i]);
    }
    printf("\n");
}
void odd_num (int arr[], int len) {
    printf("홀수 출력: ");
    for (int i = 0; i < len; i++) {
        if (arr[i] % 2) printf("%d ", arr[i]);
    }
    printf("\n");
}

 

도전 2

10진수 정수를 받아 2진수로 변환하여 출력하라.

 

8진수, 16진수의 서식문자는 있는데 2진수는 없다. 뭐...일일히 2로 나눠서 구하는 수밖에...

 

예시

입력 : 12

츨력 : 1100

#include <stdio.h>

int main () {
    int bin;
    int arr[sizeof(int)*8] = {0,};
    int cnt = 0;
    scanf("%d", &bin);

    if (bin < 2) {
        printf("%d", bin);
    } else {
        while (bin > 1) {
            arr[cnt] = bin % 2;
            cnt++; bin /= 2;
        }
        if (bin == 1) arr[cnt] = 1;
    }
    for (int i = cnt; i >= 0; i--) {
        printf("%d", arr[i]);
    }
    return 0;
}

 

도전 3

 

길이 10인 정수형 배열을 선언하고 10개를 입력받는다. 입력받은 숫자가 홀수면 앞에서부터, 짝수면 뒤에서부터 배열에 채워넣는다. 만약 사용자가 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]으로 입력했다면, 배열에는 [1, 3, 5, 7, 9, 10, 8, 6, 4, 2]로 저장되어야 한다.

#include <stdio.h>
#define N 10

int main () {
    int user;
    int arr[N];
    int odd = 0, even = N -1;

    for (int i = 0; i < N; i++) {
        scanf("%d", &user);
        if (user % 2) { // 홀수라면
            arr[odd] = user;
            odd++;
        } else { // 짝수라면
            arr[even] = user;
            even--;
        }
    }
    for (int i = 0; i < N; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

 

도전 4

 

문자열을 입력받아 회문인지 아닌지 판단하는 문제, 조건은 대소문자까지 일치해야 한다.

 

https://codejin.tistory.com/30

백준 1259번 C언어 & Python3 풀이

이전에 풀어놓은게 있어서 참고했다.

 

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool is_palindrome (char *word, int len) {
	bool ret = true;
	int size = (len + 1) / 2;

	for (int i = 0; i < size; i++) {
		if (word[i] != word[len-1-i]) {
            ret = !ret;
            break;
		}
	}
	return ret;
}

int main () {
	char a[101];
	scanf("%s", a);
	printf("회문%s니다", is_palindrome(a, strlen(a)) ? "입" : "이 아닙");
}

 

 

이제 다음 챕터로 넘어가자. 그래봤자 또 포인터지만 ㅎ.....