TIL #6 알고리즘 기초 - 수학 (문제)

노력하는 배짱이·2020년 8월 7일

1. 문제 : GCD 합

중첩 for문을 사용하여 a[i]를 기준으로 a[i+1] 부터 a[n-1]까지 각각 최대공약수를 구해 합한다.
예를 들면, 5개가 있으면 1를 기준으로 [1,2], [1,3], [1,4], [1,5]들의 최대공약수를 구해서 더하는 것이다.

최대공약수의 합이 int범위를 넘어설 수 있기 때문에 long 타입으로 해야한다.
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int t = sc.nextInt();
	while (t-- > 0) {
		int n = sc.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		long sum = 0;
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				sum += gcd(a[i], a[j]);
			}
		}
		System.out.println(sum);
	}
}
public static int gcd(int num1, int num2) {
	if (num2 == 0) {
		return num1;
	} else {
		return gcd(num2, num1 % num2);
	}
}
2. 문제 : 숨바꼭질 6

해당 문제는 쉽게 말하면 최대공약수를 이용하는 문제이다.

동생 n명, 수빈이의 현재 점 S , 동생들의 위치 $A_1$ ~ $A_N$ 이 주어진다.

D의 최댓값을 구해야한다.

예시를 들면 이해하기 쉽다.
동생이 1명 즉 n=1일때 위치는 9이고, 수빈이의 현재 위치가 3이라 가정하자.
그러면 수빈이가 동생을 찾기 위해서는 3이라는 위치에서 6만큼 이동하면 동생위치(9)에 도달 할 수 있다.

여기서 X-D 혹은 X+D로 이동할 수 있다는 조건이 있는데, D가 1이면 3위치에서 9위치 까지 6번을 이동해야하고, D가 2이면 3번, D가 3이면 2번 D가 4나 5일 경우는 안되고 6일 경우 1번으로 총 D가 될수 있는 경우의 수는 1, 2, 3, 6이 된다.

경우의 수를 보면 떠오르는 것이 있을 것이다. 즉, D의 약수들인 것이다.
문제는 D의 최댓값을 구하라 했으니, 최대공약수를 구하면 된다.
따라서 동생위치 - 수빈이위치의 절댓값 들의 최대공약수를 구하면 되는 문제이다.
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt(); // 동생 n명
	int s = sc.nextInt(); // 수빈이의 현재 위치 s
	int[] a = new int[n]; // 거리차
	for (int i = 0; i < n; i++) {
		a[i] = sc.nextInt();
		a[i] = Math.abs(s - a[i]);
	}
	for (int i = 0; i < n; i++) {
		if (i + 1 < n) {
			a[i + 1] = gcd(a[i], a[i + 1]);
		}
	}
	System.out.println(a[n - 1]);
}
public static int gcd(int num1, int num2) {
	if (num2 == 0) {
		return num1;
	} else {
		return gcd(num2, num1 % num2);
	}
}
최대 공약수 값을 다음 인덱스 a[i+1]로 넣어서 계속 반복하면 마지막 인덱스에 결과가 나오게 된다.

3. 문제 : 2진수 8진수

public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	String s = sc.nextLine();
	int n = s.length();
	if (n % 3 == 1) {
		System.out.print(s.charAt(0));
	} else if (n % 3 == 2) {
		System.out.print((s.charAt(0) - '0') * 2 + (s.charAt(1) - '0'));
	}
	for (int i = n % 3; i < n; i += 3) {
		System.out.print((s.charAt(i) - '0') * 4 + (s.charAt(i + 1) - '0') * 2 + (s.charAt(i + 2) - '0'));
	}
}
2진수를 8진수로 변환하기 위해서는 뒤에서부터 3자리씩 끊어서 계산하면 된다.
3가지 경우가 존재하는데, 예를 들어 [편의상 공백으로 표시하였습니다.] 아래와 같이 주어지면

110 011 001

11 001 100

1 100 110

첫 번째 경우 정확히 3자리씩 나누어 떨어지지만 두 번째는 앞에 2개가 남고 세 번째는 앞에 1개가 남게 된다.
세 번째 경우는 간단하게 출력만 하면된다. 왜냐하면 무조건 1이 나오기 때문이다.
첫 번째 경우와 두 번째 경우는 자리에 맞춰 문자 '0'을 빼주고 자리에 맞게 2 또는 4를 곱해주면 된다.

4. 문제 : 8진수 2진수

public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	String[] numAry = { "000", "001", "010", "011", "100", "101", "110", "111" };
	String str = sc.nextLine();
	boolean begin = true;
	if (str.length() == 1 && str.charAt(0) == '0') {
		System.out.println(0);
	}
	for (int i = 0; i < str.length(); i++) {
		int n = str.charAt(i) - '0';
		if (begin == true && n < 4) {
			if (n == 0) {
				continue;
			} else if (n == 1) {
				System.out.print("1");
			} else if (n == 2) {
				System.out.print("10");
			} else if (n == 3) {
				System.out.print("11");
			}
			begin = false;
		} else {
			System.out.print(numAry[n]);
			begin = false;
		}
	}
}
8진수는 0부터 7까지이기 때문에 배열로 값을 저장해 두었다.
그리고 2진수의 앞부분부터 읽을건데, 앞에 0이 오면 안되기 때문에 0부터 3까지는 따로 출력하도록 하였고 나머지는 값에 맞는 인덱스를 배열에 넣어 출력하였다.

