레이블이 C언어인 게시물을 표시합니다. 모든 게시물 표시
레이블이 C언어인 게시물을 표시합니다. 모든 게시물 표시

2015년 3월 18일 수요일

[Algorithm] stack을 이용한 순열(모든 부분집합, power set) 구하기

Stack을 이용한 순열 구하는 방법으로
아래와 같이 사용할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
 
 
// 배열 출력하기
void printSet(int array[], int size){    
    for (int i = 1; i <= size; i++)
        printf("%d ", array[i]);
    printf("\n");
 
    return;
}
 
// 반복문과 스택을 이용한 순열 구하기
void printPowerset(int n){
    int stack[10], k;
 
    stack[0] = 0; // 0은 제외
    k = 0;
 
    while (1){
        if (stack[k]<n){
            stack[k + 1] = stack[k] + 1;
            k++;
        }
 
        else{
            stack[k - 1]++;
            k--;
        }
 
        if (k == 0)
            break;
 
        printSet(stack, k);
    }
 
    return;
}
 
// 재귀를 통한 순열 구하기
void powersetRec(int s[], int k, int m, int n) {
    if (m <= n) {
        s[k + 1] = m;
        printSet(s, k + 1);
        powersetRec(s, k + 1, m + 1, n); /* with m */
        powersetRec(s, k, m + 1, n); /*  without m */
    }
}
 
int main(){
 
    int s[6]; // stack
    powersetRec(s, 0, 1, 4);
    
    printPowerset(4);
 
    return 0;
}
 
cs


출력 결과물

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



작성자: 시간: 댓글 없음:
라벨: , , , , ,

2015년 3월 17일 화요일

[Algorithm] Binary Counting - 비트연산을 통한 순열(부분집합, power set) 구하기

프로그래밍을 하다보면, 모든 경우의 수를 확인해야 하는 경우가 생기는데,
이럴경우 각 원소에 대한 모든 부분집합을 구해서 확인해야 한다.

1, 2, 3에 대해서 본다면 아래와 같은 모든 부분 집합이 존재 한다.
(1), (2), (3), (1 2), (1 3), (2 3), (1 2 3)

이러한 부분집합을 구할때 간단히 비트연산을 이용해서 구할 수 있는 방법이 있다.


A, B, C, D에 대한 부분 집합 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void main(void){
    int i, j;
    char arr[4] = { 'a', 'b', 'c', 'd' };
    int n = 4;
    for (i = 0; i < (1 << (n)); i++){
        for (j = 0; j < n; j++){
            if (i & (1 << j)){
                printf("%c ", arr[j]);
            }
        }
        printf("\n");
    }
}
cs
위 비트연산 1<<(n) 과, i & (1<<j) 에 대한 설명은 ->여기로<-

원소 수에 해당하는 N개의 비트열을 이용한다.
N번째 비트값이 1이면 N번째 원소가 포함되었음을 의미한다.


4비트에서 하나씩 증가 했을때의 자리수로 아래와 같이 출력됨.

10 진수
이진수
{A, B, C, D}
0
0000
1
0001
A
2
0010
B
3
0011
B, A
4
0100
C
5
0101
C, A
6
0110
C, B
7
0111
C, B, A
8
1000
D
9
1001
D, A
10
1010
D, B
11
1011
D, B, A
12
1100
D, C
13
1101
D, C, A
14
1110
D, C, B
15
1111
D, C, B, A



작성자: 시간: 댓글 없음:
라벨: , , , , , ,

[Basic Skill] 유용한 비트 연산자

1<<n
  • 2n의 값을 갖는다.
  • 원소가 n개일 경우의 모든 부분집합의 수를 의미한다.
  • Power set(모든 부분 집합)
    • 공집합과 자기 자신을 포함한 모든 부분집합
    • 각 원소가 포함되거나 포함되지 않는 2가지 경우의 수를 계산하면 모든 부분집합의 수가 계산된다.

 i & (1 << j)
  • 계산 결과는 i의 j번째 비트가 1인지 아닌지를 의미한다.
작성자: 시간: 댓글 없음:
라벨: , ,

2015년 2월 12일 목요일

[Algorithm] Quick Sort

Quick Sort는 보편적으로 가장 빠른 정렬 알고리즘으로 pivot값을 정할때 전체 값중 한쪽에 편중된 pivot이 정해지면 효율이 최악이 될 수도 있어, 경우에 따라서는 Counting Sort가 빠른 경우도 있다.

