파이썬 Heap Sort로 내림차순으로 정렬하는 방식입니다.

시간복잡도 : O(nlogn)

def heapify(A, n, k):

    while 2*k+1 < n:

        L = 2*k+1

        R = 2*k+2

        if A[k] > A[L]:

            m = L

        else:

            m = k

        if R < n and A[m] > A[R]:

            m = R

        if k != m:

            A[k], A[m] = A[m], A[k]

            k = m

        else:

            break

def make_heap(A):

    for k in range(len(A)/2, -1, -1):

        heapify(A, len(A), k)

def heapSort(A):

    make_heap(A)

    n = len(A)

    for k in range(len(A)-1):

        A[0], A[n-1] = A[n-1], A[0]

        n = n-1

        heapify(A, n, 0)

if __name__ == '__main__':

    A = [3, 10, 7, 9, 8, 5, 12, 21, 4, 15]

    heapSort(A)

    print A

파이썬 Heap Sort로 오름차순으로 정렬하는 방식입니다.

시간복잡도 : O(nlogn)

def heapify(A, n, k):

    while 2*k+1 < n:

        L = 2*k+1

        R = 2*k+2

        if A[k] < A[L]:

            m = L

        else:

            m = k

        if R < n and A[m] < A[R]:

            m = R

        if k != m:

            A[k], A[m] = A[m], A[k]

            k = m

        else:

            break

def make_heap(A):

    for k in range(len(A)/2, -1, -1):

        heapify(A, len(A), k)

def heapSort(A):

    make_heap(A)

    n = len(A)

    for k in range(n-1):

        A[0], A[n-1] = A[n-1], A[0]

        n -= 1

        heapify(A, n, 0)

if __name__ == '__main__':

    A = [3, 10, 7, 9, 8, 5, 12, 21, 4, 15]

    heapSort(A)

    print A

파이썬 Selection Sort로 오름차순으로 정렬하는 방식입니다.

시간복잡도 : O(n^2)

def selectionSort(A):

    for i in range(len(A)):

        minValue = i

        for j in range(i+1, len(A)):

            if A[j] < A[minValue]:

                minValue = j

        A[minValue], A[i] = A[i], A[minValue]

if __name__ == '__main__':

    A = [4, 1, 5, 8, 6, 2, 3, 7, 10]

    selectionSort(A)

    print A

파이썬 Insertion Sort로 오름차순으로 정렬하는 방식입니다.

시간복잡도 : O(n^2)

def insertionSort(A):

    for i in range(1, len(A)):

        temp = A[i]

        j = i

        while j > 0 and A[j-1] > temp:

            A[j] = A[j-1]

            j -= 1

        A[j] = temp

if __name__ == '__main__':

    A = [4, 1, 5, 8, 6, 2, 3, 7, 10]

    insertionSort(A)

    print A

파이썬 Quick Sort로 오름차순으로 정렬하는 방식입니다.

시간복잡도 : O(n^2) - Worst Case 일 때 이지만,

일반적으로는 가장 빠른 정렬으로 시간복잡도를 O(nlogn) 으로 봅니다.

def quickSort(A, first, last):

    left = first + 1

    right = last

    if first >= last:

        return

    pivot = A[first]

    while left <= right:

        while left <= last and A[left] < pivot:

            left += 1

        while right > first and A[right] >= pivot:

            right -= 1

        if left <= right:

            A[left], A[right] = A[right], A[left]

            left += 1

            right -= 1

    A[right], A[first] = A[first], A[right]

    quickSort(A, first, right-1)

    quickSort(A, left, last)

if __name__ == '__main__':

    A = [4, 1, 5, 8, 6, 2, 3, 7, 10]

    quickSort(A, 0, len(A)-1)

    print A

파이썬 Bubble Sort로 오름차순으로 정렬하는 방식입니다.

시간복잡도 : O(n^2)

def bubbleSort(A):

    for i in range(len(A)):

        for j in range(1, len(A)):

            if A[j-1] > A[j]:

                A[j-1], A[j] = A[j], A[j-1]

if __name__ == '__main__':

    A = [1, 9, 2, 5, 4, 8, 15, 3]

    bubbleSort(A)

    print A

Algorithm 메뉴에 포스팅했던 백준 알고리즘 문제들에 대하여,

예전에 알고리즘을 처음 해보기 시작할 때 문제풀어보기에 급급히 작성했던 코드들이어서 

부족한 코드도, 수정해야하는 코드도 많은데 보완없이 그대로 올렸던 터라 많이 고쳐야 할 것 같습니다.

최근 블로그 활동을 많이 못하게 되었는데, 조만간 전체적인 코드 수정과 함께 

시간이 된다면 추가적으로 문제들을 더 올려보도록 노력하겠습니다.

지난번, 네이버 음성인식 API를 다루는 포스팅을 

1. Android(7) - 네이버 음성인식 API 이용하기 (1) : http://jwprogramming.tistory.com/168

2. Android(8) - 네이버 음성인식 API 이용하기 (2) : http://jwprogramming.tistory.com/169

에서 다루었습니다.

지난 번에는 코드를 직접 옮기면서 조금은 복잡하게 설명드렸다고 생각되어 조금 더 이해하기 쉽게 다시 포스팅하게 되었습니다. 

실질적으로 본인의 Android Studio 툴에서, 네이버 음성인식 API를 바로 테스트해보겠습니다.

우리는 이전 포스팅에서 네이버 음성인식 라이브러리를 다운받은 적이 있습니다. 압축을 풀어줍시다. (* 이전 포스팅들에서 네이버 개발자 센터에서 음성인식 API를 신청하고, Client ID와 Secret을 얻는 것까지는 진행해주셔야 합니다.!)

Import Project 를 통하여 훨씬 쉽고 간편하게 바로 테스트 해보실 수 있습니다.

처음 프로젝트 생성 시, New Project 외에 여러가지 메뉴가 있습니다. 여기서 Import Project를 클릭하여 이전에 다운받은 라이브러리를 import 해주어야 합니다.

보시는 바와 같이 다운받고, 압축을 풀어준 폴더를 찾아서, NaverspeechClient-android-studio 를 선택 후, OK 버튼을 눌러주면 아래와 같이 Android Studio Project가 새로 생성됩니다.

이렇게 네이버에서 제공하는 라이브러리를 이용하여 바로 테스트 해볼 수 있습니다.

단, Package name은 신경 써야하는데, Android_Manifest.xml 내의 

[Package name]

package="com.naver.naverspeech.client"

부분과, 

Gradle Scripts 내의 build.gradle(Module:app)

[applicationId]

defaultConfig {
    applicationId "com.naver.naverspeech.client"
    targetSdkVersion 23
}

부분을 자신이 네이버 개발자센터에서 API신청을 할 때, Android package name 을 등록한 부분과 맞춰주어야 합니다.

그 외, 프로젝트 내에서 각 소스들 상단의 package 이름이

package com.naver.naverspeech.client;

와 같이 되어있을 것입니다.

이 부분을 자신의 package 로 전부 바꿔주시고, 마지막으로 MainActivity.java 에서 CLIENT_ID를 자신의 CLIENT_ID 로 바꿔주신 후 테스트하면 될 것입니다.