part 2. 알고리즘 유형 분석 - 완전탐색

Chapter 2. 완전탐색 - 브루트포스

완전탐색

  • 장점 : 모든 경로를 본다 = 결국 답을 발견한다.
  • 단점 : 모든 경로를 본다 = 리소스를 많이 먹고, 모든 연산을 끝내야만 한

브루트 포스 Brute-force (무차별 대입)

  • 모든 경우의 수를 다 넣어 답을 맞추는 방식
  • 무식하지만 확실히 쓰인다.
    • 암호학, 수학 등 학계에서나 ProblemSolving(PS)에서도 널리쓰인다.
    • 우선 이 방식으로 답을 찾고 최적화하는 방법을 쓰기도 한다.

Chapter 2. 완전탐색 - 예제문제(1)

- 문제 : N개의 수를 입력 받아서 두 수를 뽑아 합이 가장 클 때는 
- 시간제한 : 1초, 입력 : 2 ≤ N ≤ 1,000,000
  • 그냥 완전탐색으로 값을 구할 수 있다.
  • 하지만 그냥 하게 된다고 하면 입력의 값의 크기로 인해 1초라는 시간 안에 해결이 안됨. (₂C₁₀₀₀₀₀₀ = {10⁶ * (10⁶ - 1)} / 2 * 1 = O(N²))
  • 고려해 볼 만한 방법
    1. 정렬을 사용해 본다. : 보통 O(N log N) 의 시간 복잡도가 소요됨
    2. 가장 큰 값이 들어올 때마다 기록하고, 모든 입력이 마무리 되면 더한다 : O(N) 의 시간복잡도가 예상된다.

Chapter 2. 완전탐색 - 순열 & 조합

순열 permutation

  • 모든 경우의 수를 순서대로 살펴볼 때 용이하다
  • next_permutation 활용하는 문제가 삼성 쪽에서 주로 나온 적이 있다.
#iuclude <algorithm>
// C++
vector<int> v = {0, 1, 2, 3}; // 정렬 되서 들어와야 한다 
do {
	for (int i : v) printf("%d ", i);
	printf("\n");
} while (next_permutation(v.begin, v.end));
# python
from itertools import permutations

v = [0, 1, 2, 3]
for i in permutation(v, 4):
	print(i, " ")
0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
...
3 2 0 1
3 2 1 0

조합 combination

  • 파이썬은 기본적으로 조합까지 제공한다.
from itertools import combinations

v = [0, 1, 2, 3]

for i in combinations (v, 2):
	print (i, " ")
0 1
0 2
0 3
1 2
1 3 
2 3

Chapter 2. 완전탐색 - 예제문제(3)

boj.kr/2309

일곱 난쟁이 스페셜 저지

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 128 MB 141530 58929 41325 41.792%
문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 “백설 공주와 일곱 난쟁이”의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

예제 입력 1 
20
7
23
19
10
15
25
8
13
예제 출력 1 
7
8
10
13
19
20
23

내 생각 정리

  • 우선 9명 중 7명을 뽑는 조합과 관련한 문제로 볼 수 있다.
  • python은 combinations 를 제공하므로 그렇게 해당 방식으로 조합의 값을 받아내고 거기서 100이 되는 경우를 발견한다.
  • 그렇게 한 뒤 받아낸 값에 대해 조합의 구성을 다시 쪼개서 리스트로 만든 뒤 정렬하여 출력한다.
  • 그렇게만 하면 틀린다 이유는?
    • 일단 시간 복잡도의 문제 수준은 아니다
    • 지문에서 함정은 없다. 입력에서 조합이 여러번 발생하면 아무거나 출력해도 상관이 없다고 한다. -> 지만 문제는 여러개가 맞을 수 있다고 하니 break 를 해줘야한다
# combinations 를 활용한 방법 
from itertools import combinations

heights = [int(input()) for _ in range(9)]

# 조합으로 해결하는 방법 
for combi in combinations(heights, 7):
  if sum(combi) == 100:
    for height in sorted(combi):
      print(height)
    break # 중요 포인트
# 함수 + for문으로 해결하는 방법 
from itertools import permutations, combinations

heights = [int(input()) for _ in range(9)]

heights.sort()
total = sum(heights)

def f():
    for i in range(8):
        for j in range(i+1, 9):
            if (total - heights[i] - heights[j] == 100):
                for k in range(9):
                    if (i != k and j !=k):
                        print(heights[k])
                return
                # exit 을 해도 된다. 
            
f() # 함수로 빼서 기능을 1회전만 하고 나오도록 만든다.