안녕하세요 열코입니다.


이번에는 안드로이드에서 블루투스 연동하는 방법에 대해 알아보겠습니다.


먼저 안드로이드 프로젝트를 빈 프로젝트로 생성합니다.


그리고 안드로이드에서 블루투스에 관한 권한을 얻기 위해


app - src - main - AndroidManifest.xml에 다음과 같이 추가합니다.



1. AndroidManifest.xml에 추가


<uses-permission android:name="android.permission.BLUETOOTH" />

<uses-permission android:name="android.permission.BLUETOOTH_ADMIN" />


- BLUETOOTH : 블루투스 연결 요청, 연결 수락 및 데이터 전송과 같은 블루투스 통신을 수행하기 위해 선언합니다.


- BLUETOOTH_ADMIN : 블루투스 설정 조작 및 앱에서 기기를 검색하기 위해 선언합니다.



2. activity_main.xml에 추가


매인 화면의 액티비티는 다음과 같이 구성되어 있습니다.


<LinearLayout

    android:layout_width="match_parent"

    android:layout_height="match_parent"

    android:orientation="vertical">


    <LinearLayout

        android:layout_width="match_parent"

        android:layout_height="wrap_content"

        android:orientation="horizontal">


        <TextView

            android:layout_width="wrap_content"

            android:layout_height="wrap_content"

            android:text="수신 받은 데이터 : "/>


        <TextView

            android:layout_width="wrap_content"

            android:layout_height="wrap_content"

            android:id="@+id/textView_receive"/>


    </LinearLayout>


    <LinearLayout

        android:layout_width="match_parent"

        android:layout_height="wrap_content"

        android:orientation="horizontal">


        <TextView

            android:layout_width="wrap_content"

            android:layout_height="wrap_content"

            android:text="송신 할 데이터 : "/>


        <EditText

            android:layout_width="wrap_content"

            android:layout_height="wrap_content"

            android:id="@+id/editText_send"

            android:ems="10"/>


    </LinearLayout>


    <Button

        android:layout_width="wrap_content"

        android:layout_height="wrap_content"

        android:text="데이터 송신"

        android:id="@+id/button_send"/>

</LinearLayout>



3. MainActivity.java에 추가


* 함수들의 호출 구조가 약간 복잡하게 되어있습니다. 설명 하는 순서를 잘 따라와 주시기 바랍니다.


매인 액티비티 클래스 안에 다음과 변수들을 선언합니다. 변수들의 용도는 주석으로 설명돼있습니다.


private static final int REQUEST_ENABLE_BT = 10; // 블루투스 활성화 상태

private BluetoothAdapter bluetoothAdapter; // 블루투스 어댑터

private Set<BluetoothDevice> devices; // 블루투스 디바이스 데이터 셋

private BluetoothDevice bluetoothDevice; // 블루투스 디바이스

private BluetoothSocket bluetoothSocket = null; // 블루투스 소켓

private OutputStream outputStream = null; // 블루투스에 데이터를 출력하기 위한 출력 스트림

private InputStream inputStream = null; // 블루투스에 데이터를 입력하기 위한 입력 스트림

private Thread workerThread = null; // 문자열 수신에 사용되는 쓰레드

private byte[] readBuffer; // 수신 된 문자열을 저장하기 위한 버퍼

private int readBufferPosition; // 버퍼 내 문자 저장 위치


private TextView textViewReceive; // 수신 된 데이터를 표시하기 위한 텍스트 뷰

private EditText editTextSend; // 송신 할 데이터를 작성하기 위한 에딧 텍스트

private Button buttonSend; // 송신하기 위한 버튼


위 변수들을 모두 선언해주시고 onCreate 함수 안에 다음과 같이 작성합니다.



@Override

