안녕하세요!

프로그래밍에 관심이 많은 Jang입니다.
부족하지만 발전하는 블로거가 되도록 하겠습니다. ^^


댓글

댓글 쓰기

이 블로그의 인기 게시물

[C++] bool을 담은 vector가 foreach에서 동작하지 않는 이유

이미지
vector<bool>를 foreach에서 사용하려다가 컴파일 오류가 발생했다. 다른 primitive type, object type 에서는 발생하지 않아서 신기함을 느끼고 찾아보게 되었다. bool은 바이트 단위로 표현하면 1byte라고 볼 수 있지만, 내부적으로는 1bit만 사용하게 되므로 나머지 공간을 사용하지 않아서 메모리 관점에서 비효율이 발생한다. (char는 1byte를 제대로 사용하는 것과 비교된다.) 'vector<bool>는 내부적으로 1byte에 여러 개의 bool 값을 저장한다. (dynamic bitset)' 라 는 답변이 가장 와닿았고, 이를 바탕으로 더 찾아보게 되었다. 메모리 공간 최적화로 인해서, 표준 컨테이너의 기능과 인터페이스를 다소 잃게 된다. vector<bool>에서 operator[]는 bit를 조작할 수 있는 프록시 객체를 반환하게 되는데, 프록시 객체는 bool &이 아니기 때문에, bool *에 주소를 할당할 수 없다는 것이다. 예) bool * b = & v[0];    //Compile Error  이와 대조적으로, deque는 이러한 특수화가 이루어지지 않으므로 bool은 1byte를 취하고, operator[]에서 반환된 값의 주소를 가져올 수 있다. (의도한 방향) Proxy Class는 다른 클래스에 원하는 인터페이스 사용 을 위해서 사용하는 대리자 역할을 한다. 위에 operator[]처럼 1bit(0과 1)만 사용하기를 원하는 경우, 이를 표현하게 해준다. https://stackoverflow.com/questions/994488/what-is-proxy-class-in-c (1) vector<bool>의 내부적 구현 => Proxy Object로 반환(rvalue) => 반복자(iterator)는 lvalue만 참조가능 => Compile Error! (2) vector<char>의 내부...
자세한 내용 보기

Hash Table의 의미와 중요성

우리가 코딩하면서, 가장 많이 사용하는 자료구조 개념은 무엇일까 생각해보았다. 또, 그 중 중요하면서 유용한 것이 무엇일까 생각해보았다. 배열(array) , 해시 개념을 사용한 맵(map) , 집합(set) 같은 자료구조가 아닐까 생각이 들었고, (트리를 이용한 map, set도 있기 때문에 '해시 개념을 사용한'이라고 하였다) 검색과 생각 끝에 공통적인 개념이 사용됨을 알았다. 해시 테이블의 개념을 살펴보면, key - value 를 이용하여 원하는 자료구조를 순차 탐색할 필요 없이 바로 찾아가는 것에 있다. 그리고 이를 흔히 말하는 상수 시간 O(1) 로 볼 수 있다. 먼저, 배열을 살펴보자. 배열은 정수(0, 1, 2, ... )를 이용해서 해당 위치에 있는 자료를 바로 불러올 수 있다. 이것은 key - value로 나타내면, int형을 갖는 key와 각기 다른 타입을 갖는 value로 볼 수 있다. 즉, 배열은 key가 정수인 해시 테이블 이라고 볼 수 있다. 그러면 배열을 선언하면, 내부적으로는 어떤 일이 일어날 것인지 추측해볼 수 있다. 일단, 배열의 원하는 원소에 바로 접근하려면, 기본 주소가 필요하다. 즉, 배열의 기본주소 Base Address를 저장할 변수가 필요하다. 다음으로는 value에 해당하는 자료형의 크기를 저장할 변수가 필요할 것이다. 왜냐하면, int 32형의 경우 4byte를, int 64형의 경우 8byte가 배열 한 칸을 움직이는 최솟값이 되기 때문이다. (배열의 해당 원소의 주소 = base address + offset, offset = sizeof(자료형) * index) 그럼 좀 더 확장하여, 해시 테이블에서 사용되는 모든 타입의 key 에 대해선 어떻게 계산할까? key가 string이라고 가정하면, 문자열 abc와 문자열 bca는 위의 인덱스 개념처럼 서로 다른 위치를 가르치게 해야 한다. 그러면, 이 문자열들을 각기 다른 key를 갖게 해야 하는데, 컴퓨터 내부적으로는 숫자 이진수 0과 1로 ...
자세한 내용 보기

비트 연산에 대한 간단한 활용

비트 연산을 사용하면 빠르거나 간결한 코드를 작성할 수 있다. 이 외에도 활용 방안은 무궁무진하다. 앞으로 생각나는대로 추가할 생각이다. * 2의 거듭제곱과 관련된 수를 곱하거나 나눌 경우에  Shift(>>, <<) 연산을 사용할 수 있다. Example a /= 2;      <->     a >>= 1; a *= 16;     <->     a <<= 4; * 나머지 연산을 And(&) 연산으로 대체할 수 있는 경우가 있다. 2^n - 1에 해당 하는 숫자보다 작으면, 이를 나머지 연산으로 사용할 수 있다. 왜냐하면 이진수로 나타내었을 때, 모든 자리의 숫자가 1이기 때문이다. Example b = 3, m = 4; if (b % 15)     <->     if (b & 15)     <->     if (b & ((1<<m)-1)) * 어떤 숫자가 2의 거듭제곱인지 알고 싶을 때 And(&) 연산으로 간단하게 확인 가능하다. Example if (n & (n-1) == 0)     return true; * Swap 기능을 XOR(^) 연산으로 대체할 수 있는 경우가 있다. 정수형으로 나타낼 수 있는 자료형일 때만 가능하다. Example tmp = a;          <->        a ^= b; a = b;                ...
자세한 내용 보기