본문 바로가기

2015/07

THE100YEARSWAR 백년전쟁 풀이 문제: https://algospot.com/judge/problem/read/THE100YEARSWAR 문제 해석 1,2번 왕을 제외한 모든 귀족은 종신 관계를 가지고 있으며 입력에서 종신관계의 순서는 임의의 순서로 들어오나 결국에는 1,2번을 루트로 한 두개의 트리가 완성된다. 들어오는 순서가 임의이기 때문에 입력을 받으면서 전처리는 불가능하다. 모든 입력을 다 받고 난 뒤에 전처리를 행해야 한다. 한 귀족이 배신을 하면 그 귀족 아래의 모든 귀족이 배신을 한다. 즉 그 배신하는 귀족을 루트로하는 부분트리내 모든 노드가 배신을 한다. 입력 받기 예를 들면 귀족이 총 19명이고 1~19번 귀족=노드의 입력이 이런 형태로 들어왔다고 합시다. 이러한 트리 구조를 받을 수 있는 자료형을 먼저 만들어야 합니다.. 더보기
[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 더보기
비트마스크 사용법 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=백만*억개이.. 더보기