TWpower Reading time ~1 minute

이분 탐색에서 index를 이동할 때 좌우를 어떻게 비교하면서 이동하는지 확인해보자.


환경 및 선수조건

  • C++


원리

  1. 찾고자 하는 값을 x라 하고 배열을 a라 하자.
  2. 배열의 제일 왼쪽 인덱스를 Left 제일 오른쪽 인덱스를 Right라고 하자.
  3. Middle = (Left) + (Right - Left)/2라고 하자.
  4. left <= right를 만족하면 아래를 반복한다.
  5. x > a[Middle] 이면 Left = Middle + 1를 하고 그게 아니면 Right = Middle - 1를 한다.
  6. 다시 3으로 돌아간다.


기본 코드

  • 코드
while(left <= right){

	int middle =  left + (right - left)/2;

	if(a[middle] == x){
		// 배열에서 찾고자 하는 x의 위치가 position에 저장
		positoin = middle;
		break;
	}
	else if(a[middle] > x){
		right = middle - 1;
	}

	else{
		left = middle + 1;
	}
}


예제 코드

  • 코드
#include <stdio.h>

int main (){


	// 정렬이 되어있어야함
	int a[20] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};


	int left = 0; // 제일 왼쪽 인덱스
	int right = sizeof(a)/sizeof(int); // 제일 오른쪽 인덱스
	int x = 3; // 값 3이 배열에서 위치한 인덱스를 찾고자 한다면
	int position = -1;

	while(left <= right){

		int middle =  left + (right - left)/2;

		if(a[middle] == x){
			// 배열에서 찾고자 하는 x의 위치가 position에 저장
			position = middle;
			break;
		}
		else if(a[middle] > x){
			right = middle - 1;
		}

		else{
			left = middle + 1;
		}
	}

	printf("%d\n", position);

}


참고자료

TWpower Reading time ~1 minute

업데이트(2018.04.17): memset 함수를 사용하는 이유 및 참고자료 추가

C와 C++에서 memset 함수를 사용해보자


환경 및 선수조건

  • C, C++


목적

  • memset함수는 어떤 메모리의 시작점부터 연속된 범위를 어떤 값으로(바이트 단위) 모두 지정하고 싶을 때 사용하는 함수이다.


기본 함수 구조 및 매개변수

void * memset ( void * ptr, int value, size_t num );
  • ptr: 채우고자 하는 메모리의 시작 포인터(시작 주소)
  • value: 메모리에 채우고자하는 값. int형이지만 내부에서는 unsigned char(1 byte)로 변환되어서 저장된다.
  • num: 채우고자 하는 바이트의 수. 즉, 채우고자 하는 메모리의 크기


코드

  • 코드
#include <string.h> // string.h 파일이 필요합니다.
#include <stdio.h>

int main (){

    char a[20];

    // 1바이트마다 모두 65로 초기화
    // 배열을 채울 때는 sizeof()함수를 사용하면 됩니다.
    // sizeof 함수 - 배열의 전체 바이트 크기를 반환합니다.
    memset(a, 65, sizeof(a));

    // 출력을 통해 확인
    for(int i = 0; i < (sizeof(a)/sizeof(char)); i++){
        printf("%c\n", a[i]);
    }

}


memset 함수를 사용하는 이유

  • 대체로 memset함수는 특정 범위에 있는 연속된 메모리에 값을 지정하고 싶을 때 사용하는데 for문보다 더 빠른 속도가 나올수가 있다.
  • 여기서 나올수가 있다라고 표현한 이유는 컴파일러 그리고 컴퓨터 아키텍처에 따라서 다르기 때문이다.
  • 자세한 내용은 아래 두 참고자료를 보면 Quora에는 어셈블리 코드로 비교한게 나와있고 Stack Overflow에는 관련한 내용들이 나와있다.


참고자료

TWpower Reading time ~1 minute

C++에서 list 사용법을 간단하게 알아보자


환경 및 선수조건

  • C++


리스트 기본 함수

iterator(반복자)

  • begin(): beginning iterator를 반환
  • end(): end iterator를 반환

추가 및 삭제

  • push_front(element): 리스트 제일 앞에 원소 추가
  • pop_front(): 리스트 제일 앞에 원소 삭제
  • push_back(element): 리스트 제일 뒤에 원소 추가
  • pop_back(): 리스트 제일 뒤에 원소 삭제
  • insert(iterator, element): iterator가 가리키는 부분 “앞”에 원소를 추가
  • erase(iterator): iterator가 가리키는 부분에 원소를 삭제

조회

  • *iterator: iterator가 가리키는 원소에 접근
  • front(): 첫번째 원소를 반환
  • back(): 마지막 원소를 반환

