순열 구하기 (예제)

Programming/Algorithm 2016. 3. 10. 16:01 Posted by gaeddong2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#define SWAP(T,x,y) {T tmp = x; x = y; y = tmp;}
 
int m[100];
int v[100];
int N;
int tc;
 
void print(){
 for (int i = 0; i < N; i++)
  printf("%d ", m[i]);
 printf("\n");
}
 
void backtrack(int s){
 // condition
 if (s == N - 1){
  print();
  return;
 }
 
 //recursive
 for (int i = s; i < N; i++){
  SWAP(int, m[s], m[i]);
  backtrack(s + 1);
  SWAP(int, m[s], m[i]);
 }
}
 
int main(){
 freopen("output.txt", "w", stdout);
 int T; scanf("%d", &T); while (T--)
 {
  scanf("%d", &N);
  for (int i = 0; i < N; i++)
   scanf("%d", &m[i]);
 
  printf("#%d\n", ++tc);
  backtrack(0);
 }
 
 return 0;
}
cs


저작자표시

'Programming > Algorithm' 카테고리의 다른 글

길찾기 알고리즘(0 에서 99로 갈 수 있는지 확인)  (0) 2016.03.11
멱집합(부분집합) 응용, 조건에 따라 불필요한 부분집합 제거  (0) 2016.03.10
멱집합 (백트래킹 예제)  (0) 2016.03.10
회문 찾기 알고리즘  (0) 2016.03.10
문자열을 숫자로 변경 코드  (0) 2016.03.09

멱집합 (백트래킹 예제)

Programming/Algorithm 2016. 3. 10. 11:59 Posted by gaeddong2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
 
#define MAX 101
 
int Num;
int Arr[MAX];
int Print[MAX];
 
void output();
int BinaryFlag(int a);
void input()
{
 int i;
 
 //집합의 개수
 scanf("%d", &Num);
 //집합의 개수만큼 집합의 데이터를 입력받는다.
 for (i = 1; i <= Num; i++)
 {
  Print[i] = 0;
  scanf("%d", &Arr[i]);
 }
}
void process(int index)
{
 int i;
 
 //index 범위가 현재 배열의 데이터 길이보다 크면 return
 if (index > Num)
 {
  output();
  return;
 }
 
 for (i = 0; i < 2; i++)
 {
  //BinaryFlag 함수를 통해서 0, 1값을 가져와서 Print배열에 저장한다.
  Print[index] = BinaryFlag(i);
  process(index + 1);
  //output();
 }
}
int BinaryFlag(int a)
{
 int FlagArr[2] = { 1, 0 };
 return FlagArr[a];
}
void output()
{
 int i;
 int flag = 0;
 for (i = 1; i <= Num; i++)
 {
  if (Print[i] == 1)
  {
   printf("%d ", Arr[i]);
   flag++;
  }
 }
 if (flag != 0)
  printf("\n");
}
int main(void)
{
 //freopen("input.txt", "r", stdin);
 //freopen("output.txt", "w", stdout);
 
 int TC;
 int Tcc = 0;
 scanf("%d", &TC);
 while (TC--)
 {
  printf("#%d\n", ++Tcc);
  input();
  process(1);
  output();
 }
 return 0;
}
cs


저작자표시

'Programming > Algorithm' 카테고리의 다른 글

멱집합(부분집합) 응용, 조건에 따라 불필요한 부분집합 제거  (0) 2016.03.10
순열 구하기 (예제)  (0) 2016.03.10
회문 찾기 알고리즘  (0) 2016.03.10
문자열을 숫자로 변경 코드  (0) 2016.03.09
사다리타기 (알고리즘)  (0) 2016.03.09

회문 찾기 알고리즘

Programming/Algorithm 2016. 3. 10. 08:33 Posted by gaeddong2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <time.h>
 
char map[100][100];
int N;
int answer;
int tc;
 
bool isRowEqual(char * p, int len)
{
 for (int i = 0; i < (len + 1) / 2; i++)
 if (*(p + i) != *(p + len - 1 - i))
  return false;
 
 return true;
}
 
bool isColEqual(char * p, int len)
{
 for (int i = 0; i < (len + 1) / 2; i++)
 if (*(p + i * 100) != *(p + (len - 1 - i) * 100))
  return false;
 
 return true;
}
 
int main()
{
 freopen("input.txt", "r", stdin);
 freopen("output.txt", "w", stdout);
 
 int T = 10; while (T--)
 {
  // init
  answer = 0;
 
  scanf("%d", &tc);
 
  for (int i = 0; i < 100; i++)
   scanf("%s", map[i]);
 
  // row
  for (int h = 0; h < 100; h++)
  for (int w = 0; w < 100; w++)
  for (int k = 100 - w; k > answer; k--)
  if (isRowEqual(&map[h][w], k))
  {
   if (answer < k) answer = k;
   break;
  }
 
  // col
  for (int w = 0; w < 100; w++)
  for (int h = 0; h < 100; h++)
  for (int k = 100 - h; k > answer; k--)
  if (isColEqual(&map[h][w], k))
  {
   if (answer < k) answer = k;
   break;
  }
 
  printf("#%d %d\n", tc, answer);
 }
 
 return 0;
}
cs


저작자표시

'Programming > Algorithm' 카테고리의 다른 글

순열 구하기 (예제)  (0) 2016.03.10
멱집합 (백트래킹 예제)  (0) 2016.03.10
문자열을 숫자로 변경 코드  (0) 2016.03.09
사다리타기 (알고리즘)  (0) 2016.03.09
미로찾기 알고리즘 (BFS)  (0) 2016.03.09
 

티스토리툴바