[Algorithm] 1주차 스터디 - 브루트 포스와 백트래킹

주제 : 시간복잡도와 Big-O 표기법, 브루트 포스와 백트래킹

Big-O 표기법

알고리즘의 성능을 수학적으로 표기해주는 방법. 시간과 공간 복잡도를 표기할 수 있다.

출처 : 구글 이미지 검색

O (1) > O (logn) > O (n) > O (nlogn) > O (n^2)  > O (n^3) > O (2^n)

위와 같은 성능 순서를 가지고 있다.

브루트 포스

가능한 모든 경우를 다 파악하는 경우 보통 브루트 포스라고 한다. (for문으로 전수조사..) 반복문이 쌓일 수록 지수의 성능을 가지게 된다.

백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘. 이름 그대로 이 경우가 아니다 싶으면 다시 돌아가서 다른 경우를 찾는 것. 브루트 포스보다 경우의 수가 줄어들 수 있지만, 최악의 경우 성능이 브루트 포스와 같을 수 있다.

 

---

필수 문제 풀이

백준 2309 - 일곱난쟁이(C++)

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

9명의 난쟁이 키가 입력으로 들어왔을 때 일곱 난쟁이 키의 합 100을 이용해 진짜 난쟁이 7명을 찾는 문제이다.

풀이

예전 통계를 배울 때 여집합을 이용하는 것 처럼 가짜 난쟁이 2명을 찾는 방법으로 계획했다. 따라서 난쟁이의 키를 입력 받을 때 합계도 동시에 기록하고, 두 가짜 난쟁이를 찾는 반복문을 통해 색출했다. 이 반복문은 총 키의 합 - (용의자1 + 용의자2) = 100인지 확인한다. 또한 작은 키부터 순서대로 결과값을 출력해야 하기 때문에 처음부터 오름차순으로 정렬하고 시작했다.

제출한 코드

#include <iostream>
#include <algorithm>

using namespace std;
int main() {
	int a[9];
	int sum = 0;
	for (int i = 0; i < 9; i++) {
		cin >> a[i];
		sum += a[i];
	}

	//오름차순 정렬
	sort(a, a + 9);
	for (int i = 0; i < 8; i++) {
		for (int j = 1; j < 9; j++) {
			if (sum - (a[i] + a[j]) == 100) {
				//결과 출력
				for (int m = 0; m < 9; m++) {
					if (m == i || m == j)
						continue;
					cout << a[m] << endl;
				}
				return 0;
			}
		}
	}

	return 0;
}

 

백준 1065 - 한수(C++)

https://www.acmicpc.net/problem/1065

1065번: 한수

한수 : 각 자리의 수가 등차수열을 이루는 수

입력값이 들어왔을 때 입렵값보다 작거나 같은 수 중에서 한수의 개수를 출력해야한다.

풀이

입력받은 숫자 N까지의 반복문을 통해 한수를 찾아 count를 높이도록 했다. 두자리 수까지는 모든 수가 한수이기 때문에 1부터 99까지는 한수의 값이 그 숫자 값이라고 여겼다. 세자리수부터는 한수인지 판별하는 함수를 통해 판별했다. 이 함수는 각 자리의 숫자값을 배열에 저장해 (일의자리수 - 십의자리수) 가 (십의자리수 - 백의자리수)인 숫자만 count하도록 했다. 문제에서 1000까지의 수를 입력받기 때문에 반복문에서 1000까지 판별하도록 했다.

제출한 코드

#include <iostream>
using namespace std;

int findX(int i) {
	int place[3];
	int gap = 0;

	for (int j = 0; j < 3; j++) {
		place[j] = i % 10;
		i = i / 10;
	}
	if (place[0] - place[1] == place[1] - place[2])
		return 1;
	else
		return 0;
}

int main() {
	int n;
	cin >> n;
	int count =0;

	//for 문 돌면서 한수 찾기
	for (int i = 1; i <= n; i++) {
		if (i < 100) {
			count = i;
		}
		else if (i == 1000) break;
		else
			count += findX(i);
			
	}
	cout << count;
	return 0;
}

 

백준 7568 - 덩치(Python)

https://www.acmicpc.net/problem/7568

7568번: 덩치

몸무게와 키 리스트를 입력받을 때 덩치 등수를 매겨 각 사람별로 등수를 출력해야한다.

덩치 :키와 몸무게 모두 높은 사람만 덩치가 크다고 인정받는다.

 

풀이

입력에 대한 처리가 Python이 익숙해서 Python으로 풀었다.. N값을 통해 몇명의 정보가 들어오는 지 알 수 있으므로 모든 반복문은 N을 기준으로 만들었다. 정보를 리스트에 저장한 후 각 정보값(몸무게,키) 모두가 상대방보다 큰 지 비교를 통해 알아낸 후 등수를 매겼다. 이 문제에는 동일 등수가 존재하기 때문에  먼저 1등으로 설정한 후 비교대상보다 덩치가 큰 상대가 나타났을 때 한 순위씩 밀려나도록 설계했다.

제출한 코드

N = int(input())
S = []
R = []
for i in range (N):
    S.append(list(map(int,input().split())))

for j in range(N):
    rank = 1
    for k in range(N):
        if j!=k:
            if (S[j][0] <S[k][0]) and (S[j][1] < S[k][1]):
                rank +=1
    R.append(rank)

for i in R:
    print(i,end=' ')