본문 바로가기

2016/0917

유한차분법(finite difference method)에서 boundary exchange하기 가로가 n, 세로가 m인 배열 uu (이중배열은 아니고 이중배열처럼 쓰이는 일차 배열)의 boundary에서 정보 교환시void exchange_boundary(int m, int n, double *uu, int nprocs, int myrank){ int i,j; MPI_Request req[4]; MPI_Status stat[4]; if(myrank 0){ MPI_Isend(&.. 2016. 9. 28.
Project Euler #58 (Spiral primes) 문제는 https://projecteuler.net/problem=58 Spiral prime을 계산하여 10% 이하가 될 때를 구한다.간단한 문제이므로 코드에 대한 설명은 생략한다.#include #include #include #define RATIO 10 bool is_prime(int p) { int i; for (i = 2; i 2016. 9. 27.
Project Euler #55 (Lychrel numbers) 문제는 https://projecteuler.net/problem=5550회 이상 palindrome-sum-iteration을 돌려도 palindrome이 나오지 않는 Lychrel numbers에 대한 문제이다.#include #include #define ASIZE 30 #define MITER 50 void deep_copy(int n[], int m[]) { int i; for (i = 0; i = 0; i--) { if (m[i] != 0) { lim = i + 1; break; } } for (i = 0; i <.. 2016. 9. 19.
블록 분할코드 블록 분할 코드 예: Cvoid para_range(int n1, int n2, int nprocs, int myrank, int *ista, int *iend){ int iwork1, iwork2; iwork1 = (n2-n1+1)/nprocs; iwork2 = (n2-n1+1)%nprocs; *ista = myrank*iwork1 + n1 + min(myrank, iwork2); *iend = *ista + iwork1 - 1; if(iwork2 > myrank) *iend = *iend + 1; } 2016. 9. 13.
티스토리 블로그 노출 구글에 노출시키기: http://neogurihouse.tistory.com/11네이버에 노출시키기: http://neogurihouse.tistory.com/18 참고하세요. 2016. 9. 13.
블로그 배경이미지 변경했습니다 ㅎ 리아트 님이 그리신 "한 여름밤의 꿈"이란 작품이 마음에 들어 블로그 배경으로 해도 되는지 연락을 드렸더니 허락해 주셨습니다~ㅎㅎ 출처: http://www.grafolio.com/works/86934 아름답네요~ 2016. 9. 13.
LINUX에서! screenrc와 vimrc설정 내가 사용하는 .screenrc와 .vimrc이다. .screenrc: vbell off msgwait 3600 autodetach on startup_message off pow_detach_msg "Screen session of \$LOGNAME \$:cr:\$:nl:ended." defhstatus " ^EW" # [^EM/^Ed(^ED) ^Ec]" defscrollback 10000 termcapinfo xterm Z0=\E[?3h:Z1=\E[?3l:is=\E[r\E[m\E[2J\E[H\E[?7h\E[?1;4;6l termcapinfo xterm* OL=10000 termcapinfo xterm 'VR=\E[?5h:VN=\E[?5l' termcapinfo xterm 'k1=\E[11~:k2=\E.. 2016. 9. 12.
Project Euler #108 (Diophantine reciprocals I) 문제는 https://projecteuler.net/problem=108 x = n + t가 되는 t를 놓고 풀면y = n + n*n/t가 되고, 여기서 t는 n*n의 소인수가 된다. 이를 이용하여 가능한 t를 n*n 소인수 set에서 iteration시켜 x, y를 유도하고t가 size; i++) { r->pcount[i] = f->pcount[i]; } r->size = f->size; return r; } factor* factorize(int n) { int i, j, fsize = 0, sqrtn = sqrt(n); int pcount[P]; factor *f = init_factor(); for (i = 0; prime[i] 1) f->size = -1; else { f->pcount = (i.. 2016. 9. 9.
Project Euler #105 (Special subset sums: testing) 문제는 https://projecteuler.net/problem=105 이전에 problem 106에서 사용한 unclear함수를 사용한다. - 문제 106번 보기 그리고 arr은 일종의 3진법이라 생각하면 될 것이다. 아래는 코드이다. #ifdef _MSC_VER #define _CRT_SECURE_NO_WARNINGS #endif #include #include #define N 12 bool check_rule2(int num[N], int n) { int i; int sumB = 0, sumC = 0; for (i = 0; i sumC; } int co.. 2016. 9. 9.
Project Euler #106 (Special subset sums: meta-testing) 문제는 https://projecteuler.net/problem=106 문제를 해석하면 S(B) ≠ S(C); that is, sums of subsets cannot be equal.If B contains more elements than C then S(B) > S(C).에서 특정 set이 rule ii를 만족한다는 가정하에 해당 set이 special한지를 확인하려면 몇 번의 테스트가 필요한가? 이다. 그리고 의미심장한 숫자를 몇 개 던지는데... 우선 n = 4 일 때 가능한 subset pair의 개수는 "25개"이며 이 중 "1가지" 경우만 확인하면 된다. 또 n = 7 일 때 가능한 subset pair의 개수는 "966개"이며 이 중 "70가지" 경우만 확인하면 된다. 그러면 n = 1.. 2016. 9. 9.
Project Euler #103 (Special subset sums: optimum) 문제는 https://projecteuler.net/problem=103그러나 사실 103번은 맛보기고 105번과 106번이 진짜 문제라고 할 수 있다. 103번은n = 1: {1} n = 2: {1, 2} n = 3: {2, 3, 4} n = 4: {3, 5, 6, 7} n = 5: {6, 9, 11, 12, 13} 에서A = {a1, a2, ... , an}라는 optimum set이 있을 때, 다음 optimum set은 B = {b, a1+b, a2+b, ... ,an+b}, (이때 b는 A의 중간 원소) 이라서n = 6 to be A = {11, 17, 20, 22, 23, 24}, with S(A) = 117 일 것 같은데 실제로는 n = 6 is A = {11, 18, 19, 20, 22, .. 2016. 9. 9.
Project Euler #104 (Pandigital Fibonacci ends) 문제는 https://projecteuler.net/problem=104, 언어는 C를 사용했다. 문제를 해석하자면 첫 9자리 숫자와 마지막 9자리 숫자가 pandigital(1~9까지 숫자가 하나씩 반드시 존재)이 되는 피보나치 숫자의 index를 구하는 문제이다. 코드를 요약하자면 각각이 자리수 N개를 저장 가능한 변수를 M개 사용하여 더하기를 구현하여 사용하는 것이다. 아래 코드에서는 long long (typedef로 ubint로 줄여서 사용) 의 범위가 –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807임을 활용하여 0~(10^18 - 1), 즉 18자리를 이용하고 10^18를 overflow로 간주하여 사용할 것이다. 사실 ubint를 long l.. 2016. 9. 9.
Project Euler #107 (Minimal network) 차후에 자세하게 설명하겠지만 MST (Minimal Spanning Tree: 최소 신장 트리) 문제다. 여기서 "최소 신장 트리"라는 말은 "최소 가중치 신장 트리"라는 말의 단축형으로, 모든 신장 트리는 정확하게 |V| - 1개의 간선을 가지게 된다. (아래 코드의 coo부분) 따라서 간선의 수를 최소화 할 수는 없다. MST에 자세히 이후에 글을 쓰겠다. (https://en.wikipedia.org/wiki/Minimum_spanning_tree) 아래는 크루스칼 알고리즘으로 구현하였다. (크루스컬 알고리즘 의사코드 - 한글위키) #ifdef _MSC_VER #define _CRT_SECURE_NO_WARNINGS #endif #include #include #include #define N 40.. 2016. 9. 9.
병렬 컴퓨팅 효율검사 출처: http://web.skhu.ac.kr/~mckim1/Lecture/DS/dna/class15/class15_04.html 어떤 문제 를 해결하는 가장 빠른 순차 알고리즘의 실행시간을 이라 하자 여기서 은 입력 데이터의 개수 문제 를 해결하는 병렬 알고리즘이 개의 프로세서를 사용하여 의 시간 안에 그 문제를 해결 할 수 있다하자 이 보다 작을 수 없음 병렬 알고리즘의 효율성(Efficiency)는 와 의 비율로 표시 .......... 효율성의 값은 0과 1 사이의 수 - 1에 가까울수록 더 효율적인 알고리즘 예제 : 어떤 문제를 해결하는 가장 빠르다고 알려진 순차 알고리즘의 실행시간이 초이고, 4개의 .........프로세서를 사용하는 병렬 알고리즘이 그 문제를 푸는데 걸리는 시간이 초라 하자... 2016. 9. 9.
Project Euler #102 (Triangle containment) 문제는 https://projecteuler.net/problem=102, 그리고 언어는 C를 사용하였다. 문제를 해결하기 위해 가장 필요한 함수는 특정한 점(x0, y0)이 삼각형 ABC안에 있나 없나 확인하는 부분이다. 방향벡터의 외적으로도 풀 수 있다(http://blog.naver.com/kimrip/40159510013) 여기서는 이해하기 쉬운 방법을 소개한다. 삼각형을 살피기 전에 중학교때 배운 "부등식의 영역"을 복습해보자. http://mathbang.net/466 우선 두 점 (x1, y1), (x2, y2)를 지나는 직선의 방정식을 구해보자. 결과를 알더라도 한번 유도해보는 차원에서 살펴보자. 두 점을 지나는 직선을 라고 둘 때, a를 기울기, b를 절편이라고 한다. 즉 x = 0 일때.. 2016. 9. 7.
Syntax Highlighter를 쓰고싶다면... http://jb-story.tistory.com/13 여기를 참고하자! 2016. 9. 6.
Project Euler #101 (Optimum polynomial) 문제는 https://projecteuler.net/problem=101 처음에는 C언어 연습도 할 겸 malloc등을 이용해서 동적할당으로 배열 계산을 하려고 했다. 그러나.. u(10)이후 값은 unsigned long long 이나 unsigned __int64로 처리할 수 없었다. determinant나 adjugate와 같은 함수들을 기껏 다 구현해놓고 데이터 크기때문에 사용할 수 없었다..ㅠ 그래서 결국엔 Matlab으로 했다.. 우선 문제를 분석하면 아주 정통적인 행렬 문제란걸 알 수 있다. 예를들어 u(1), u(2), u(3)까지 커버되는 OP(3, n)의 식을 알고싶다면 이 만족되는 a, b, c를 구하면 된다. 구하고자하는 값이 3개이고, 방정식도 3개가 나오므로 노가다로 구할 수도 .. 2016. 9. 5.