# 바이너리에서 1인 Bit만 세어보기: Hamming weight(Population count algorithm)


2진수로 바꾸었을때 길이가 n인 정수에서 1인 bit만 세어보는 알고리즘을

발전하는 순서로 나열해 보았습니다.



1. 2로 계속 나누면서 나머지 세기 = O(n)

// 

public static int bitCount1(int i) {
    int count = 0;

    while (i > 0) {
        count += i%2;
        i /= 2;
    }

    return count;
}



2. bit shift 이용해서 1자리 세기 = O(n)

//

public static int bitCount2(int i) {
    int count = 0;

    while (i> 0) {
        count += 0x1 & i;
        i = i >> 1;
    }

    return count;
}



3-1. Population count 알고리즘으로 풀기 = O(log(n))

 // Java의 음수의 경우는 >> 할 때 맨 왼쪽에 1이 의도치않게 붙어서 >>> 를 사용하는게 낫다.

public static int bitCount3(int i) {
    i = (i & 0x55555555) + ((i >>> 1) & 0x55555555);        // ...01010101010101010101010101010101...
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);        // ...00110011001100110011001100110011...
    i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f);        // ...00001111000011110000111100001111...
    i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff);        // ...00000000111111110000000011111111...
    i = (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff);       // ...00000000000000001111111111111111...
    return i & 0x3f;
}



3-2. 고민말고 Integer.bitCount() 쓰기 = O(log(n))

// 원리는 3-1과 똑같다.

public static int bitCount4(int i) {
    return Integer.bitCount(i);
}



# 1~3 까지의 성능비교

// shift도 빠르지만...

for (int i=0; i < Integer.MAX_VALUE; i++) {
    int a = bitCount(i);
}

bitCount1 = 90,453ms

bitCount2 = 31,677ms

bitCount3 = 3ms

bitCount4 = 3ms



4. Hardware 찬스 쓰기

CPU 영역에서 bit를 한번에 세주는 기능이 있다고 한다.



Reference:

- https://en.wikipedia.org/wiki/Hamming_weight

- https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer

저작자표시 동일조건

'Algorithms' 카테고리의 다른 글

Wildcard('?', '*') 패턴 매칭 알고리즘  (0) 2018.11.20


# Wildcard('?', '*') 패턴 매칭 알고리즘


Wildcard가 들어간 패턴과 주어진 문자가 해당하는지 확인하는 알고리즘 중

매칭테이블로 이를 구현하는 것에 대해 알아본다.


1. 문제의 정의

- "ABC" == "ABC": 문자열 모두 동일하다면 True

- "ABC" == "A?C": 문자열 중 ?가 있는 한글자만 빼고, 나머지는 동일하다면 True

- "AC" == "A*C", "ABBBC" == "A*C": 문자열 중 *가 있는 부분이 없거나 여러개인 경우, 나머지는 동일하다면 True


2. 매칭테이블

Dynamic Programming 기법으로서 이전의 문자열까지의 비교를 누적하고, 다음문자를 비교할때 이를 참고한다.


Matching Table
0123...m
A?C...*
0T(0,0)T(0,1)T(0,2)T(0,3)...T(0,m)
1AT(1,0)T(1,1)T(1,2)T(1,3)...T(1,m)
2BT(2,0)T(2,1)T(2,2)T(2,3)...T(2,m)
3CT(3,0)T(3,1)T(3,2)T(3,3)...T(3,m)
........................
nZT(n,0)T(n,1)T(n,2)T(n,3)...T(n,m)

T(n, m)가 패턴 매칭의 결과가 된다.


3. 매칭의 조건

- case1: text[0] == pattern[0] 이면, T(0,0) = True 라고 본다.

             공백과 공백의 비교는 True라고 본다.

             하지만, 물론, 공백과 공백이 아닌 문자의 비교는 False이다.


- case2: text[i] == pattern[j]  이면, T(i, j) = T(i-1, j-1) 을 따른다.(대각선 상속)

              자기 위치의 문자와, 이전까지 문자열이 매칭되고 있었는지의 누적결과도 확인하는 것이다.


- case3: pattern[j] == ? 이면, T(i, j) = T(i-1, j-1) 을 따른다.(대각선 상속)

              ?의 패턴은 아무문자나 가능하고 그 개수만 맞으면 되기 때문에 이전까지의 누적결과만 확인하면 된다.