protected void onCreate(Bundle savedInstanceState) {

    super.onCreate(savedInstanceState);

    setContentView(R.layout.activity_main);


    // 각 컨테이너들의 id를 매인 xml과 맞춰준다.

    textViewReceive = (TextView)findViewById(R.id.textView_receive);

    editTextSend = (EditText)findViewById(R.id.editText_send);

    buttonSend = (Button)findViewById(R.id.button_send);


    // 블루투스 활성화하기

    bluetoothAdapter = BluetoothAdapter.getDefaultAdapter(); // 블루투스 어댑터를 디폴트 어댑터로 설정


    if(bluetoothAdapter == null) { // 디바이스가 블루투스를 지원하지 않을 때

        // 여기에 처리 할 코드를 작성하세요.

    }

    else { // 디바이스가 블루투스를 지원 할 때

        if(bluetoothAdapter.isEnabled()) { // 블루투스가 활성화 상태 (기기에 블루투스가 켜져있음)

            selectBluetoothDevice(); // 블루투스 디바이스 선택 함수 호출                

        }

        else { // 블루투스가 비 활성화 상태 (기기에 블루투스가 꺼져있음)

            // 블루투스를 활성화 하기 위한 다이얼로그 출력

            Intent intent = new Intent(BluetoothAdapter.ACTION_REQUEST_ENABLE); 

            // 선택한 값이 onActivityResult 함수에서 콜백된다.

            startActivityForResult(intent, REQUEST_ENABLE_BT); 

        }

    }

}


마찬가지로 간단한 설명은 모두 주석으로 처리했습니다.


onCreate 함수는 프로그램(App)이 실행되고 MainActivity가 자동으로 호출되며 호출되는 순간 onCreate 함수가 호출됩니다.


따라서 가장 먼저 호출되는 함수라고 생각하시면 됩니다. 이 함수안에 블루투스를 활성화 하는 코드를 작성했습니다.


해당 코드를 실행하면 다음과 같은 다이얼로그(대화상자)가 나오며 '사용'을 누르면 디바이스의 블루투스를 켜주는 코드가 되겠습니다.



만약 블루투스를 지원하지 않는 기기의 경우 본 프로그램이 정상 작동하지 않으니 꼭 디바이스가 블루투스를 지원하지 않을 때 < 조건 문에서 처리할 코드를 작성하시기 바랍니다.


☞ "예를들어 finish() 함수를 호출하여 프로그램을 종료시킬 수 있습니다."



권한 요청 다이얼로그에서 '사용'을 누르면 onActivityResult() 함수가 호출됩니다.



onActivityResult() 함수는 Alt + insert 키를 눌러 Override Methods를 눌러 onActivityResult를 선택하면 자동으로 생성됩니다.


생성된 onActivityResult() 함수에 다음과 같이 코드를 작성합니다.



@Override

protected void onActivityResult(int requestCode, int resultCode, @Nullable Intent data) {

    super.onActivityResult(requestCode, resultCode, data);


    switch (requestCode) {

        case REQUEST_ENABLE_BT :

            if(requestCode == RESULT_OK) { // '사용'을 눌렀을 때

                selectBluetoothDevice(); // 블루투스 디바이스 선택 함수 호출

            }

            else { // '취소'를 눌렀을 때

                // 여기에 처리 할 코드를 작성하세요.

            }

            break;

    }

}


'사용'을 눌렀다면 selectBluetoothDevice() 함수를 호출합니다.


만약 '취소'를 눌렀다면 블루투스를 활성화 할 수 없기 때문에 처리 할 코드를 작성 해 주시면 됩니다.


여기까지 블루투스가 비활성화 돼있을 때 수행되는 코드였으며,



아래부터는 블루투스가 이미 활성화 돼있을 때 수행되는 코드입니다.


디바이스가 블루투스를 지원하며 블루투스가 이미 켜져있는 상태라면 selectBluetoothDevice() 함수를 호출합니다.


selectBluetoothDevice() 함수를 다음과 같이 작성합니다. 


