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 간결한 코드 다양한 집합 연산들을 배열이나 반복문을 쓸 필요 없이 한 줄에 쓸 수 있기 때문에 비..

버블 정렬 Bubble Sort 버블 정렬이란? 버블 정렬은 배열의 인접 요소(adjacent element)를 비교하여 교환하는 모양이 마치 거품이 움직이는 모양이라고 해서 붙여진 이름이다. 인접한 두 개의 배열 요소를 비교 및 교환하여 최댓값을 제일 뒤로 보내는 전략이다. 구현은 간단하나 그에 비해 속도는 느린 편이다. 정렬 예시 Code / C언어 기반 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 33 34 35 36 37 38 39 40 41 42 43 #include #include #include #define SIZE 10 int arr[SIZE]; //Print Array void..

탐욕 알고리즘 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...

트리 Tree 트리의 개념과 특징 DAG(Directed Acyclic Graphs) 방향성 있는 비순환 그래프 loop x, circuit x 노드(node 혹은 vertex)와 링크(link 혹은 edge)의 집합 트리에서 한 노드에서 다른 노드로 가는 경로(path)는 유일하다. N개의 노드를 가지는 나무는 N-1개의 링크를 가진다. 종류 : 이진트리(binary tree), B 트리, 힙(heap), 세그먼트(segment) 등등 트리의 기본 구조 루트 Root : 트리의 제일 위에 있는 노드 경로 Path : 트리 내에서 연결된 노드를 통해 이동할 때의 이동 경로(path는 오직 하나) 자식 노드 children, 부모 노드 parent : 직접 연결되어 있으면서 아래에 있다면 자식, 위에 있다..

선택 정렬 Selection Sort 선택 정렬이란? 최소 혹은 최댓값부터 찾아 정렬하는 방법 다른 정렬들에 비해 비교적 쉽게 구현이 가능하다. (오름차순일 때) 첫 인덱스부터 정렬하는 방법으로 기준으로부터 오른쪽 값들과 비교하여 가장 작은 수를 찾아 값을 교환한다. -핵심코드 1) A와 B의 값을 교환 tmp = A; A = B; B = tmp; 2) for문의 범위 설정 for( i=0; i < SIZE -1; i++){ for( j=i+1 < SIZE; j++){ ... } } 바깥 for 문 현재 기준 인덱스를 가리키는 역할 범위는 SIZE-1까지(SIZE-1까지 정렬하면 마지막은 정해지기 때문) 내부 for 문 최소(혹은 최대) 값을 찾는 역할 범위는 기준+1부터 SIZE까지 정렬 예시 선택 정..

스택 Stack 스택이란? 스택이나 큐, 트리와 같은 자료구조는 자신이 행위적 측면을 포함하는 자료구조이다. 이런 자료 구조는 제한된 접근 방식을 규정하고 있으며 이를 추상적 자료 구조(Abstrct Data Structure)라고 한다. 스택은 제일 나중에 들어간 것이 제일 먼저 나오는 LIFO(Last In First Out) 구조로 배열이나 연결 리스트(Linked List)로 구현할 수 있다. 배열로 구현하기는 쉽지만 처음에 스택의 크기를 지정해줘야 한다는 단점이 있고, 연결 리스트는 크기를 동적으로 할당하기 때문에 용량에 대해서는 제한(최대 메모리까지)이 없지만 구현하기는 비교적 어렵다는 단점이 있다. 스택의 구성 스택은 기본적으로 데이터를 삽입할 수 있는 push와 스택에서 데이터 하나를 빼내..