기타

  • empty(): 리스트가 비어있으면 true 아니면 false를 반환
  • size(): 리스트 원소들의 수를 반환


구현 코드

#include <iostream>
#include <list>

using namespace std;

int main(){

	list<int> l;


	// push_back
	l.push_back(5);
	l.push_back(6);
	l.push_back(7);
	l.push_back(8);
	l.push_back(9);
	l.push_back(10);


	// pop_back
	l.pop_back();


	// push_front
	l.push_front(4);
	l.push_front(3);
	l.push_front(1);
	l.push_front(0);


	// pop_front
	l.pop_front();


	// back and front
	cout << "list front value: " << l.front() << '\n';
	cout << "list end value: " << l.back() << '\n';


	// size
	cout << "list size: " << l.size() << '\n';


	// empty
	cout << "Is it empty?: " << (l.empty() ? "Yes" : "No") << '\n';


	// iterator
	list<int>::iterator begin_iter = l.begin(); // auto begin_iter = l.begin()도 가능
	list<int>::iterator end_iter = l.end(); // auto end_iter = l.end()도 가능


	// insert
	begin_iter++; // 2번째를 가리키는 iterator
	l.insert(begin_iter, 2);


	// erase
	end_iter--; // 마지막 원소를 가리키는 iterator
	l.erase(end_iter);


	// *iterator: 원소 접근
	cout << "list "<< distance(l.begin(), begin_iter)+ 1 << " element: " << *begin_iter << '\n';

	return 0;

}


참고자료

TWpower Reading time ~1 minute

업데이트(2019.04.22): iterator를 이용한 for문 예제 추가

C++에서 vector 사용법을 간단하게 알아보자


환경 및 선수조건

  • C++


벡터 기본 함수

iterator(반복자)

  • begin(): beginning iterator를 반환
  • end(): end iterator를 반환

추가 및 삭제

  • push_back(element): 벡터 제일 뒤에 원소 추가
  • pop_back(): 벡터 제일 뒤에 원소 삭제

조회

  • [i]: i번째 원소를 반환
  • at(i): i번째 원소를 반환
  • front(): 첫번째 원소를 반환
  • back(): 마지막 원소를 반환

기타

  • empty(): 벡터가 비어있으면 true 아니면 false를 반환
  • size(): 벡터 원소들의 수를 반환

배열과의 차이

  • 동적으로 원소를 추가할 수 있으며 크기가 자동으로 늘어난다.


구현 코드

#include <iostream>
#include <vector>

using namespace std;

int main(){

	vector<int> v;


	// push_back
	// 1-2-3-4-5
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);


	// pop_back
	v.pop_back();


	// back and front
	cout << "vector front value: " << v.front() << '\n';
	cout << "vector end value: " << v.back() << '\n';


	// [i] and at(i)
	cout << "vector opeartor[]: " << v[3] << '\n';
	cout << "vector at: " << v.at(3) << '\n';


	// size
	cout << "vector size: " << v.size() << '\n';


	// empty
	cout << "Is it empty?: " << (v.empty() ? "Yes" : "No") << '\n';


	// iterator
	vector<int>::iterator begin_iter = v.begin(); // auto begin_iter = v.begin()도 가능
	vector<int>::iterator end_iter = v.end(); // auto end_iter = v.end()도 가능

	// get value by iterator
	cout << "vector begin value: " << *begin_iter << '\n';

	// for statement iteration using iterator
	for(vector<int>::iterator iter = v.begin(); iter != v.end(); iter++){
		cout << *iter << ' ';
	}
	cout << endl;

	return 0;

}


참고자료

TWpower Reading time ~1 minute

C++에서 queue 사용법을 간단하게 알아보자


환경 및 선수조건

  • C++


큐 기본 함수

추가 및 삭제

  • push(element): 큐에 원소를 추가(뒤에)
  • pop(): 큐에 있는 원소를 삭제(앞에)

조회

  • front(): 큐 제일 앞에 있는 원소를 반환
  • back(): 큐 제일 뒤에 있는 원소를 반환

기타

  • empty(): 큐가 비어있으면 true 아니면 false를 반환
  • size(): 큐 사이즈를 반환


구현 코드

#include <iostream>
#include <queue>

using namespace std;

int main(){

	// 큐 생성
	queue<int> q;


	// push
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	q.push(6);


	// pop
	q.pop();
	q.pop();
	q.pop();


	// front
	cout << "front element: " << q.front() << '\n';


	// back
	cout << "back element: " << q.back() << '\n';


	// size
	cout << "queue size: " << q.size() << '\n';


	// empty
	cout << "Is it empty?: " << (q.empty() ? "Yes" : "No") << '\n';

	return 0;

}


참고자료