- case4: pattern[j] == * 이면, T(i, j) = T(i, j-1) 혹은 T(i-1, j) 을 따른다.(옆 또는 위 상속)

              T(i, j-1) 는 * 의 자리에 특정문자가 추가될 수 있음을 나타내고, 그 이전까지의 누적결과는 괜찮았는지 확인하는 것이다.

              T(i-1, j) 는 * 가 공백에 매칭되고 있음을 나타내고, 그 이전까지의 누적결과는 괜찮았는지 확인하는 것이다.


- case5: pattern[1] == * 이면, T(0, j) = T(0, j-1) 을 따른다.(옆 상속)

              패턴이 *로 시작하면 다음 pattern[2] 까지 문제없음을 전달하기 위함이다.



4. 다양한 case 확인해보기



Reference:

- https://www.geeksforgeeks.org/wildcard-pattern-matching/

- https://www.youtube.com/watch?v=3ZDZ-N0EPV0



저작자표시 동일조건

'Algorithms' 카테고리의 다른 글

바이너리에서 1인 Bit만 세어보기: Hamming weight(Population count algorithm)  (0) 2018.11.27

# [1000] A+B를 출력 solved by Python, C++, C, Java, Kotlin

문제: https://www.acmicpc.net/problem/1000


나는 이 문제가 백준코딩의 시작이었다.

백준코딩을 시작하려면 이걸 젤 먼저 풀어야 할 것 같은데 왜 1000번일까?....

function을 채워넣는 문제만 풀어봤던 나는 백준코딩 사이트의 입출력이 친절하지 않게 느껴진다.

입력은 text를 통으로 던져주고, 그걸 분석해내는 것 부터가 시작이다.

출력은 걍 바닥(콘솔)에다 뿌리는거다.

심지어 로그같은것도 찍을 수 없는데다가 출력화면이 없다.

Judge만 하지 틀린이유나 예제를 공개하지 않는다.

이러한 평가방법은 더 불친절해서 거만하게 까지 느껴진다.


어쨌든 콘솔입력을 쉽게 접하지 않은 사람에게 시작부터가 챌린지다.

콘솔입력을 받아들이는 방법은 조금씩 달라지겠지만

1000번 문제가 자신만의 입력방식을 찾고 익혀볼 수 있는 문제가 아닐까 생각한다.


1. By Python:

input()으로 한줄을 읽고 parsing한 다음 계산한다.

input 말고도 있겠지만 input()이 Python의 표준이라고 하기도 하고

parsing, converting이 상대적으로 쉽기 때문에 걍 풀어버렸다.


 

'''
input example
1 2

'''

line = input()
a, b = line.split(' ')
print(int(a) + int(b))



2. By C++:

scanf, cin도 있고 text에 예제를 저장해서 불러오는 등 다양한 방법이 있는데 C++하면 cin인것 같아서...

하지만, 속도가 느리다는 백준의 비교측정 포스트를 보고 scanf로 추후 바꾸게 된다.



#include <stdio.h>

#include <iostream>


using namespace std;


int main() {

    

    int a, b;

    cin >> a >> b;

    cout << a+b << "\n";

    

    return 0;

}

 

여기서 중요한 건, include와 "main"이라는 함수명 등이 고스란이 포함되어 있어야 한다는 것이다.

이것은 백지에서 시작하는 것이 function을 채워넣는 문제에 비하여

얼마나 불필요한 일들에 신경을 써야 하는지를 보여준다.

반면에 이렇게 함으로서 개인이 즐겨쓰는 라이브러리를 포함할 수도 있고(백준에서 지원 안해주면 컴파일에러나고 왜 그런지도 모르겠지만...)

알고리즘의 자유도는 증가하는 것 같다.



3. By C:

단순하게 scanf를 썼다.

 #include <stdio.h>


int main() {

    

    int a, b;

    scanf("%d %d", &a, &b);

    printf("%d\n", a+b);

    

    return 0;

}



4. By Java:

BufferedReader로 열심히 해봤다가

언어별 기본 포멧을 제공한다는 것을 발견하고는

부끄러워서 지우고 예제와 같은 방법을 사용하기로 했다.


import java.util.Scanner;

public class main {

    public static void main_2() {
        Scanner sc = new Scanner(System.in);
        int a, b;
        a = sc.nextInt();
        b = sc.nextInt();
        System.out.println(a + b);
    }
}



5. By Kotlin:

Kotlin은 class를 쓰지 않고도 이렇게 메소드만 달랑 쓸수 있단다.