추가적으로 설명하자면 0은 000 1은 001 2는 010 3은 011 이라서 앞에 0이 붙는데 주어진 8진수의 맨 앞자리가 1, 2, 3 중에 하나가오면 저걸 그대로 쓸 수 없는 것이다.

5. 문제 : -2진수

기본적인 진법 변환과 유사한 문제이다.
하지만 이 문제에서는 여러가지 조건을 고려해야한다.
2진수로 변환하는 것처럼 풀면서 '-' 붙이는데 n이 음수일 때와 2로 나누어떨어질 때 그리고 나누어 떨어지지 않을 때를 고려해야한다.
예를들어 -13인 경우 -2 * 7 + 1과 같이 나타낼 수 있는데 이런식으로 구하면 된다. 즉, 나머지가 0또는 1이 나온다.

-13 = -2 * 7 + 1

7 = -2 * -3 + 1

-3 = -2 * 2 + 1

2 = -2 * -1 + 0

-1 = -2 * 1 + 1

1 = -2 * 0 + 1
결과 : 110111

2로 나누었을 때 0으로 나누어 떨어지면 0을 출력
2로 나누어지지 않고 양수인 경우 2로 나눈 몫에 '-'를 붙이고 '1'를 출력
2로 나누어지지 않고 음수인 경우 '+1'를 하고 2로 나누고 '1'를 출력

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	if (n == 0) {
		System.out.println(0);
	} else {
		go(n);
	}
}
public static void go(int n) {
	if (n == 0) {
		return;
	}
	if (n % 2 == 0) {
		go(-(n / 2));
		System.out.print(0);
	} else {
		if (n > 0) {
			go(-(n / 2));
		} else {
			go((-n + 1) / 2);
		}
		System.out.print(1);
	}
}

6. 문제 : 골드바흐 파티션

이전에 공부한 골드바흐의 추측 문제의 코드를 조금 수정하면 해결할 수 있는 문제이다.

해당 문제는 짝수 N을 두 소수의 합으로 나타내는 경우의 수를 구하는 문제이다.
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	ArrayList<Integer> primes = new ArrayList<>();
	boolean[] check = new boolean[1000001];
	for (int i = 2; i <= 1000000; i++) {
		if (check[i] == false) {
			primes.add(i);
			for (int j = i + i; j <= 1000000; j += i) {
				check[j] = true;
			}
		}
	}
	int t = sc.nextInt();
	while (t-- > 0) {
		int n = sc.nextInt();
		int cnt = 0;
		for (int p : primes) {
			if (n - p >= 2 && p <= n - p) {
				if (check[n - p] == false) {
					cnt += 1;
				}
			} else {
				break;
			}
		}
		System.out.println(cnt);
	}
}
primes라는 ArrayList에는 소수만 존재하고 입력된 수를 n이라 했을 때, n-소수(p)를 한 값이 check 배열에 존재하면 cnt 변수를 1씩 늘려주면 된다.
또한 문제의 조건으로 두 소수의 순서만 다른 것은 같은 파티션이다.이 주어졌기 때문에 p <= n-p 를 추가하면 조건을 만족시킬 수 있다.

7. 문제 : 진법 변환2

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int b = sc.nextInt();
	StringBuilder sb = new StringBuilder();
	while (n > 0) {
		int remainder = n % b;
		if (remainder < 10) {
			sb.append((char) (remainder + '0'));
		} else {
			sb.append((char) (remainder - 10 + 'A'));
		}
		n = n / b;
	}
	System.out.println(sb.reverse());
}

문제에서 10을 넘어가면 A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35로 표현하라고 되어있다.
그래서 나머지 값에 -10을 하고 문자 'A'를 더해주면 해당 조건처럼 나오게 된다.

8. 문제 : 진법 변환

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String n = sc.next();
	int b = sc.nextInt();
	int len = n.length();
	int num = 0;
	for (int i = 0; i < len; i++) {
		char c = n.charAt(i);
		if (c >= '0' && c <= '9') {
			num = num * b + (c - '0');
		} else {
			num = num * b + (c - 'A' + 10);
		}
	}
	System.out.println(num);
}

9. 문제 : Base Conversion

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int a = sc.nextInt();
	int b = sc.nextInt();
	int m = sc.nextInt();
	int result = 0;
	for (int i = 0; i < m; i++) {
		int x = sc.nextInt();
		result = result * a + x;
	}
	convert(result, b);
}
public static void convert(int num, int base) {
	if (num == 0) {
		return;
	}
	convert(num / base, base);
	System.out.print(num % base + " ");
}

10. 문제 : 소인수분해

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	for(int i=2; i*i <=n; i++) {
		while(n%i == 0) {
			System.out.println(i);
			n /=i;
		}
	}
	if(n>1) {
		System.out.println(n);
	}
}
입력으로 주어진 수가 n이라 했을 때 소인수분해를 하면 나올 수 있는 인수가 2부터 $\sqrt{n}$ 까지 이다.
따라서 2부터 $\sqrt{n}$ 까지 for문을 돌리고 N을 나눌 수 있으면 나눌 수 없을때까지 반복하면 된다.