본문 바로가기

프로그래밍/알고리즘/C++

[C++ STL] 동적 2차원 배열 사용법(vector) //int arr[6][5] 배열 선언. 0으로 값 초기화vector arr(6, vector(5, 0)); //값 삽입int serial = 0;for (int i = 0; i >랑 구분해 주기 위해 중간에 공백을 꼭 넣어주세요. 사용벡터는 연속된 공간에 할당하는 자료형이기 때문에 일반 배열처럼 사용해도 됩니다.맨 위 코드에 값 삽입 부분을 보시면 됩니다. C++11 이상 배열 생성 초간편 방법vector arr({ vector( { 0, 1, 2.. 더보기
[C++] 구간트리 (Binary Indexed Tree) - 구간 최대,최소값 struct IndexedTree { vector tree; int size; IndexedTree(int n, int *arr) : tree(4 * n, 987654321) { //넉넉하게 4*n 사이즈 배열 생성, 초기값 지정 size = 1; while (size right) return 987654321; //초기값 if (left == nodeLeft && right == nodeRight) return tree[node]; int mid = (nodeLeft + nodeRight) / 2; return min(query(left, right, node * 2, nodeLeft, mid), query(left, right, node * 2 + 1, mid + 1, nodeRight)); } vo.. 더보기
[C++] 펜윅트리 (이진 인덱스 트리) - 구간합 구해주는 트리 struct FenwickTree { vector tree; FenwickTree(int n) : tree(n + 1) {} inline int sum(int pos) { ++pos; int ret = 0; while (pos > 0) { ret += tree[pos]; pos &= (pos - 1); } return ret; } inline void add(int pos, int val) { ++pos; while (pos < (int) tree.size()) { tree[pos] += val; pos += (pos & -pos); } }}; 사용법생성자 FenwickTree fenwickTree(n) : n은 들어갈 노드의 개수int sum(int pos) : 0번~pos번째까지의 합을 구해준다.(내.. 더보기
[C++] 비트 마스크 배열 (큰 비트 마스크) #include #include //gcc의 경우 해제 #include #define SIZE 3 #define BLOCK 32 //모두 끄기 inline void clear(int *bitmask){ memset(bitmask,0,sizeof(bitmask)); } //n번 비트 켜졌는지 inline int isOn(int *bitmask,int n){ return (bitmask[n/BLOCK]&(1 더보기
트리 최적 노드 삽입 순서 #include void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp;}void bubble_sort(int *array, int size) { for (int i = size - 1; i >= 0; i--) for (int j = 0; j array[j + 1]) swap(&array[j], &array[j + 1]);}void best_way(int* array, int from, int size) { if (from == size) return; int center=(from + size) / 2; printf("%d ", array[center]); best_way(array, from, center); best_way(array, cent.. 더보기
버블 정렬 알고리즘 오름차순 #include void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp;}void bubble_sort(int *array, int size) { for (int i = size - 1; i >= 0; i--) for (int j = 0; j array[j + 1]) swap(&array[j], &array[j + 1]);}int main() { int sample[10] = { 2, 6, 7, 7, 9, 3, 5, 9, 1, 3 }; for (int i = 0; i 더보기
[C++] 창작 스도쿠 푸는 알고리즘 이 알고리즘으로 UI를 구현한 Sudoku solver는 http://sunnyholic.com/100 여기 있습니다. 자바로 동일하게 작성한 코드는 http://sunnyholic.com/80 입니다. 비트마스크로 최적화 한 코드는 글의 맨 아래를 봐주세요. 빈 칸중 들어갈 수 있는 수의 경우가 제일 적은 칸을 선택하여 수를 삽입한 뒤 재귀적으로 풀고오답이면 백트래킹 하고 정답이 나오면 종료하는 알고리즘 입니다.C처럼 보이지만 C문법을 따르진 않았습니다. 함수 메인 제외 5개1. init() : 간편하게 행 열 섹터를 순차적으로 순회하기 위해 미리 순회 순서를 찾아놓음.2. sizeofNumset(Set set) : 가능한 숫자 셋트에서 그 숫자들을 세어 개수를 리턴3. findAblNum(int rn.. 더보기