잘 몰라서 예제와 똑같아 했다.



import java.util.Scanner

fun main(args: Array<String>) {
    val sc: Scanner = Scanner(System.`in`)
    var a = sc.nextInt()
    var b = sc.nextInt()
    println(a + b)
}



================================================================

Reference:

- https://www.acmicpc.net/problem/1000

- https://www.acmicpc.net/help/language


저작자표시 동일조건

Quick sort(퀵 정렬)



원칙1: pivot을 고른다.(주로 첫번째 또는 마지막 값을 선정하는 편이다.)

원칙2: pivot값을 기준으로 작은쪽, 큰쪽으로 나누어 서로간의 swap으로 위치를 교환한다.(증가될 수 없는 배열이라고 가정....)

원칙3: swap이 끝나면 그 나눈 중심에 pivot을 두고 작은쪽, 큰쪽을 각각 퀵소트한다.



Best case: O(n) 

Average case: O()

Worst case: O() 


# 재귀함수로 구현한 Quick sort

public class QuickSort implements ISort {


    @Override

    public void sort(Comparable[] array) {

        quickSort(array, 0, array.length - 1);

    }


    private void quickSort(Comparable[] array, int startIndex, int endIndex) {

        if (startIndex >= endIndex) {

            return;

        }


        final Comparable pivot = array[startIndex];

        int left = startIndex + 1;

        int right = endIndex;


        do {

            while (array[left].compareTo(pivot) < 0 && left < endIndex) {

                left++;

            }

            while (array[right].compareTo(pivot) > 0 && startIndex < right) {

                right--;

            }


            if (left < right) {

                swap(array, left, right);

            }


        } while (left < right && left < endIndex && startIndex < right);

        swap(array, startIndex, right);


        quickSort(array, startIndex, right - 1);

        quickSort(array, right + 1, endIndex);

    }


    private void swap(Comparable[] array, int i, int j) {

        Comparable temp = array[i];

        array[i] = array[j];

        array[j] = temp;

    }

}


Reference:

- https://en.wikipedia.org/wiki/Quicksort


'Algorithms > Sorting' 카테고리의 다른 글

Merge sort(병합 정렬)  (0) 2017.02.08
Selection sort(선택 정렬)  (0) 2017.02.08
Insertion sort(삽입 정렬)  (0) 2017.02.06
Bubble sort(거품? 정렬)  (0) 2017.02.06

Merge sort(병합 정렬)



원칙1: 2개가 될때까지 쪼갠다.

원칙2: 2개가 되면 서로 비교해서 자리를 바꾸거나 바꾸지 않는다.

원칙3: 이렇게 조각난 2개를 4개로, 4개를 8개로... 순서를 맞추어 병합한다.


Best case: O(n) 

Average case: O()

Worst case: O() : 



# 재귀함수로 구현한 Merge sort

public class MergeSort implements ISort {


    @Override

    public void sort(Comparable[] array) {

        mergeSort(array, 0, array.length - 1);

    }


    private void mergeSort(Comparable[] array, int startIndex, int endIndex) {

        if (endIndex - startIndex < 1) {

            return;

        }


        int middleIndex = (endIndex + startIndex) / 2;

        mergeSort(array, startIndex, middleIndex);

        mergeSort(array, middleIndex + 1, endIndex);


        merge(array, startIndex, middleIndex, endIndex);

    }


    private void merge(Comparable[] array, int startIndex, int middleIndex, int endIndex) {

        Comparable[] mergedArray = new Comparable[endIndex - startIndex + 1];

        int indexA = startIndex;

        int indexB = middleIndex + 1;


        for (int i = 0; i < mergedArray.length; i++) {

            if (indexB > endIndex || (indexA <= middleIndex && array[indexA].compareTo(array[indexB]) < 0)) {

                mergedArray[i] = array[indexA++];

            } else {

                mergedArray[i] = array[indexB++];

            }

        }


        for (int i = 0, j = startIndex; i < mergedArray.length; i++, j++) {

            array[j] = mergedArray[i];

        }

    }

}


Reference:

- https://en.wikipedia.org/wiki/Merge_sort


'Algorithms > Sorting' 카테고리의 다른 글

Quick sort(퀵 정렬)  (0) 2017.06.24
Selection sort(선택 정렬)  (0) 2017.02.08
Insertion sort(삽입 정렬)  (0) 2017.02.06
Bubble sort(거품? 정렬)  (0) 2017.02.06

