코딩소년 - 기술블로그

값에 의한 전달 (Passing by Value)

인자를 복사해서 전달한다.

시간복잡도 O(n)이 추가되는 격이니, 값에 의한 전달은 좋은 방법이 아니라는 생각이 든다.

함수 안에서 복사본들 변경해도 함수를 호출한 곳의 원본은 변경되지 않는다.

포인터에 의한 전달  (Passing by Pointer)

함수 안에서 주소를 통해 함수를 호출한 곳의 원본에 접근한다.

나도 주로 값을 전달할 때 포인터를 활용하여 전달을 많이 사용하였다.

레퍼런스에 의한 전달 (Passing by Reference)

레퍼런스에 의한 전달은 C에서는 없는 C++의 특징이다.

출력인자, 입출력 인자 전달 시 사용 된다.

헷갈릴 수 있는데, 함수의 인자에 &(레퍼런스)이 붙으면 레퍼런스에 의한 전달이고

*(포인터)가 붙으면 포인터에 의한 전달이라고 이해하면 되겠다.

이진탐색 알고리즘은 기본적으로 O(log n)의 시간복잡도를 가진다.

O(1) (constant time complexity) 다음 가장 빠른 시간복잡도가 O(log n)이기 때문에,

상당히 빠른 알고리즘에 속한다. 그리고 아무리 생각해도 정말 효율적이다.

10개의 숫자가 정렬이 되어있다고 가정해보자.

10 20 30 40 50 60 70 80 90 100 

여기서 30의 숫자를 찾으려고 한다면,

이진탐색 알고리즘으로 처음에 중간 값인 50을 비교하고 30은 50보다 작기 때문에 

50의 오른쪽 부분은 더 이상 볼 필요가 없어진다.

이제 끝점을 초기의 중간 값의 왼쪽으로 한 칸 옮긴다.

10 20 30 40 

이제 중간 값이 20이 된다. 

30은 20 보다 커서, 10과 20이 필요 없어진다.

30과 40이 남고 이제 중간 값인 30 = 30 이 되어서

총 3번의 Step만으로 목표로 하는 숫자를 찾았다.

C++로 작성된 이진 탐색 소스코드는 아래와 같다.

#include <iostream>
#include <vector>

using namespace std;

// 벡터 레퍼런스를 넘겨줘야한다. 
// 앰퍼샌드를 빼면, 그대로 Copy하기 때문에 시간복잡도가 O(n)이 된다.
int binarySearch(vector<int> &arr, int target, int start, int end)
{
	while (start<=end)
    {
    	int mid = (start+end)/2;
        if (arr[mid] == target) return mid;
        // 찾는 target이 중간값보다 작으면 왼쪽으로 탐색
        else if (arr[mid] > target) end = mid -1;
        // 찾는 target이 중간값보다 크면 오른쪽으로 탐색
        else start = mid +1;
    }
    return -1;
}

int n, target;
vector<int> arr;

int main()
{
    // 전체 원소의 개수 n, 찾고자 하는 값 target 입력 받기  
    cin >> n >> target;
    
    // 전체 원소 입력받기 
    for(int i=0; i<n; i++)
    {
    	int x;
        cin >> x;
        arr.push_back(x);
    }
    
    //이진 탐색 수행결과 출력
    int result = binarySearch(arr, target, 0, n-1);
    if (result == -1)
    {
    	cout << "원소가 존재하지 않습니다." << '\n';
    }
    else
    {
    	cout << result + 1 << '\n';
    }
    return 0;
}

IPC (Inter-Process Communication) 란?

프로세스간 통신의 줄임말이다.

IPC의 종류 

• 메세지큐
• 공유메모리
• 세마포어
• pipe (named pipes, Anonymous pipes)
• Regular Files with Locking
• Sockets
• Signals