public void selectBluetoothDevice() {

    // 이미 페어링 되어있는 블루투스 기기를 찾습니다.

    devices = bluetoothAdapter.getBondedDevices();

    // 페어링 된 디바이스의 크기를 저장

    pariedDeviceCount = devices.size();

    // 페어링 되어있는 장치가 없는 경우

    if(pariedDeviceCount == 0) {

        // 페어링을 하기위한 함수 호출

    }

    // 페어링 되어있는 장치가 있는 경우

    else {

        // 디바이스를 선택하기 위한 다이얼로그 생성

        AlertDialog.Builder builder = new AlertDialog.Builder(this);

        builder.setTitle("페어링 되어있는 블루투스 디바이스 목록");

        // 페어링 된 각각의 디바이스의 이름과 주소를 저장

        List<String> list = new ArrayList<>();

        // 모든 디바이스의 이름을 리스트에 추가

        for(BluetoothDevice bluetoothDevice : devices) {

            list.add(bluetoothDevice.getName());

        }

        list.add("취소");


        // List를 CharSequence 배열로 변경

        final CharSequence[] charSequences = list.toArray(new CharSequence[list.size()]);

        list.toArray(new CharSequence[list.size()]);


        // 해당 아이템을 눌렀을 때 호출 되는 이벤트 리스너

        builder.setItems(charSequences, new DialogInterface.OnClickListener() {

            @Override

            public void onClick(DialogInterface dialog, int which) {

                // 해당 디바이스와 연결하는 함수 호출

                connectDevice(charSequences[which].toString());

            }

        });


        // 뒤로가기 버튼 누를 때 창이 안닫히도록 설정

        builder.setCancelable(false);

        // 다이얼로그 생성

        AlertDialog alertDialog = builder.create();

        alertDialog.show();

    }

}


페어링 되어있는 장치가 없는 경우 페어링을 직접 수행하는 함수를 호출해야합니다.


블루투스 페어링 하는 함수는 최대한 빨리 작성하겠습니다.


현재 프로그램은 이미 페어링 되어있는 블루투스 디바이스만 찾을 수 있습니다.





페어링 되어있는 장치가 있는경우 그 목록을 리스트로 만들어 다이얼로그에 띄웁니다.


해당 리스트 아이템을 눌렀을 때 해당 디바이스와 연결하는 함수(connectDevice 함수)를 호출합니다.


connectDevice() 함수는 다음과 같이 작성합니다.


public void connectDevice(String deviceName) {

    // 페어링 된 디바이스들을 모두 탐색

    for(BluetoothDevice tempDevice : devices) {

        // 사용자가 선택한 이름과 같은 디바이스로 설정하고 반복문 종료

        if(deviceName.equals(tempDevice.getName())) {

            bluetoothDevice = tempDevice;

            break;

        }

    }

    // UUID 생성

    UUID uuid = java.util.UUID.fromString("00001101-0000-1000-8000-00805f9b34fb");

    // Rfcomm 채널을 통해 블루투스 디바이스와 통신하는 소켓 생성

    try {

        bluetoothSocket = bluetoothDevice.createRfcommSocketToServiceRecord(uuid);

        bluetoothSocket.connect();

        // 데이터 송,수신 스트림을 얻어옵니다.

        outputStream = bluetoothSocket.getOutputStream();

        inputStream = bluetoothSocket.getInputStream();

        // 데이터 수신 함수 호출

        receiveData();

    } catch (IOException e) {

        e.printStackTrace();

    }

}


이 함수는 위 다이얼로그에서 선택한 블루투스 디바이스와 연결하는 함수입니다.


블루투스를 연결하고 데이터를 수신하기 위한 함수 receiveData() 함수를 호출합니다.


receiveData() 함수는 다음과 같이 작성합니다.



