입 달린 감자의 코딩 블로그

brute : 동물

force : 힘

브루트 포스 알고리즘은 동물처럼 무식하게 힘을 쓰는 알고리즘이다. 즉 모든 경우의 수를 탐색하면서 요구 조건에 충족되는 결과만 가져온다.

예를 들어 우리가 자전거를 훔친다고 생각하자. 0000~9999 의 비밀번호 중 하나일 것이므로 모두 시행해 자전거를 훔치면 된다. 노가다는 컴퓨터가 한다. 걱정하지마라.

password = int(input())

for i in range(0,9999):
    if password == i:
        print(i," 비밀번호 해제")

자전거를 훔치는데 1초도 안걸림을 확인할 수 있다.

백준의 2798번 문제를 풀어보자.

자 복잡하게 생각할 필요 없다. 컴퓨터한테 노가다 시키면 된다.

N,M = map(int,input().split())

arr = list(map(int,input().split()))

result = 0

for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1, N):
            sum = arr[i] + arr[j] + arr[k]
            if sum > M:
                continue
            else:
                result = max(result, sum)

print(result)

삼중 for 문을 사용해 모든 경우의 수를 계산해냈다.

선택 정렬은 오름차순으로 정렬할 때 배열에서 최솟값을 찾아 맨 앞에서 부터 정렬해 가는 방식이다.

말로는 이해하기 힘들 수도 있다. 그림을 한번 그려보자.

선택 정렬의 방식이다. 

3  4  2  1  에서 1)의 경우 1이 최솟값이다. 이 최소값과 최솟값의 자리에 있던 숫자를 교환하는 것을 반복하면 정렬이 되는 방식이다.

바로 프로그래밍 해보자.

#include <stdio.h>

void BubbleSort(int arr[], int n) {

	for (int i = 0; i < n - 1; i++) {
		int maxIdx = i; 
		for (int k = i + 1; k < n; k++) {
			if (arr[k] < arr[maxIdx]) {
				maxIdx = k; //최솟값을 찾는 과정
			}
			
		}
		int tmp = arr[i]; //최솟값과 교환
		arr[i] = arr[maxIdx];
		arr[maxIdx] = tmp;
	}
}

int main() {
	int arr[] = { 4,3,1,2 };
	BubbleSort(arr, sizeof(arr)/sizeof(int));

	for (int i = 0;i < 4; i++) {
		printf("%d ", arr[i]);
	}
}

시간 복잡도는 버블 정렬과 같이 (n-1) + (n-2) +  ... + 2 + 1 로 O(n^2) 이 된다.

서로소는 최대공약수가 1인 숫자들이다.

이 블로그 초반에 최대공약수와 최소공배수에 대한 개념을 정리한 적이 있다. 그것을 활용해보자.

int GCD(int a, int b) {
	int i;
	if (a > b)
		i = a;
	else
		i = b;

	for (int j = i; ;j--) {
		if (a % j == 0 && b % j == 0)
			return j;
	}
}

최대공약수에 대한 알고리즘이다. 자 그럼 최대공약수가 1이면 되니까 조건문을 사용하면 간단하겠다.

int GCD(int a, int b) {
	int i;
	if (a > b)
		i = a;
	else
		i = b;

	for (int j = i; ;j--) {
		if (a % j == 0 && b % j == 0)
			return j;
	}
}

void RelativelyPrime(int a, int b) {
	if (GCD(a,b) == 1) {
		printf("서로소 입니다!");
	}
	else {
		printf("서로소가 아닙니다!");
	}
}

int main() {
	RelativelyPrime(12, 4);
}

간단하게 프로그래밍 할 수 있다.

어디 컴공 편입 문제에서 본 것 같다. 이차방정식을 프로그래밍 해보거라...

간단할 것 같아서 오늘 해보겠다.

자 우리 중학교 시절로 돌아가보자. 그때 판별식 달달 외웠지... 비제곱마이너스사에이씨...

활용해서 프로그래밍해보자 

#include <stdio.h>
#include <cmath>

void Quad(int a, int b, int c) {
	double d1 = (-b + sqrt(b * b - 4 * a * c)) / (2 * a);
	double d2 = (-b - sqrt(b * b - 4 * a * c)) / (2 * a);

	if (b * b - 4 * a * c > 0) {
		printf("서로 다른 두 실근 %f, %f \n", d1, d2);
	}
	else if (b * b - 4 * a * c == 0) {
		printf("중근 %f \n", d1);
	}
	else {
		printf("허근 \n");
	}
}

int main() 
{
	Quad(1, -5, 4);
}

이런 수학 문제를 프로그래밍 하는 것은 정의나 정리만 잘 알면 쉽게 할 수 있는 것 같다.

 자 오늘은 머리도 좀 식힐 겸 확률 파트의 조합을 프로그래밍 해보자.

조합의 식은 아래와 같고

mCn = m!/(n!*(m-n)!)

!는 팩토리얼로 앞서서 구현한 적이 있다.

자 활용해서 프로그래밍 해보자.

#include <stdio.h>

int Factorial(int n) { //재귀적으로 팩토리얼 구현
	if (n == 1)
		return 1;
	else
		return n * Factorial(n - 1);
}//재귀적 구현

int Combination(int m, int n) {  
	int result = Factorial(m) / (Factorial(n) * Factorial(m - n)); //조합 공식
	return result;
}

int main() {
	printf("5C3 = %d", Combination(5,3)); //5C3의 결과 10이 출력된다.
}

심플하다.

자 오늘은 정렬 중에 기본인 버블 정렬에 대해 알아보자.

버블 정렬은 인접한 두 수를 대수 비교하면서 정렬하는 방법이다. 바로 그림을 보자.

4  2  3  1  에서 버블 정렬을 1회 시행해 본 그림이다.  4의 위치에 주목해서 보자.

4와 2를 비교하여 2가 우선순위가 앞섬을 알 수 있고 이에 따라 4와 2가 위치가 바뀐다.

마찬가지로 뒤에 숫자들과 비교하면서 자리를 바꿔주면 4는 자기 위치를 찾게 된다.

1회 시행에서 4의 위치를 찾았다. 그럼 2회 시행 시 어떤 숫자가 자기 자리를 찾아가겠는가?   3이다.

위 과정을 프로그래밍 해보자.

#include <stdio.h>

void BubbleSort(int arr[],int n) {
	for (int i = 0; i < n - 1; i++) {
		for (int k = 0; k < n - 1 - i; k++) {  //4의 위치를 찾았다면 4를 건들 필요가 없어진다.
			if (arr[k] > arr[k + 1]) {
				int tmp = arr[k + 1];
				arr[k + 1] = arr[k];
				arr[k] = tmp;  //배열값을 교환하는 알고리즘
			}
		}
	}
}

int main() {
	int arr[] = { 4,2,3,1 };

	BubbleSort(arr, 4);

	for (int i = 0; i < 4; i++) {
		printf("%d ", arr[i]);
	}
}

자 이제 시행 횟수를 통해 시간복잡도를 구해보자.

4  2  3  1  에서 1회 시행 시 4와 2, 4와 3, 4와 1 총 3번의 비교가 발생했다.

2회 시행 시 2와 3, 3과 1 총 2번의 비교가 발생했다.

결국 일반화 시키면 (n-1) + (n-2) + ... + 2 + 1 로

n(n-1)/2 로 나타낼 수 있으며 시간복잡도는 O(n^2) 임을 알 수 있다.