브루트포스
핵심: 모든 경우의 수를 계산하고, 다 해보는 것
방법의 수가 적은 경우에만 사용하는것이다.
모든 문제를 풀수있는 방법이 아니다.
보통 재귀,순열,비트마스크를 사용해서 문제를 푼다.
- 문제의 가능한 경우의 수를 계산해본다. -> 직접 계산을 통해서 구한다.(손으로 계산)
- 가능한 모든 방법을 다 만들어본다.-> 하나도 빠짐 없이 만들어야한다.(재귀,순열,비트마스크)
- 각각의 방법을 이용해 답을 구해본다. -> 문제에 나와있는대로 답을 구해본다.
- 시간복잡도: 방법의 수 X 방법 1개의 시간복잡도
1. 그냥 다해보기
- 일곱난쟁이(https://www.acmicpc.net/problem/2309)
경우의수 = 9C2
- 사탕게임(https://www.acmicpc.net/problem/3085)
경우의수 = 2N^2
시간복잡도 = N^4
- 날짜계산(https://www.acmicpc.net/problem/1476)
경우의수 = 15 X 28 X 19
- 리모콘(https://www.acmicpc.net/problem/1107)
경우의수 = 1,000,000
숫자버튼을 누르고, 그 다음 +나- 중 하나만 연속해서 눌러야한다.
위 방법이 아니면 의미없는 방법이 포함되거나 같은 것이 반복되어서 최소를 구할수없다.
- 테트로미노(https://www.acmicpc.net/problem/14500)
회전,대칭가능 -> 블록의 개수 = 19가지
경우의수 = 19(어떤 테트로미노결정) X (NM)(=어디에 놓을건지 결정)
2. 건너 뛰며 해보기
-
카잉달력(https://www.acmicpc.net/problem/6064)
-
수이어쓰기1(https://www.acmicpc.net/problem/1748)
3. N중 for문
- 1,2,3 더하기(https://www.acmicpc.net/problem/9095)
4. 재귀★★★★★
1.순서와 관련된 문제
2.선택과 관련된 문제
- N과M (1)★ (https://www.acmicpc.net/problem/15649)
- N과M (2)★★★ (https://www.acmicpc.net/problem/15650)
- 순서와 선택★★★★★ 두가지 관점에서 문제풀이 가능
- N과M (3)★ (https://www.acmicpc.net/problem/15651)
-
N과M (4)★ (https://www.acmicpc.net/problem/15652)
-
N과M (5)(https://www.acmicpc.net/problem/15654)
-
N과M (6)(https://www.acmicpc.net/problem/15655)
-
N과M (7)(https://www.acmicpc.net/problem/15656)
-
N과M (8)(https://www.acmicpc.net/problem/15657)
-
N과M (9)(https://www.acmicpc.net/problem/15663)
-
N과M (10)(https://www.acmicpc.net/problem/15664)
-
N과M (11)(https://www.acmicpc.net/problem/15665)
-
N과M (12)(https://www.acmicpc.net/problem/15666)
5. 순열
모든 순서를 시도해보아야하고, 순서가 매우 중요한 의미가 있을때 사용한다.
임의의 수열을 다른 순서로 섞는 연산
첫순열(오름차순)에서 다음순열, 다음순열, ... , 마지막 순열(내림차순)까지 이동한다
다음순열
- a[i-1] < a[i]를 만족하는 가장 큰 i를 찾는다. -> O(N)
- j>=i 이면서 a[j]>a[i-1]를 만족하는 가장 큰 j를 찾는다 -> O(N)
- a[i-1]과a[j]를 swap한다. -> O(1)
- a[i]부터 순열을 뒤지는다. -> O(N)
- 전체순열 시간복잡도: O(N x N!)
문제
-
다음 순열(https://www.acmicpc.net/problem/10972)
-
이전 순열(https://www.acmicpc.net/problem/10973)
-
모든 순열(https://www.acmicpc.net/problem/10974)
-
차이를 최대로(https://www.acmicpc.net/problem/10819)
-
외판원 순회2(https://www.acmicpc.net/problem/10971)
-
★★★로또(https://www.acmicpc.net/problem/6603)
6. 재귀
다음상태란: 문제의 정답을 아직 구하지못하였고, 정답을 구하러가기 위해서 문제의 조건을 위배하지 않으면서 다음 상태를 만들어줘야 한다!
문제
- 1,2,3 더하기(https://www.acmicpc.net/problem/9095)
브루트포스(재귀)를 이용할때 찾아봐야하는것
- 불가능한 경우 (sum>goal) : 재귀호출을 계속해도 정답을 절대 찾을수없는 경우 또는 문제의 조건을 위배한 경우
- 정답을 찾은 경우 (sum==goal)
- 다음 경우(재귀함수)를 호출 (go(count+1,sum+i,goal))
- 암호 만들기(https://www.acmicpc.net/problem/1759)
- 경우의 수 = 2^c
- 불가능한 경우 (i>=alpha의크기)
- 정답을 찾은 경우 (만든 password의 길이==n)
- 다음 경우 호출:
1. i번째를 사용(go(n,alpha,password+alpha[i],i+1))
2. i번째를 사용x (go(n,alpha,password,i+1))
- 시간복잡도: 2^c
- 퇴사 (https://www.acmicpc.net/problem/14501)
- 경우의 수 = 2^N
- 함수 : go(day,sum)
- 불가능한 경우 (day>n+1)
- 정답을 찾은 경우 (day==n+1)
- 다음 경우 호출:
1. 상담을 한다 (go(day+t[day],sum+p[day]))
2. 상담을 하지않는다 (go(day+1,sum))
- 시간복잡도: 2^N
- 스타트와 링크(https://www.acmicpc.net/problem/14889)
- 경우의 수 = 2^N
- 함수 : go(index,first,second)
- 불가능한 경우 ()
- 정답을 찾은 경우 (index==n+1)
- 다음 경우 호출(두 경우 모두 호출 전에 first 또는 second에 index를 넣고 호출 후에 빼는 과정이 필요):
1. index사람을 1번 팀에 넣는다 go(index,first,second)
2. index사람을 2번 팀에 넣는다 go(index,first,second)
- 시간복잡도: 2^N
- <백트래킹을 이용>링크와 스타트(https://www.acmicpc.net/problem/15661)
- 경우의 수 = 2^N
- 함수 : go(index,first,second)
- 불가능한 경우 (first의 크기>n/2 or second의 크기>n/2)
- 정답을 찾은 경우 (index==n+1)
- 다음 경우 호출(두 경우 모두 호출 전에 first 또는 second에 index를 넣고 호출 후에 빼는 과정이 필요):
1. index사람을 1번 팀에 넣는다 go(index,first,second)
2. index사람을 2번 팀에 넣는다 go(index,first,second)
- 시간복잡도: 2^N
- <백트래킹을 이용>부등호(https://www.acmicpc.net/problem/2529)
- 경우의 수 = 9^k
- 함수 : go(index,num)
- 불가능한 경우 (index>n+1)
- 정답을 찾은 경우 (index==n+1)
- 다음 경우 호출: go(index+1,num+to_string(index))
- <백트래킹을 이용>맞춰봐(https://www.acmicpc.net/problem/1248)
7. 비트마스크
문제에 전체개수 중 일부를 이용해서 모든 방법을 구할때 이용할수있다.
비트마스크 연산
- 정수로 집합을 나타낼수 있다.
{1,3,4,5,9} = 570 = 2^1 + 2^3 + 2^4 + 2^5 + 2^9
- 0~N-1까지 정수로 이루어진 집합을 나타낼수있다.
- 비트마스크 연산
- 검사연산: 정수에 어떤 비트가 1인지 검사할수있다. ex(570 & (1<<1) = 2 -> 1번째 비트가 포함되어있는지 검사)
- 추가연산: ex) 2번째(4) 비트추가하기 -> 570 | (1<<2) = 574
- 제거연산: ex) 1번째(2) 비트제거하기 -> 570 & ~(1<<1) = 568
- 토글연산: ex) 1번째(2) 비트토글하기 -> 570 ^ (1<<1) = 568
- 전체집합 = (1<<N) - 1, 공집합=0
문제
- 집합(https://www.acmicpc.net/problem/11723)
- 부분수열의 합(https://www.acmicpc.net/problem/1182)
모든 집합의 개수=2^N
모든 집합을 구해보면 된다!
- 스타트와 링크(https://www.acmicpc.net/problem/14889)
모든 집합의 개수=2^N
모든 집합을 순회해본다!
- 종이조각(https://www.acmicpc.net/problem/14391)
+α
- 최솟값을 구하는 문제에서 의미없는 것이 있는 방법은 절대 최소가 될수없다.
- 최솟값을 구하는 문제에서 중복이 존재하는 방법은 절대 최소가 될수없다.
- 백트래킹: 재귀함수를 이용해 브루트포스를 하다보면, 더이상 함수호출이 의미없는 경우가 생기는데 이런 경우를 제외하고 브루트 포스를 진행하면 백트래킹이라고 한다.