public void receiveData() {

    final Handler handler = new Handler();

    // 데이터를 수신하기 위한 버퍼를 생성

    readBufferPosition = 0;

    readBuffer = new byte[1024];


    // 데이터를 수신하기 위한 쓰레드 생성

    workerThread = new Thread(new Runnable() {

        @Override

        public void run() {

            while(Thread.currentThread().isInterrupted()) {

                try {

                    // 데이터를 수신했는지 확인합니다.

                    int byteAvailable = inputStream.available();

                    // 데이터가 수신 된 경우

                    if(byteAvailable > 0) {

                        // 입력 스트림에서 바이트 단위로 읽어 옵니다.

                        byte[] bytes = new byte[byteAvailable];

                        inputStream.read(bytes);

                        // 입력 스트림 바이트를 한 바이트씩 읽어 옵니다.

                        for(int i = 0; i < byteAvailable; i++) {

                            byte tempByte = bytes[i];

                            // 개행문자를 기준으로 받음(한줄)

                            if(tempByte == '\n') {

                                // readBuffer 배열을 encodedBytes로 복사

                                byte[] encodedBytes = new byte[readBufferPosition];

                                System.arraycopy(readBuffer, 0, encodedBytes, 0, encodedBytes.length);

                                // 인코딩 된 바이트 배열을 문자열로 변환

                                final String text = new String(encodedBytes, "US-ASCII");

                                readBufferPosition = 0;

                                handler.post(new Runnable() {

                                    @Override

                                    public void run() {

                                        // 텍스트 뷰에 출력

                                        textViewReceive.append(text + "\n");

                                    }

                                });

                            } // 개행 문자가 아닐 경우

                            else {

                                readBuffer[readBufferPosition++] = tempByte;

                            }

                        }

                    }

                } catch (IOException e) {

                    e.printStackTrace();

                }

                try {

                    // 1초마다 받아옴

                    Thread.sleep(1000);

                } catch (InterruptedException e) {

                    e.printStackTrace();

                }

            }

        }

    });

    workerThread.start();

}


수신 된 데이터를 쓰레드를 통해 1초마다 바이트 배열로 받아 인코딩 후 스트링 변수로 변환 하여 텍스트 뷰에 출력하는 코드입니다.


여기까지 블루투스를 통한 데이터 수신 과정이었습니다.



아래는 블루투스를 통한 데이터 송신 과정에 대해 설명하겠습니다.


먼저 이전에 만든 버튼에 다음과 같은 버튼 리스너를 추가합니다. (위치는 onCreate안 buttonSend findViewbyId 밑에 만들면 됩니다.)


buttonSend.setOnClickListener(new View.OnClickListener() {

    @Override

    public void onClick(View v) {

        sendData(editTextSend.getText().toString());

    }

});


버튼을 누르면 sendData() 함수를 호출하는 이벤트 리스너입니다.


sendData()함수를 다음과 같이 작성합니다.


void sendData(String text) {

    // 문자열에 개행문자("\n")를 추가해줍니다.

    text += "\n";

    try{

        // 데이터 송신

        outputStream.write(text.getBytes());

    }catch(Exception e) {

        e.printStackTrace();

    }

}


여기까지 잘 따라오셨다면 블루투스 데이터 송,수신 프로그램이 올바르게 작동 할 것입니다.




이상 안드로이드 블루투스 연동이었습니다.


부족한 부분이나 오류가 나는 부분, 기타 질문사항은 댓글로 남겨주세요!


공감♡ 버튼을 눌러주시면 더욱 유용하고 좋은 포스팅으로 찾아 뵙겠습니다.




이번에는 PC에 비주얼 스튜디오 2017버전을 설치하는 방법에 대해 소개합니다.


먼저 비주얼 스튜디오를 다운로드 받기위해 아래 사이트에 접속합니다.


다운받기 ☜ 클릭



비주얼 스튜디오에는 Community, Professional, Enterprise 이렇게 3가지 버전이 있습니다.


그중 Community는 가장 기본적인 기능을 제공하며 무료로 다운받을 수 있습니다.


그외 Professional, Enterprise 버전은 추가적인 개발용 소프트웨어 및 클라우드 


서비스를 제공하며 추가적으로 교육을 받을도 있습니다.


Professional 버전과 Enterprise 버전의 연간 결제 비용은 539 달러, 3000달러로 책정되어 있습니다. (후덜덜)


