본문 바로가기
반응형

[알고리즘 + 자료구조]43

[알고리즘] 8퀸 문제 서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓기. int flag_a[8]; // 각 행에 퀸을 배치했는지 체크하는 배열 int flag_b[15]; // 대각선 /에 퀸을 배치했는지 체크하는 배열 int flag_c[15]; // 대각선 \에 퀸을 배치했는지 체크하는 배열 int pos[8]; // 각 열에서 퀸의 위치 // 각 열에서 퀸의 위치를 출력 void print() { int i; for(i = 0; i < 8; i++) { printf("%2d", pos[i]); } putchar('\n'); } // i 열에서 알맞은 위치에 퀸을 배치 void set(int i) { int j; for(j = 0; j < 8; j++) { if(!flag_a[j] && !flag_b[.. 2020. 11. 4.
[알고리즘] 하노이의 탑 // 원반[1] ~ 원반[no]를 x 기둥에서 y 기둥으로 옮김 void move(int no, int x, int y) { if(no > 1) move(no - 1, x, 6 - x - y); // 그룹을 시작 기둥에서 중간 기둥으로 printf("원반[%d]를(을) %d 기둥에서 %d 기둥으로 옮김\n", no, x, y); // 바닥 원반을 목표 기둥으로 if(no > 1) move(no - 1, 6 - x - y, y); // 그룹을 중간 기둥에서 목표 기둥으로 } 2020. 11. 4.
[ 알고리즘 ] 유클리드 호제법 유클리드 호제법 : 두 수 a b가 있을 떄, a를 b로 나눈 나머지가 r일 때 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 과정의 반복 속에 나머지가 0이 되었을 때 나누는 수가 두 수 a b의 최대공약수가 된다. // 정수 x, y 의 최대공약수 반환 // 유클리드 호제법 : 두 수 a b가 있을 떄, a를 b로 나눈 나머지가 r일 때 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 과정의 반복 속에 나머지가 0이 되었을 때 나누는 수가 두 수 a b의 최대공약수가 된다. int gcd(int x, int y) { if(y == 0) return x; else return gcd(y, x % y); } 자연수를 넘겨줘야 하겠지만, 0과 n의 최대공약수는 n인 사실이 있다. 또한 .. 2020. 11. 4.
[알고리즘] Factorial / 팩토리얼 1. 0! = 1 2. n > 0 이면 n! = n x (n - 1)! int factorial(int n) { if(n > 0) return n * factorial(n - 1); else return 1; } 2020. 11. 4.
반응형

티스토리툴바