Hello World

여러가지 비트 연산 최하위 비트 구하기 : 2의 보수의 특징을 활용함. [연산 방법] 1 num & (-num) cs [예제 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include int main() { //0000 1010 int num = 10; //0000 0010 int result = num & (-num); //output printf("%d\n", result); return (0); } cs 다음 비트가 처음으로 0이 나오는 자리 구하기 [연산 방법] 1 ((num ^ (num + 1)) + 1) / 4 cs *중간에 0이 없을 경우 최상위 비트를 반환함. [예제 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include int main()..

비트마스크 비트마스크란? 내부적으로 이진수를 사용하는 컴퓨터는 이진법 관련 연산을 빨리 진행할 수 있다. 이런 특성을 이용해 정수의 이진수 표현을 자료 구조로 쓰는 기법을 비트마스크(bitmask)라고 한다. 보통은 집합에서 주로 쓰인다. 비트마스크의 장점 빠른 속도 비트마스크 연산은 O(1)에 구현되는 것이 많기 때문에 적절히 사용한다면 다른 자료구조들에 비해 빨리 동작한다. 비트마스크를 사용한다는 것은 애초에 원소의 개수가 많지 않다는 것을 의미하긴 하지만 같은 연산을 여러번 수행해야 할 경우에는 이런 사소한 차이가 큰 속도 향상을 가져올 수 있다. * int(정수형) = 4 Bytes = 32 bits 간결한 코드 다양한 집합 연산들을 배열이나 반복문을 쓸 필요 없이 한 줄에 쓸 수 있기 때문에 비..

탐욕 알고리즘 Greedy Algorithm 탐욕 알고리즘이란? 최적화 문제를 해결하는 알고리즘으로 근시안적인 방법이다. 그 순간이 최적이라고 생각되는 것을 선택해 나가는 방식이다. 각 결정은 지역(local)적으로는 최적이나, 전체(global)적으로 봤을 때 최적이라는 보장은 없다. 대표 문제 동전 문제 배낭 문제 활동 선택 문제(회의실 배정) ... 동전 문제 Q. 어떻게 거스름돈의 개수를 최소한으로 줄일 수 있을까? [접근방법] 그 당시 거슬러줄 수 있는 가장 큰 액수의 동전을 선택한다. coin = 0 이면 종료 coin > 0 이면, coin보다 작거나 같은 동전 중 가장 큰 동전(m)을 선택 coin = coin - m 1~3 반복 *그러나 이 방법은 모든 coin system에서 동작한다는..

Lower Bound와 Upper Bound 일종의 이분 탐색(binary search) 오름차순으로 정렬되어 있을 때를 가정한다. Lower Bound -정렬된 숫자들 중에 목표값이 처음 등장하는 인덱스 값을 반환한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int lower_bound(int *arr, int key, int size) { int mid, left, right; left = 0; right = size - 1; while (left = key) right = mid; else left = mid + 1; } return right; } Colored by Color Scripter cs Upper Bound -정렬된 숫자들 중에 목표값보다 높은 숫자가 처음 등장하는..

이분 탐색 Binary Search 이분 탐색의 개념과 특징 이분 탐색(혹은 이진 탐색)은 이미 정렬된 배열에 대해 log₂N의 평균 검색 길이를 갖는 매우 빠르고 간단한 알고리즘이다. 기본 알고리즘 구간에 대해 중간값을 우선 검사한다. 중간값보다 작다면 찾는 값은 왼쪽 구간에 있다. (right = mid-1) 중간값보다 크다면 찾는 값은 오른쪽 구간에 있다. (left = mid+1) 중간값과 같다면 종료 구간을 줄여가며 1~3을 반복한다. 예제 정렬된 배열에 대해 목표값 9를 찾고자 한다. Search 1. left = 0(인덱스 위치) right = 8 mid = (0+8)/2 = 4 >>7(중간값)은 목표값 보다 작으므로 구간을 오른쪽으로 옮긴다. >>left = mid + 1 Search 2...