사실 Community 버전인 가장 기본적인 버전으로도 현재 구현할 수 있는 모든 기능은 구현 가능하다고 생각합니다.


그렇기 때문에 무료버전인 Community 버전을 다운받아도 개발에 큰 무리가 없습니다.



다운로드가 완료되면 다음과 같은 파일을 실행 시켜줍니다.


vs_community__122977249.1535611188.exe


위 파일을 실행하면 Visual Studio 2017 Installer가 실행됩니다.



프로그램이 실행되면 다음버튼을 누릅니다.



다음과 같은 화면이 나오며 다 될때까지 기다립시다...



다운로드가 완료되면 다음과 같은 화면이 나타납니다.



C/C++ 프로그래밍을 하실분은 C++를 이용한 데스크톱 개발을 선택하시고


C# 프로그래밍을 하실분은 .NET 데스크톱 개발을 선택하시고 설치를 누르면 되겠습니다.


둘다 하실분은 둘다 눌러서 설치합니다!


지금 선택하지 않아도 나중에 설정에 들어가서 설치할 수 있으니 걱정하지마세요!


지금까지 잘 따라오셨다면 설치를 완료했을거라 믿습니다...


혹시 설치 중 오류사항이나 궁금한점은 댓글로 달아주세요!




이상 '비주얼 스튜디오 2017 설치하기' 에 대해 설명했습니다.


공감♡ 버튼을 눌러주시면 더욱 유용하고 좋은 포스팅으로 찾아 뵙겠습니다.




현재 많은 수의 알고리즘이 존재하지만 그중 실제 구현에서는 몇가지 알고리즘만 사용됩니다.


자바, C++ 등의 언어에서는 라이브러리로 O(n log n) 하한의 정렬 알고리즘을 제공하여 그냥 사용하면 되지만, 정렬 알고리즘을 더 깊게 공부하거나, 효율적인 정렬 알고리즘을 사용하려는 개발자를 위해 정렬 알고리즘에 대한 이해는 필수입니다.


실제 구현 시 사용되는 몇가지 알고리즘에 대해 비교 설명 해보겠습니다.

(각 알고리즘에 대한 상세 설명 및 구현방법은 생략합니다. 추후에 정리해서 올릴게요!)



비교 정렬 알고리즘 성능


이름

최적(Best)

평균(Average)

최악(Worst)

메모리

안정성(Stable)*

퀵(Quick) 정렬

n log n

n log n

n^2

log n ~ n

No

합병(Merge) 정렬

n log n

n log n

n log n

n

Yes

 삽입(Insertion) 정렬

n

n^2

n^2

1

Yes

힙(Heap) 정렬

n log n

n log n

n log n

1

No

Intro Sort

n log n

n log n

n log n

log n

No

 선택(Selection) 정렬

n^2

n^2

n^2

1

No

쉘(Shell) 정렬

n log n

gap에 따라 다름

1

No

거품(Bubble) 정렬

n

n^2

n^2

1

Yes


Stable(안정성) : 같은 값에 대해 정렬 시도 후 위치가 바뀌지 않으면 Stable 하다고 하며, 위치가 서로 바뀔 수 있다면 Not Stable 하다고 합니다.



1. 퀵 정렬(Quick Sort) 

- 분할 및 정복 알고리즘으로, 피벗이라는 요소를 사용하여 배열을 분할 합니다.

- 낮은 오버헤드로 다른 O(n log n) 정렬 알고리즘 보다 빠른 성능을 보입니다.

- 최악의 경우 성능이 O(n^2)입니다만, 드문 경우로써 피벗 요소를 잘 선택하여 O(n log n)의 성능을 얻을 수 있습니다.


2. 합병 정렬(Merge Sort)

- 비교 기반 분할 정복 정렬 알고리즘 입니다.

- Python과 Java의 표준 정렬 루틴에 사용되는 Timsort 알고리즘에 사용됩니다.


