완전탐색은 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색하는 방법입니다
'무식하게 푼다'의 의미인 Brute Force 라고도 부릅니다
모든 경우의 수를 탐색하기에 정확성은 100%, 효율성은 안좋습니다
따라서 주어진 N의 크기가 작을 때 사용하는 것이 좋습니다
'알고리즘' 이라기보다는 문제를 푸는 방법!!
완전탐색의 5가지 방법
완전탐색 기법으로 문제를 해결하기 위해선 아래와 같이 고려해보고 수행합니다
1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산
2. 가능한 모든 방법을 다 고려
3. 실제 답을 구할 수 있는지 적용
위의 2에서 말한 "모든 방법" 5가지
1. 단순 Brute Force
2. 순열
3. 재귀 호출
4. 비트마스크
5. BFS, DFS
단순 Brute Force
반복문, 조건문을 활용하여 단순하게 모든 방법을 찾는 방법
ex) 자물쇠 암호를 찾는 경우 (0000 ~ 9999 모든 경우를 확인)
BFS, DFS 활용
그래프 자료구조에서 모든 정점을 탐색하기 위한 방법
ex) 단순히 길을 찾는 문제 => BFS, DFS // 장애물, 목적지 추가 등 추가적인 작업 필요한 문제 => 완전 탐색 + BFS, DFS
순열
임의의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법인 순열을 활용하는 방법
서로 다른 N개를 일렬로 나열하는 순열의 경우의 수 = N! // N이 한 자릿수 정도..
완전탐색의 대표적인 유형
ex) n개의 숫자로 가능한 모든 순열을 만들어 경우의 수 확인
재귀 호출
재귀 함수를 통해 해결하는 방법
ex) 부분집합 문제, 만들고자 하는 부분 집합 S'일 때, S' = { }이며 각 원소에 대해 해당 원소가 포함되면 S'에 넣고 재귀 함수 호출, 포함되지 않으면 S'을 그대로 재귀 함수에 넣어주는 방식
비트마스크
비트(bit) 연산을 통해 부분 집합을 표현하는 방법
ex) 위의 재귀 호출과 마찬가지로 주로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 사용
차이를 최대로 성공
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 256 MB 25694 16649 12847 65.396%
문제
N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.
|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|
입력
첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.
출력
첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.
예제 입력 1
6
20 1 15 8 4 10
예제 출력 1
62
# n = int(input())
# num = map(int, input().split())
# nCr = itertools.permutations(num, n)
# def calculator(li):
# total = 0
# for i in range(len(li)-1):
# total += abs(li[i]-li[i+1])
# return total
# asw = -1e9
# for li in nCr:
# asw = max(asw, calculator(li))
# print(asw)