또한 정렬할 배열이 100개 이하라면 선택 정렬을 사용하는게 속도에 유리할 수가 있다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void quicksort(int arr[], int left, int right){
    int i = left, j = right;
    int tmp;
    int pivot = arr[(left + right) / 2];
    while (i <= j){
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i <= j){
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    if (left < j)
        quicksort(arr, left, j);
    if (i < right)
        quicksort(arr, i, right);
}
cs
작성자: 시간: 댓글 없음:
라벨: , , , ,

[Basic Skill] 2,4,8,16진수 -> 10진수 변환하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 제곱근
int power(int value, int num){
    int result = 1;
    for (int i = 0; i < num; i++)
        result *= value;
    return result;
}
// 진수변환하기 (2,4,8,16 진수를 10진수로 변환)
// input ex) B, Q, O, H  (순서대로, 2, 4, 8, 16진수)
// 2진수 양수 )  1.0.1.1.B  or  +1.1.0.B
// 4진수 음수 )  -3.0.1.1.Q
// 16진수 음수 )  -A.9.F.H
int converToDec(char * str, int length, int type){
    int count = 0;
    // 해당 진수의 재곱근하여 자리수를 찾음.
    count = power(type, (length + 1) / 2 -1);
    int result = 0;
    char tempStr[50] = { 0, };
    int start = 0;
    int end = 0;
    bool minus = false;
    int atoi = 0;
    
    for (int i = 0; i <= length; i++){
        if (*(str + i) == '.'){
            end = i;
            stringCopy(tempStr, str, start, end);
            atoi = asciiToInteger(tempStr);
            result += atoi * count;
            start = end + 1;
            count /= type;            
        }
        else if (*(str + i) == '-'){ // 음수일경우
            start = i + 1;
            minus = true;
        }
        else if (*(str + i) == '+'){ // 양수일경우
            start = i + 1;
        }
    }
    if (minus)
        return -result;
    return result;
}
cs
작성자: 시간: 댓글 없음:
라벨: , , ,

2014년 12월 18일 목요일

[Basic Skill] 문자를 Integer로 변환하기 (Ascii to Integer)

문자열을 int형으로 변환하기 위해서는 0~10 이라는 숫자를 표시하는 문자에
'0' 이라는 숫자를 나타내는 Ascii 값인 48을 빼주면 된다.

간단히 말해
0 이라는 문자는 Ascii 값 48 이고, 1이라는 문자는 Ascii값 49... 로 되어 있기 때문에

예로 2라는 숫자는 50 이라는 Ascii 코드로 약속 되어 있기 때문에

50 - 48 을 통해 2 라는 숫자가 나오고, 그 2라를 값을 int형으로 지정하면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 문자형 숫자를 Integer로 변환하기 (1~10, A~F)
int asciiToInteger(const char * str){
    int result = 0;
 
    while (*str){
        if (*str >= '0' && *str <= '9'){ // 0~9 의 문자일 경우
            result = result * 10 + *str - '0';
        }
        else if (*str >= 'A' && *str <= 'F'){ // A~F의 문자일 경우
            result = result * 10 + (*str - 'A') + 10;
        }        
        str++;
    }
 
    return result;
}
 
cs
작성자: 시간: 댓글 없음:
라벨: , ,

[Basic Skill] 문자열 복사 (strcpy) 구현하기

문자를 복사하기 위해서는 해당 문자열의 시작과 끝 위치를 정해서 아래와 같이
문자열 복사가 가능함.



1
2
3
4
5
6
7
8
void stringCopy(char *dest, const char *src, int start, int end){
    int i = 0;
    for (int i = 0; i < end - start; i++){
        *(dest + i) = *(src + start + i);
    }
    // printf("stringCopy dest %s src %s \n", dest, src);
    return;
}
cs
작성자: 시간: 댓글 없음:
라벨: , ,

[Basic Skill] 문자열의 길이 구현하기 strLength

문자열의 길이를 구하기 위해서 문자 배열의 길이를 구하면 됨.
문자 배열에서 '\0' 혹은 'NULL' 을 만나기 전 까지 count 하면 그게 문제 길이가 됩니다.


1
2
3
4
5
6
7
8
int strLength(const char *str){
    int strlen = 0;
        while (*(str++) != '\0'){
            strlen++;
        };
        // printf("string length = %d \n", strlen);
    return strlen;
}
cs

작성자: 시간: 댓글 없음:
라벨: , ,
피드 구독하기: 글 (Atom)