3. 힙 정렬(Heap Sort) 

- 특별한 유형의 데이터 구조 이진트리를 생성하여 사용합니다.

- 퀵 정렬보다 대부분 다소 느리지만 최악의 경우 O(n log n)이라는 이점이 있습니다. 


4. 삽입 정렬(Insertion Sort) 

- 작은 데이터 셋(data set)에 널리 사용됩니다. 

- 대부분 정렬 된 목록에 비교적 효율적이며, 더 복잡한 알고리즘의 일부로 사용되는 간단한 정렬 알고리즘입니다.


5. Intro Sort

- 하이브리드 정렬 알고리즘으로 퀵 정렬과 힙 정렬을 결합 하여 구현된 알고리즘입니다.

C++ STL(표준 라이브러리)에서 제공합니다.


6. 쉘 정렬(Shell Sort)

- 적은 수의 코드와 합리적으로 빠르며, 임베디드 및 구형 메인 프레임 메모리에 사용됩니다.


7. 거품 정렬(Bubble Sort)

- 구현하기 가장 간단한 알고리즘이지만 O(n^2)으로 정렬 되지 않은 대형 데이터 셋에서 거의 사용되지 않습니다.

- 거의 정렬된 데이터에서 효율적으로 사용됩니다. O(n)




비 비교 정렬 알고리즘 성능


이름

최적(Best)

평균(Average)

최악(Worst)

메모리

안정성(Stable)

버킷(Bucket) 정렬

-

n+k

(n^2) * k

2^k

Yes

 계수(Counting) 정렬

-

n+r

n+r

n+r

Yes

기수(Radix) 정렬

-

n * (k / d)

n * (k / d)

n+(2^d)

Yes



1. 버킷 정렬(Bucket Sort) 

- 배열을 유한 개수의 버킷으로 분할하여 계산하는 분할 정복 정렬 알고리즘입니다.

- 데이터 셋 요소가 모든 버킷에 고르게 분산될 때 가장 최적한 성능을 보입니다.

- 버킷을 할당하기 위한 메모리가 많이 필요합니다.


2. 계수 정렬(Counting Sort)

- 정수 정렬 알고리즘으로 정수 배열(리스트)에 한정적입니다.

- 숫자 크기(r)에 따라 매우 큰 영향을 받을 수 있으며 n에 비해 r이 매우 커지는 경우 비 효율적입니다.


3. 기수 정렬(Radix Sort)

- 자리수 d에 따라 공간 복잡도가 매우 커질 수 있습니다.





이상 정렬 알고리즘에 대해 비교 분석 해 보았습니다.

질문 또는 오타나 잘못된 정보가 있는 경우 댓글로 달아주세요!

공감♡ 버튼을 눌러주시면 더욱 유용하고 좋은 포스팅으로 찾아 뵙겠습니다.



'자료구조, 알고리즘' 카테고리의 다른 글

[BOJ] 8979 올림픽 - 문제 풀이  (1) 2019.03.29
검색 알고리즘 종류  (2) 2018.09.11
자료구조 그래프(Graph)  (1) 2018.09.06
자료구조 힙(Heap)  (0) 2018.09.05
자료구조 이진 탐색 트리(Binary Search Tree)  (0) 2018.09.01
자료구조 트리(Tree)  (0) 2018.08.30
[자료구조] 큐 QUEUE  (0) 2018.08.19
[자료구조] 스택 STACK  (0) 2018.08.19



안녕하세요 열코입니다.

이번시간에는 기본적인 검색(탐색) 알고리즘 종류들에 대해 알아보도록 하겠습니다.


1. 선형 검색 (Linear Search)

- 배열의 가장 좌측부터 시작하여 찾으려는 값과 하나씩 배열의 각 요소와 비교합니다.

- 찾으려는 값을 발견한다면 배열의 해당 인덱스를 반환(return)합니다.

- 찾으려는 값이 없다면 -1을 반환합니다.

- 시간복잡도 O(n)