Selection sort(선택 정렬)




- 1원칙: i 위치에 채워질 최저/최대값을 i 뒤에서 찾는다.

- 2원칙: i보다 가장 작은수를 찾는다.

- 3원칙: 있다면 i와 자리를 바꾼다.



Best case: O()  == Worst case: O() : 어차피 다 확인해야 한다. 


public class SelectionSort {


    public void sort(Comparable[] array) {

        for (int i = 0; i < array.length; i ++) {

            int lowestIndex = i;

            for (int j = i + 1; j < array.length; j++) {

                if (array[lowestIndex].compareTo(array[j]) > 0) {

                    lowestIndex = j;

                }

            }


            // swap

            if (i != lowestIndex) {

                Comparable temp = array[i];

                array[i] = array[lowestIndex];

                array[lowestIndex] = temp;

            }

        }

    }

}


Referenced from: https://en.wikipedia.org/wiki/Selection_sort

'Algorithms > Sorting' 카테고리의 다른 글

Quick sort(퀵 정렬)  (0) 2017.06.24
Merge sort(병합 정렬)  (0) 2017.02.08
Insertion sort(삽입 정렬)  (0) 2017.02.06
Bubble sort(거품? 정렬)  (0) 2017.02.06

Insertion sort(삽입 정렬)



- 1원칙: i의 앞쪽은 이미 정렬된 상태라고 가정(i는 1부터 시작하기에 가능)

- 2원칙: i의 위치에서 자기보다 앞에 있는 (j < i)를 하나씩 비교해보며 작을경우 뒤로 Shifting한다.

- 3원칙: shifting하고 남은 공간에 i에 있던 item을 삽입한다.



i의 앞쪽은 항상 정렬된 상태이고

Best case: O() : 정렬이 거의 다 되어있는 상태에서...

Worst case: O() : 역순정렬된 상태 일때...


public class InsertionSort {


    public void sort(Comparable[] array) {

        for (int i = 1; i < array.length; i++) {

            final Comparable currentItem = array[i];

            int insertPosition = i - 1;

            while (insertPosition >= 0 && currentItem.compareTo(array[insertPosition]) < 0) {

                array[insertPosition + 1] = array[insertPosition];

                insertPosition--;

            }


            insertPosition++;

            if (insertPosition < i) {

                array[insertPosition] = currentItem;

            }

        }

    }

}




Reference:

- https://en.wikipedia.org/wiki/Insertion_sort

'Algorithms > Sorting' 카테고리의 다른 글

Quick sort(퀵 정렬)  (0) 2017.06.24
Merge sort(병합 정렬)  (0) 2017.02.08
Selection sort(선택 정렬)  (0) 2017.02.08
Bubble sort(거품? 정렬)  (0) 2017.02.06

Bubble sort(거품? 정렬)



- 1원칙: i, i +1의 자리를 비교하여 뒤의것이 작다면 자리를 교환한다.

- 2원칙: 0 ~ n -1 이렇게 n개까지 돌리고 교환된 적이 있다면 다시 0부터 돌린다.(loop)

          loop: 앞이나 뒤로 계속 이동해야 할 수 있어서...

- 3원칙: 교환된 것이 없다면 모든것이 정렬완료된 상태이므로 loop를 종료한다.


0부터 n까지 계속 비교하기 때문에 

Best case: O() : 정렬이 거의 다 되어있는 상태에서...

Worst case: O() : 역순정렬된 상태 일때...


이미 정렬된 상태라고 예상될때 쓰는게 좋지 않을까 함


public class BubbleSort {


    public void sort(Comparable[] array) {

        boolean isCompleted = true;

        while (isCompleted) {

            isCompleted = false;

            for (int i = 0; i + 1 < array.length; i++) {

                if (array[i].compareTo(array[i + 1]) > 0) {

                    Comparable temp = array[i];

                    array[i] = array[i + 1];

                    array[i + 1] = temp;

                    isCompleted = true;

                }

            }

        }

    }

}



Reference:

- https://en.wikipedia.org/wiki/Bubble_sort

'Algorithms > Sorting' 카테고리의 다른 글

Quick sort(퀵 정렬)  (0) 2017.06.24
Merge sort(병합 정렬)  (0) 2017.02.08
Selection sort(선택 정렬)  (0) 2017.02.08
Insertion sort(삽입 정렬)  (0) 2017.02.06

+ Recent posts

티스토리툴바