본문 바로가기

프로그래밍/알고리즘

[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 더보기
비트마스크 사용법 8개의 비트를 사용하고자 한다. int bitmask를 비트마스크 변수로 선언한다. 비트는 맨 오른쪽 비트가 0번 비트고 총 8개 비트면 0~7의 범위를 갖는다. bitmask 변수의 우측 8개 비트만 사용한다는 것이다. 비트 상태가 0인것을 꺼져있다고 하고 1인것을 켜져있다고 한다. 이때 n번 비트가 켜진 상태는 시프트 연산 1 더보기
조합, 이항계수 계산 코드 #include #define MAX 200 unsigned int C[MAX + 1][MAX + 1] = { 0 }; void calcBino() { //이항계수 계산 for (int i = 0; i 더보기
독이 든 술 단지를 찾아라 옛날 어느 먼 나라에 술을 매우 즐겨 마시는 왕이 살고 있었다.어느 날 이웃 나라의 암살자가 창고에 들어가서 술 단지 하나에 독을 넣고 나오다가 붙잡혔다. 암살자는 어느 단지인지는 모르지만 하나의 단지에만 독을 넣었다고 실토하고는 숨을 거두었다. 사용된 독의 특징은 식별이 불가능 하며 사람에게만 독성이 있고독이든 단지의 술을 아주 조금만 맛보아도 술을 맛 본 사람이 자고 일어난 다음날 죽는다.왕은 독이든 술 단지를 반드시 내일까지 찾아내라고 실력있는 책략가인 당신에게 명하였다.당신은 투옥된 죄수들을 다음날 살아 남으면 석방을 시켜주는 조건으로 실험에 동원 할 수 있다.될 수 있으면 최소한의 죄수들을 동원하고자 한다. 창고에 128개의 술 단지가 있고 그 중 하나의 단지에 독이 들어 있을 때내일까지 독이 .. 더보기
트리 최적 노드 삽입 순서 #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 더보기
이클립스 유용 플러그인들 한글 패치http://ftp.kaist.ac.kr/eclipse/technology/babel/update-site/http://ftp.kaist.ac.kr/eclipse/technology/babel/update-site/R0.12.1/juno/http://ftp.kaist.ac.kr/eclipse/technology/babel/update-site/R0.12.1/kepler/http://ftp.kaist.ac.kr/eclipse/technology/babel/update-site/R0.12.1/luna/ CDThttp://ftp.kaist.ac.kr/eclipse/tools/cdt/releases루나 http://ftp.kaist.ac.kr/eclipse/tools/cdt/releases/8.6/ 코.. 더보기
완전 좌우 대칭인 시간 찾는 문제 2015-01-11 10:51:022015-01-22 10:51:022015-02-11 20:51:022015-02-22 20:51:022015-10-11 01:51:022015-10-22 01:51:022015-11-11 11:51:022015-11-22 11:51:022015-12-11 21:51:022015-12-22 21:51:02 위와 같이 14개 숫자로 이루어진 시간이앞 7개 뒷 7개가 대칭을 이루는 시간을 완전 좌우 대칭인 시간이라고 할때1970-01-01 00:00:00 부터 9999-12-31 23:59:59 까지 시간중에완전 대칭인 시간은 몇개가 있을까? 14개 숫자가 0~9까지 가능하다고 할때 체크해봐야 하는 경우의 수는 10의 14승즉 100,000,000,000,000=백만*억개이.. 더보기
[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.. 더보기
[Java] 창작 스도쿠 푸는 알고리즘 이 알고리즘으로 UI를 구현한 Sudoku solver는 http://sunnyholic.com/100 여기 있습니다. C++로 동일하게 작성한 코드는 http://sunnyholic.com/81 입니다. 빈 칸중 들어갈 수 있는 수의 경우가 제일 적은 칸을 선택하여 수를 삽입한 뒤 재귀적으로 풀고 오답이면 백트래킹 하고 정답이 나오면 종료하는 알고리즘 입니다. 함수 메인 제외 5개 1. 생성자 함수 : 간편하게 행 열 섹터를 순차적으로 순회하기 위해 미리 순회 순서를 찾아놓음. 2. sizeofNumset(Set set) : 가능한 숫자 셋트에서 그 숫자들을 세어 개수를 리턴 3. findAblNum(int rn,int cn) : (rn,cn)칸에 가능한 숫자 셋트 리턴 4. findMinPossibl.. 더보기