- 이진 검색 및 해시 테이블과 같은 다른 검색 알고리즘이 훨씬 빠르기 때문에 실제로 거의 사용하지 않습니다.


- 소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int search(int arr[], int n, int x) { // 매개변수 : 배열이름, 배열의 길이, 찾으려는 값
 
    int i;
 
    for (i = 0; i < n; i++) { // 배열 전체 순차 탐색
 
        if (arr[i] == x) { // 찾는 값 발견
 
            return i; // 해당 위치(인덱스) 반환
 
        }
 
    }
 
    return -1// 찾으려는 값을 발견하지 못하면 -1 반환
 
}
cs



2. 이진 검색 (Binary Search)

- 검색 반경을 반으로 나눠어 반복하는 검색 방법입니다.

- 정렬 된 배열에서 사용 가능합니다.

- 찾으려는 값을 배열의 중간값과 비교하여 그 값이 더 작다면 우측 배열, 크다면 좌측 배열로 이동하여 반복

- 시간 복잡도 O(log n)


- 소스코드


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
int binarySearch(int arr[], int l, int r, int x) { // 매개변수 : 배열이름, 배열 시작 인덱스, 배열 끝 인덱스, 찾으려는 값
 
   if (r >= l) 
 
   { 
 
        int mid = l + (r - l)/2// 중간 값 선택
 
        if (arr[mid] == x) // 비교하여 찾는 값이라면
 
            return mid; // 해당 인덱스 반환
 
 
        if (arr[mid] > x) // 찾으려는 값보다 크다면
 
            return binarySearch(arr, l, mid-1, x); // 좌측 배열 탐색
 
 
        return binarySearch(arr, mid+1, r, x); // 우측 배열 탐색
 
   }
 
   return -1;  // 찾으려는 값이 없다면 -1 반환
 
cs


- C++ STL에서는 이진 검색을 라이브러리로 제공합니다.

- binary_search(시작위치, 끝위치, 찾으려는값) 식으로 사용합니다.

- lower_bound는 찾으려는 값이 여러개 존재할 때 사용합니다. (upper_bound는 큰 인덱스를 반환)

- 배열(또는 리스트) 안에 찾으려는 값이 1개(단일) 존재한다면 해당 값의 인덱스를 반환합니다.

- 배열 안에 찾으려는 값이 2개 이상 존재한다면 해당 값 중 가장 앞쪽(낮은) 인덱스(num of first position)를 반환합니다.

- 배열 안에 찾으려는 값이 없을 경우 찾으려는 값 다음 위치의 인덱스를 반환합니다.

- 자바에서 Array.binarySearch() 또는 Collections.binarySearch()을 라이브러리로 사용할 수 있습니다.

- 만약 자바에서 이진 탐색을 사용하려면 전에 Array.sort() 메소드를 호출하여 배열을 정렬할 필요가 있습니다.




※ 배열 또는 리스트에서 최소값, 최대값 검색

- 정렬된 배열 또는 리스트에서는 양쪽 끝 값이 최소값 또는 최대값입니다.

- Divide and Conquer를 사용하여 O(log n) 시간에서 최소값 또는 최대값을 구할 수 있습니다.


- 소스코드


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
int findPeakUtil(int arr[], int low, int high, int n) 
 
 
    int mid = low + (high - low)/2
 
 
    if ((mid == 0 || arr[mid-1<= arr[mid]) && 
 
            (mid == n-1 || arr[mid+1<= arr[mid])) 
 
        return mid; 
 
 
    else if (mid > 0 && arr[mid-1> arr[mid]) 
 
        return findPeakUtil(arr, low, (mid -1), n); 
 
 
 
    else return findPeakUtil(arr, (mid + 1), high, n); 
 
 
 
int findPeak(int arr[], int n) 
 
 
    return findPeakUtil(arr, 0, n-1, n); 
 
cs



이상 ''에 대해 알아보았습니다.

질문 또는 오타나 잘못된 정보가 있는 경우 댓글로 달아주세요!

메인 페이지로 이동하시면 더 많은 자료를 볼 수 있습니다.





'자료구조, 알고리즘' 카테고리의 다른 글

[BOJ] 8979 올림픽 - 문제 풀이  (1) 2019.03.29
정렬 알고리즘 종류  (0) 2018.09.12
자료구조 그래프(Graph)  (1) 2018.09.06
자료구조 힙(Heap)  (0) 2018.09.05
자료구조 이진 탐색 트리(Binary Search Tree)  (0) 2018.09.01
자료구조 트리(Tree)  (0) 2018.08.30
[자료구조] 큐 QUEUE  (0) 2018.08.19
[자료구조] 스택 STACK  (0) 2018.08.19


자바에서 NullPointerException은 RuntimeException입니다. 특수한 널 값은 객체 참조에 할당할 수 있습니다. 

프로그램에 널값을 가지는 객체 참조를 사용하려고하면 NullPointerException이 throw됩니다.


null에 대해

- null이란 아무것도 없음을 의미합니다.(0또는 공백 : "")

- 모든 참조유형에 대한 기본 값은 null입니다.

- null은 유효한 객체 인스턴스가 아니므로 할당 되는 메모리가 없습니다.


+ 예외가 발생하는 경우

- null 객체에서 method를 호출하는 경우

- null 객체의 필드에 접근하거나 값을 변경하는 경우

- null 의 길이를 배열처럼 취하는 경우

- null 을 throw 하는 경우

- null 을 통해 동기화 할 경우


+ 그럼에도 null 값이 필요한 이유? 

- 널은 자바에서 사용되는 특수 값입니다. 주로 참조 변수의 값이 할당되지 않았음을 나타내는데 사용됩니다.

- Null Object 패턴(로그 시스템) 및 Singleton 패턴에 사용됩니다.

- 연결된 목록 및 트리와 같은 데이터 구조를 구현하는 데 사용됩니다.


+ NullPointerException을 피하는 방법

1. 문자열 비교 : String 변수와 리티럴문자를 비교할 때 다음과 같은 오류가 발생할 수 있습니다.


String ptr = null;

if (ptr.equal("abc") // NullPointerException 발생!

{

System.out.println("SAME!");

}

else

{

System.out.println("NOT SAME!");

}


이는 다음과 같이 null객체 대신 리터럴문자에서 equal 메소드를 호출함으로써 해결할 수 있습니다.


String ptr = null;

if ("abc".equals(ptr))

{

System.out.println("SAME!");

}

else

{

System.out.println("NOT SAME!"); // "NOT SAME" 출력

}


2. try - catch문 사용 : 다음과 같이 예외처리문을 사용가능합니다.


public class Main {

public static void main(String[] arg) {

String s = null; 

try

System.out.println(getLength(s)); 

catch(IllegalArgumentException e) 

System.out.println("IllegalArgumentException caught"); // 예외처리 발생!!

}

public static int getLength(String s) 

if (s == null) 

{

throw new IllegalArgumentException("The argument cannot be null");

}

return s.length(); 

}


3. 삼항 연산자 사용 : null 값은 == 또는 != 의 연산자가 적용되기 때문이 이를 이용하여 다음과 같이 코드를 작성할 수 있습니다.


public class Main {

public static void main(String[] arg) {

String s = null; 

System.out.println(s.length()); // NullPointerException 발생!!

        

}


위 코드를 아래와 같이 수정합니다.


public class Main {

public static void main(String[] arg) {

String s = null; 

System.out.println((s == null) ? "0" : s.length()); // "0" 출력

        

}


이상 java.lang.NullPointerException에 대해 알아보았습니다.

자바 예외에 대해 더 알고싶은 분은 여기를 참고하세요.

또한 본 게시글에 대한 오류나 질문사항은 아래 댓글로 남겨주세요.

공감♡ 버튼을 눌러주시면 더욱 유용하고 좋은 포스팅으로 찾아 뵙겠습니다.


to Top